Областная олимпиада по математике, 2019 год, 9 класс

Сколькими способами можно раскрасить все клетки таблицы $2019\times 2019$ в черный и белый цвета так, чтобы в каждом квадрате $2 \times 2$ было ровно две белые и две черные клетки?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Ответ. $2^{2020}-2.$
Решение. Пусть $b$ обозначает черный цвет, а $w$ — белый. Назовем строку чередующейся, если ее раскраска имеет вид «$bwbw\ldots$» или «$wbwb\ldots$», в противном случае раскраску назовем обычной.
   Заметим, что в обычной раскраске строки существуют две соседние по стороне клетки одного цвета.
   Раскрасим 1-ю строку. Число способов сделать это равно $2^{2019}.$ Из них две раскраски являются чередующимися, а остальные ${(2^{2019}-2)}$ — обычными.
   i) Раскрасим 1-ю строку так, чтобы она была чередующейся (это можно сделать двумя способами). Тогда легко заметить, что и 2-я строка также должна быть чередующейся, так как в противном случае в каком-то квадрате $2 \times 2$ будут три клетки одного цвета. Причем эта строка может начинаться как с белой клетки, так и с черной. Следовательно, 2-ю, 3-ю, $\ldots,$ 2019-ю строки можно раскрасить двумя способами, а всю таблицу $2^{2019}$ способами.
   ii) Пусть 1-я строка является обычной. В этой строке есть блок из двух соседних клеток одного цвета. Без ограничения общности, пусть это блок «$bb$». Тогда во 2-ой строке под данными клетками должен быть блок «$ww$». Если у нас встречается блок «$bbw$», тогда во 2-ой строке под этим блоком должен быть блок «$wwb$». Следовательно, вторая строка получается из первой строки изменением цвета всех его клеток на противоположный, то есть вторая строка определяется однозначно и она также не является чередующимися. Повторяя этот процесс, получим, что цвета всех клеток таблицы определяются однозначно. Так как раскрасить 1-ю строку можно $2^{2019}-2$ способами, то и все оставшиеся клетки можно раскрасить $2^{2019}-2$ способами.
   В итоге получим, что требуемое количество раскрасок равно $$2^{2019}+(2^{2019}-2)=2^{2020}-2.$$