13-я Международная Жаутыковская олимпиада, 2017 год

Прямоугольник на клетчатой бумаге со стороной клетки 1 разбит на фигурки домино (прямоугольники, состоящие из двух клеток с общей стороной). Докажите, что все вершины клеток на границе и внутри прямоугольника можно раскрасить в три цвета так, чтобы для каждых двух вершин, находящихся на расстоянии 1, выполнялось следующее условие: эти вершины разного цвета, если соединяющий их отрезок лежит на границе одной из фигурок домино, и одинакового цвета в противном случае. ( А. Голованов )

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

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