На доске нарисован клетчатый прямоугольник 2×140. Будем считать две клетки соседними, если они имеют общую сторону. Сколькими способами можно закрасить ровно 139 клеток так, чтобы среди них не было соседних?
В каждом из
Закрашенные клетки в соседних столбцах должны стоять в разных строках. Поэтому в любой непрерывной группе непустых столбцов строки чередуются, и вся группа определяется выбором строки в первом её столбце:
Пусть пустым оказался столбец с номером
-
или : остаётся одна группа из столбцов, это способа. Для двух крайних положений получаем способа. -
(таких столбцов ): слева и справа от пустого столбца по одной группе. Между ними пустой столбец, поэтому группы выбираются независимо: способа. Всего способа.
Складываем:
Пустой столбец разбивает ряд на независимые группы, а в каждой группе строки чередуются, поэтому остаётся выбрать строку только в первом столбце группы.
