Question

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

Answer 1

ответ: 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\\$

И так далее, то есть $A_{n} -B_{n} =+-1$

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

$S= -1+1 = 0$

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