13-ші халықаралық Жәутіков олимпиадасы, 2017 жыл

Бірлік шаршылардан құралған тор қағазда доминоларға (ортақ қабырғасы бар екі шаршыдан құралған тіктөртбұрыш фигура) бөліктелген тіктөртбұрыш берілген. Тіктөртбұрыштың шекарасында және ішінде жатқан шаршылардың төбесі болатын барлық төбелерді, арақашықтығы 1-ге тең болатын кез келген екі төбе үшін келесі шарт орындалатындай үш түске бояуға болатынын дәлелдеңіз: осы екі төбені қосатын кесінді доминолардың біреуінің шекарасында жатса, онда осы төбелер әртүрлі түске боялған, және кері жағдайда бірдей түске боялған. ( А. Голованов )

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

Комментарии от администратора Комментарии от администратора №1.     Мы покажем, что существует требуемая раскраска специального вида. Именно, присвоив цветам номера 1, 2 и 3, мы назовём клетку правой, если эти цвета встречаются в таком порядке при обходе клетки по часовой стрелке, и левой — в противном случае. Тогда, если раскрасить клетки прямоугольника $m\times n$ в шахматном порядке, то существует раскраска требуемого вида, в которой все черные клетки правые, а все белые левые; такую раскраску мы назовём регулярной.
Заметим, что регулярная раскраска любой клетки нашего прямоугольника однозначно определена цветом любой из её вершин. Действительно, если эта клетка, скажем, чёрная (и поэтому должна быть правой с точки зрения раскраски вершин), мы можем начать с вершины, цвет которой известен и обойти клетку по часовой стрелке, прибавляя к номеру цвета 1 $\bmod 3$, если двигаемся по стороне фигурки домино, и не меняя цвет в противном случае.
Если две клетки имеют общую сторону, применение этой процедуры к одной из их общих вершин даёт один и тот же цвет для другой общей вершины: одна из двух клеток чёрная, а другая белая, а движение по общей стороне является обходом по часовой стрелке для одной клетки и против часовой стрелки для другой. Поэтому если клетка с одной непокрашенной вершиной граничит с двумя клетками, у которых все вершины покрашены регулярным образом, мы можем покрасить последнюю вершину так, чтобы получилась регулярная раскраска. Если клетка с двумя непокрашенными вершинами граничит с клеткой, вершины которой регулярно покрашены, мы можем докрасить две вершины клетки, так, чтобы получившаяся раскраска была регулярной.
Применяя эту процедуру, мы можем покрасить вершины всех клеток прямоугольника. Сначала с помощью шахматной раскраски определим, какие клетки должны быть левыми, а какие правыми. После этого покрасим левую нижнюю клетку, выбрав произвольным образом цвет левого нижнего угла. Это позволит нам поочерёдно раскрасить все вершины клеток нижнего ряда. Затем каждый следующий ряд мы покрасим, начиная с левой клетки: самая левая клетка примыкает к одной клетке, у которой все вершины уже покрашены, а каждая последующая — к двум.