Математикадан облыстық олимпиада, 2019 жыл, 9 сынып
Комментарий/решение:
Комментарии от администратора Комментарии от администратора №1.
Ответ. 22020−2.
Решение. Пусть b обозначает черный цвет, а w — белый. Назовем строку чередующейся, если ее раскраска имеет вид «bwbw…» или «wbwb…», в противном случае раскраску назовем обычной.
Заметим, что в обычной раскраске строки существуют две соседние по стороне клетки одного цвета.
Раскрасим 1-ю строку. Число способов сделать это равно 22019. Из них две раскраски являются чередующимися, а остальные (22019−2) — обычными.
i) Раскрасим 1-ю строку так, чтобы она была чередующейся (это можно сделать двумя способами). Тогда легко заметить, что и 2-я строка также должна быть чередующейся, так как в противном случае в каком-то квадрате 2×2 будут три клетки одного цвета. Причем эта строка может начинаться как с белой клетки, так и с черной. Следовательно, 2-ю, 3-ю, …, 2019-ю строки можно раскрасить двумя способами, а всю таблицу 22019 способами.
ii) Пусть 1-я строка является обычной. В этой строке есть блок из двух соседних клеток одного цвета. Без ограничения общности, пусть это блок «bb». Тогда во 2-ой строке под данными клетками должен быть блок «ww». Если у нас встречается блок «bbw», тогда во 2-ой строке под этим блоком должен быть блок «wwb». Следовательно, вторая строка получается из первой строки изменением цвета всех его клеток на противоположный, то есть вторая строка определяется однозначно и она также не является чередующимися. Повторяя этот процесс, получим, что цвета всех клеток таблицы определяются однозначно. Так как раскрасить 1-ю строку можно 22019−2 способами, то и все оставшиеся клетки можно раскрасить 22019−2 способами.
В итоге получим, что требуемое количество раскрасок равно 22019+(22019−2)=22020−2.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.