Ячейки таблицы 2 х n отмечаются. Таблица считается флексовой, если никакие две соседние по стороне ячейки не отмечены(в том числе, если не отмечено ни одной ячейки). Чему может…

Для решения этой задачи давайте обозначим количество флексовых таблиц размером 2 x n, в которых отмечено чётное число ячеек, как \(E_n\), а количество таблиц с нечётным числом отмеченных ячеек - как \(O_n\). Нам необходимо найти разность \(E_n - O_n\).

Прежде всего, выявим общую формулу для подсчёта количества таких таблиц. Рассмотрим динамическое программирование:

Обозначим \(a_n\) за количество флексовых таблиц 2 x n. Для этого:

1. Если первый столбец не содержит отмеченных ячеек, остаётся флексовая таблица размером 2 x (n-1), то есть \(a_{n-1}\).
2. Если первый столбец содержит только одну отмеченную ячейку, то это может быть либо ячейка в верхнем ряду, либо в нижнем. В этом случае, в оставшейся части таблицы (размер 2 x (n-2)) также будут продолжаться правила флексовости. Таким образом, это даёт \(2a_{n-2}\) способов.

Таким образом, рекуррентное соотношение будет выглядеть следующим образом: \[ a_n = a_{n-1} + 2a_{n-2} \]

Для базовых случаев:

• \(a_0 = 1\) (пустая таблица считается флексовой).
• \(a_1 = 2\) (две возможные конфигурации: либо ни одной ячейки не отмечено, либо одна ячейка отмечена).

Теперь мы можем постепенно найти значения \(E_n\) и \(O_n\). Заметим интересный факт: разность \(E_n - O_n\) будет равна количеству способов отметить 0 ячеек, поскольку отметка чётного количества ячеек всегда даст одну конфигурацию без отмеченных ячеек, тогда как не будет ни одного способа создать таблицу с нечётным количеством ячеек, не отмечая ни одной ячейки.

Следовательно, \(E_n - O_n = 1\) для любых n. Таким образом, разность между числом флексовых таблиц с чётным и нечётным числом отмеченных ячеек всегда равна 1.