tex]. В ответ запишите сумму всех этих значений...

July 2022 1 45 Report

На клетчатой доске размером 2 х n клеток некоторые клетки закрашиваются в красный цвет. Раскраска называется правильной , если среди закрашенных нет двух соседних клеток(соседними называются клетки, имеющие общую сторону) Раскраска, в которой ни одна клетка не закрашена, тоже считается правильной. Пусть [tex]A_{n}[/tex] - количество правильных раскрасок с четным числом закрашенных клеток, [tex]B_{n}[/tex] - количество правильных раскрасок с нечетным числом закрашенных клеток. Найдите все возможные значения [tex]A{n} - B{n}[/tex]. В ответ запишите сумму всех этих значений.

Answers & Comments

OneGyrus

Ответ: 0

Объяснение:

Здравствуйте!

Попробуем составить рекуррентное соотношение для чисел раскрасок.

Пусть для доски $2*k$ имеем $A_{k}$ правильных раскрасок с четным числом закрашенных клеток и $B_{k}$ правильных раскрасок с нечетным числом закрашенный клеток, для доски

$2*(k-1)$ : $A_{k-1}$ и $B_{k-1}$ , соответственно. Определим $A_{k+1}$ и $B_{k+1}$ для доски $2*(k+1)$ .

Добавим к предыдущей доске, поверх $k$ -й снизу строки, $k+1$ -ю строку. Вставим в нее одну из правильных раскрасок доски $2*k$ . У нас есть 3 варианта как мы можем закрашивать квадратики в новой строке.

Закрашиваем левую клетку, закрашиваем правую клетку или вообще не закрашиваем. Необходимо понимать, что если мы закрашиваем левую клетку в $k+1$ -й строке, то в $k$ -й строке закрашен правый квадратик, либо вообще ничего не закрашено и наоборот.

Пусть мы не закрасили в верхней строке ни одного квадрата, в этом случае общее число четных раскрасок : $N_{1}$ = $A_{k}$ , а нечетных : $K_{1} =B_{k}$

(Будем считать, что пустая раскраска входит в число четных)

Пусть мы закрасили левый квадрат в $k+1$ -й строке, в этом случае либо правый квадрат $k$ -й строки закрашен, либо вообще ничего не закрашено. То есть из всех вариантов $A_{k}$ или $B_{k}$ нужно вычесть те, в которых левая клетка окрашена. Из симметрии очевидно, что числа вариантов с левой и правой окрашенной клетками равны.

Чтобы найти число всех вариантов с окрашенной левой или правой клеткой, нужно из общего числа вариантов вычесть варианты с незакрашенными клетками.

Очевидно, что число таких вариантов равно : $A_{k-1}$ или $B_{k-1}$

Учитывая, что с добавлением одной закрашенной клетки четность меняется, то имеем:

$> , где <img src=$ и $N_{3}$ - количества правильных раскрасок с четным числом закрашенных квадратов,

с закрашенным в $k+1$ -й строке левым(индекс 2) и правым (индекс 3) квадратом.

Аналогично:

$> , где <img src=$ и $K_{3}$ - количества правильных раскрасок с нечетным числом закрашенных квадратов, с закрашенным в $k+1$ -й строке левым(индекс 2) и правым (индекс 3) квадратом.

Таким образом :

$A_{k+1} =N_{1} + N_{2} + N_{3} = N_{1} +2N_{2} = A_{k} + B_{k} + B_{k-1}\\B_{k+1} =K_{1} + K_{2} + K_{3} = K_{1} +2K_{2} = B_{k} + A_{k} + A_{k-1}\\A_{k+1} -B_{k+1} = B_{k-1} - A_{k-1}$

Найдем : $A_{1,2} ; B_{1,2}$

Когда $n=1$ , число вариантов с нечетным числом клеток равно $B_{1} = 2$ (левый и правый квадрат закрашены) . С четным же числом клеток такая комбинация только одна $A_{1}= 1$ , когда ни одна клетка не закрашена (0 клеток, 0 делится на 2). $A_{1} -B_{1} =1-2 = -1$

Когда $n= 2$ , число вариантов с нечетным числом клеток равно $B_{2} = 4$

(все варианты закрасить одну клетку, поскольку 3 клетки всегда будут вплотную) . С четным числом клеток имеем $A_{2} = 3$ таких комбинаций ( две комбинации с двумя клетками по диагонали и одна комбинация с незакрашенными клетками). $A_{2} -B_{2}= 3-4 = -1$

Из полученного выше свойства имеем:

$></p><p>И так далее, то есть <img src=$

Таким образом, сумма возможных значений $A_{n} -B_{n}$ равна:

$S= -1+1 = 0$

Если вам понравилось решение, ставь лайк и отметь его лучшим.

2 votes Thanks 3

Simba2017 метод математической индукции... в школе его не проходят...

Simba2017 но объяснение вполне понятное, спасибо!

OneGyrus Вообще-то проходят. Но тут скорее рекуррентную формулу составили.

OneGyrus Может это отдаленно и похоже на метод мат индукции, но тут мы сами выведи рекуррентное соотношение, а не доказывали его.

GluV Я использовал метод динамического программирования. Все раскраски можно разбить на правильные и неправильные. Правильные, можно разбить на такие, у которых последний столбец пустой, а так же такие у которых в последнем столбце закрашен один квадрат, верхний или нижний.

Answers & Comments

tex]...

oharakterizujte vse sluchai oslozhnenij 1 konechno s etim boryutsya te kto hotel

29 otmette nomer predlozheniya v kotorom ne stavitsya zapyataya na meste propuska

pomogite srochno v pryamougolnom treugolnike dlina vysoty provedennoj k gipoted07423c52d33678257448c62ac4211c 56692

obrazuyushaya konusa naklonena k ploskosti ego osnovaniya pod uglom 45 gradusov a eg

45 otmette nomer predlozheniya v kotorom na meste propuska ne stavitsya dvoetochic136f324872e6ebc51696e152c71da41 53317

uprostite logicheskoe uravnenie ekvivalentnymi preobrazovaniyami do minimalnogo v

pomogite srochno v ravnobedrennom treugolnike abc s osnovanie ab vershiny a c

v treugolnoj piramide tri grani vzaimno perpendikulyarny i ih ploshadi ravny 210

27 otmette nomer predlozheniya gde na meste propuskov ne nado stavit zapyatye

рекомендуемые вопросы

Helpful Links

Helpful Social