Задача 97823

Темы:    [ Раскраски ] [ Принцип Дирихле (углы и длины) ] [ Шахматные доски и шахматные фигуры ] [ Примеры и контрпримеры. Конструкции ] [ Четность и нечетность ]

Сложность: 4- Классы: 8,9,10

Условие

Авторы: Печковский А.Н., Итенберг И.

Дана бесконечная клетчатая бумага со стороной клетки, равной единице. Расстоянием между двумя клетками называется длина кратчайшего пути ладьи от одной клетки до другой (считается путь центра ладьи). В какое наименьшее число красок нужно раскрасить доску (каждая клетка закрашивается одной краской), чтобы две клетки, находящиеся на расстоянии 6, были всегда окрашены разными красками?

Решение

  Пример раскраски клетчатой плоскости в четыре цвета, при которой каждые две клетки на расстоянии 6 окрашены в разные цвета, представлен на рис. слева.

  Другой пример. Введём на клетчатой плоскости систему координат. Достаточно раскрасить клетки с чётной суммой координат (раскраска остальных клеток получается из этой сдвигом на 1 вправо). Точки, у которых сумма координат кратна 4, раскрасим в два цвета: если обе координаты чётные – в синий, если обе нечётные – в красный. Точки, у которых сумма координат чётна, но не кратна 4, аналогично раскрасим в оставшиеся два цвета.
  Чтобы доказать, что меньшим числом цветов обойтись нельзя, достаточно рассмотреть четыре клетки, показанные на рис. справа. Любые две из них расположены на расстоянии 6 друг от друга, и следовательно, все они должны быть окрашены в разные цвета.

Ответ

В 4 цвета.

Замечания

1. 8 баллов.

2. Ср. с задачей 98224.

Источники и прецеденты использования

олимпиада
Название	Турнир городов
Турнир
Дата	1983/1984
Номер	5
вариант
Вариант	весенний тур, основной вариант, 7-8 класс
Задача
Номер	1
олимпиада
Название	Турнир городов
Турнир
Дата	1983/1984
Номер	5
вариант
Вариант	весенний тур, подготовительный вариант, 7-8 класс
Задача
Номер	5