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