ГЛАВНАЯ » РЕШЕБНИК

2019-01-23   
Квадрат $3000 \times 3000$ произвольным образом разбит на доминошки (т. е. прямоугольники $1 \times 2$ клетки). Докажите, что доминошки можно раскрасить в три цвета так, чтобы доминошек каждого цвета было поровну и у каждой доминошки было не более двух соседей ее цвета (доминошки считаются соседними, если они содержат клетки, соседние по стороне).


Решение:



Раскрасим клетки квадрата в черный и белый цвет в шахматном порядке. Каждая доминошка покрывает ровно одну черную клетку. Разобьем квадрат $3000 \times 3000$ на квадраты $6 \times 6$, и в каждом квадрате перекрасим черные клетки в 3 цвета как показано на рисунках. Окрасим доминошки в первый, второй и третий цвета так, чтобы доминошка накрывала клетку своего цвета.

В квадрате $6 \times 6$ поровну клеток каждого цвета, значит и в квадрате $3000 \times 3000$ тоже. Следовательно, доминошек каждого цвета поровну. Пусть две клетки одного цвета покрыты соседними доминошками. Легко видеть, что для наших раскрасок это возможно только если эти две клетки имеют общую вершину. Для данной клетки на имеется не более двух клеток того же цвета, имеющих с ней общую вершину, а на - не более одной такой клетки. Отсюда следует, что если использовать раскраску , то для любой доминошки имеется не более двух соседних доминошек того же цвета, а если использовать раскраску , то даже не более одной соседней доминошки того же цвета.