Question

На клетчатой доске размером 2 х 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}$

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

$> , где <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$

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

Answer 2

Давайте рассмотрим, как можно закрасить клетки на доске 2 x n, чтобы получить правильную раскраску. Поскольку ни одна клетка не может иметь двух соседних закрашенных клеток, у нас есть два возможных варианта для первой строкой (где "R" обозначает закрашенную клетку, а "W" - не закрашенную):

1. RW RW RW ... RW (четно закрашенных)
2. WR WR WR ... WR (четно закрашенных)

Теперь давайте посмотрим, как можно продолжить раскраску для каждого из этих вариантов.

Для первого варианта (начинается с закрашенной клетки):

1. RW RW RW ... RW (четно закрашенных) WR WR WR ... WR (нечетно закрашенных)

Для второго варианта (начинается с не закрашенной клетки):

2. WR WR WR ... WR (четно закрашенных) RW RW RW ... RW (нечетно закрашенных)

Таким образом, у нас есть рекуррентная формула для подсчета числа правильных раскрасок для каждого из случаев:

Пусть E(n) - количество правильных раскрасок с четным числом закрашенных клеток на доске 2 x n, O(n) - количество правильных раскрасок с нечетным числом закрашенных клеток на доске 2 x n.

Тогда формулы будут следующими:

E(n) = E(n-1) + O(n-1) (переход от четного к четному) O(n) = E(n-1) + O(n-1) (переход от нечетного к четному)

Начальные условия: E(1) = 1 (все клетки не закрашены) O(1) = 1 (одна клетка закрашена)

Мы можем использовать эти рекуррентные формулы, чтобы посчитать количество правильных раскрасок для разных значений n, начиная с 2 и увеличивая n. Исходя из этих значений, мы можем найти сумму значений E(n) и O(n) для всех n.

Пример для n = 2: E(2) = E(1) + O(1) = 1 + 1 = 2 O(2) = E(1) + O(1) = 1 + 1 = 2

Сумма для n = 2: 2 + 2 = 4

Аналогично, вы можете продолжить вычисления для более больших значений n и найти сумму значений E(n) и O(n) для всех этих значений.