Loading [MathJax]/jax/output/SVG/jax.js

Математикадан облыстық олимпиада, 2019 жыл, 9 сынып


Өлшемі 2019×2019 болатын кестенің барлық шаршыларын, әрбір 2×2 квадраттың дәл екі қара және екі ақ шаршысы болатындай етіп, қанша әдіспен бояуға болады?
посмотреть в олимпиаде

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

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