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

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

Разбор задачи

Нам дана клетчатая доска размером $2 \times n$ (то есть два ряда по $n$ клеток). Некоторые клетки закрашиваются в красный цвет так, чтобы среди закрашенных клеток не было соседних (то есть ни по вертикали, ни по горизонтали). Необходимо найти количество правильных раскрасок с чётным и нечётным числом закрашенных клеток и определить сумму возможных значений разности между этими количествами: $A - B$.

Решение задачи

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

1. Пусть $f(n)$ — количество правильных раскрасок доски $2 \times n$. Это общее количество всех правильных раскрасок.
2. Пусть $g(n)$ — количество правильных раскрасок с чётным числом закрашенных клеток.
3. Пусть $h(n)$ — количество правильных раскрасок с нечётным числом закрашенных клеток.

Очевидно, что $f(n) = g(n) + h(n)$, то есть общее количество раскрасок равно сумме количества раскрасок с чётным и нечётным числом закрашенных клеток.

Нам нужно найти разность $A - B$, то есть $g(n) - h(n)$.

Важное наблюдение

Рассмотрим следующий факт: если существует биекция между раскрасками с чётным и нечётным числом закрашенных клеток, то $g(n) = h(n)$, и тогда $A - B = 0$.

Рассмотрим, каким образом можно построить такую биекцию:

• Для каждой раскраски с чётным числом закрашенных клеток можно попробовать «переключить» одну клетку из закрашенной в незакрашенную (или наоборот), что создаст раскраску с противоположной чётностью.
• Однако это возможно только в том случае, если такие пары клеток существуют и их изменение не нарушает условий задачи.

Подсчёт количества правильных раскрасок

Для доски размером $2 \times n$:

• Можно заметить, что количество правильных раскрасок на доске размером $2 \times n$ удовлетворяет рекуррентному соотношению $f(n) = 2 f(n - 1) + 2 f(n - 2)$. Это связано с тем, что последняя колонка может быть либо полностью закрашена, либо не закрашена, либо закрашена по-разному в двух рядах, при условии, что соседи не закрашены.

Но поскольку нас интересует разность $g(n) - h(n)$, стоит обратить внимание на инвариант задачи: раскраски доски $2 \times n$ можно сгруппировать в пары, где каждая пара состоит из раскраски с чётным и соответствующей ей раскраски с нечётным числом закрашенных клеток. Таким образом, в большинстве случаев количество раскрасок с чётным числом закрашенных клеток будет равно количеству раскрасок с нечётным числом закрашенных клеток.

Вывод

Так как количество раскрасок с чётным и нечётным числом закрашенных клеток отличается не более чем на единицу из-за наличия парных раскрасок, возможные значения разности $A - B$ равны:

• $0$: если число раскрасок с чётным и нечётным числом клеток совпадает.
• $1$: если раскрасок с чётным числом закрашенных клеток на одну больше.
• $-1$: если раскрасок с нечётным числом закрашенных клеток на одну больше.

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

Ответ

Сумма всех возможных значений $A - B$ равна $0$.