Подсчеты в клетчатых задачах

Количество всех раскрасок квадрата в два цвета — ровно Найдем количество раскрасок, которые можно получить с помощью перекрашивания исходной по указанным правилам. Назовем перекрашивание одного и того набора клеток доски видом перекрашивания. Заметим, что

Полученная раскраска не зависит от порядка выбора видов перекрашивания, а только от их количества.

Если некоторый вид перекрашивания использовался раз в некотором перекрашивания, то полученная раскраска совпадает с той, если бы он использовался раз, а количество остальных видов осталось таким же. Тем самым, мы можем считать, что каждый вид перекрашивания участвует в перекраске или раз.

Найдем количество видов перекрашивания. Всего существуют различных квадратов квадратов и квадрата Таким образом, количество видов перекрашивания равно каждый из которых используется в перекрашивание или раз, следовательно, общее количество перекрашивании равно а значит, найдется раскраска, которую получить невозможно.