Олимпиадная задача: сколько цветов нужно для раскраски клетчатого листа с условиями на расстояния и фигуры?

  а) См. задачу 197823.   б) Пример восьмицветной раскраски показан на рис. слева.

 Оценка. Рассмотрим семиклеточную фигуру на рис. а) в центре. Любые две её клетки можно покрыть одной "буквой Γ" из четырёх клеток, поэтому все её клетки должны быть разноцветными. Следовательно, в фигуре на рис. б) клетки, отмеченные звездочками, при семицветной раскраске должны быть одного цвета (потому что остальные её шесть клеток нужно покрасить в шесть разных цветов). Значит, в любой бесконечной решётке с шагом в три клетки (рис. справа) все клетки должны быть окрашены одним цветом, а остальные клетки плоскости – другими цветами. Но в таком случае потребуется уже не семь, а девять цветов: по числу таких решёток, покрывающих плоскость.

а) В 4 цвета;  б) в 8 цветов.