Условие задачи (1984, № 9) Задача М883 // Квант. — 1984. — № 9. — Стр. 34—35; 1984. — № 12. — Стр. 36—37.
В какое наименьшее число цветов нужно раскрасить клетки бесконечного листа клетчатой бумаги, чтобы
- любые две клетки на расстоянии 6 были покрашены в разные цвета? (Расстояние между клетками — наименьшее число линий сетки, горизонтальных и вертикальных, которые должна пересечь ладья на пути из одной клетки в другую.)
- любые четыре клетки, образующие фигуру в форме буквы Г (рис. 1), были покрашены в четыре разных цвета?
Изображения страниц
Решение задачи (1984, № 12) Задача М883 // Квант. — 1984. — № 9. — Стр. 34—35; 1984. — № 12. — Стр. 36—37.
а) Ответ: в 4 цвета. Пример раскраски клетчатой плоскости в 4 цвета, при которой любые две клетки на расстоянии 6 окрашены в разные цвета, представлен на рисунке 2.
Чтобы доказать, что меньшим числом цветов обойтись нельзя, достаточно рассмотреть 4 клетки, показанные на рисунке 3. Любые две из них расположены на расстоянии 6 друг от друга и, следовательно, все они должны быть окрашены в разные цвета.
б) Ответ: в 8 цветов. Схема доказательства повторяет пункт а): надо привести пример 8-цветной раскраски (он показан на рисунке 4) и объяснить, почему семи цветов недостаточно.
Рассмотрим 7-клеточную фигуру на рисунке 5, а. Любые две её клетки можно покрыть одной «буквой Г» из четырёх клеток, поэтому все её клетки должны быть разноцветными. Следовательно, в фигуре на рисунке 5, б клетки, отмеченные звёздочками, при 7-цветной раскраске должны быть одного цвета (потому что остальные её 6 клеток нужно покрасить в 6 разных цветов). Тогда, очевидно, в любой бесконечной решётке с шагом в 3 клетки (рис. 6) все клетки должны быть окрашены одним цветом, а остальные клетки плоскости — другими цветами. Но в таком случае потребуется уже не 7, а 9 цветов (по числу таких решёток, покрывающих плоскость).