** клетчатой доске размером 2 х n клеток некоторые клетки закрашиваются в красный цвет....

Question

325k просмотров

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

Алгебра аноним 30 Авг, 24 | 325k просмотров

Дан 1 ответ

OneGyrus_zn · Answer 1 · 2024-08-29T23:36:02+0000

Ответ: 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}$

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

$N_{2} = N_{3} = B_{k} - \frac{ B_{k} - B_{k-1}}{2} = \frac{ B_{k} + B_{k-1}}{2} \\$ , где $N_{2}$ и $N_{3}$ - количества правильных раскрасок с четным числом закрашенных квадратов,

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

Аналогично:

$K_{2} = K_{3} = \frac{ A_{k} + A_{k-1}}{2} \\$ , где $K_{2}$ и $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$

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

$A_{3} -B_{3} = B_{1} -A_{1} = -(A_{1} -B_{1}) = 1\\A_{4} -B_{4} = B_{2} -A_{2} = -(A_{2} -B_{2}) = 1\\A_{5} -B_{5} = B_{3} -A_{3} = -(A_{3} -B_{3}) = -1\\$