Задание 6 "Раскраски плоскости"
Для плоскости взята какая-то единица длины. Расстояния в
дальнейшем измеряются ею. Раскраска плоскости k красками - это
разбиение плоскости на k непересекающихся множеств. Это значит,
что каждая точка плоскости относится к одному и только одному
из этих множеств. Можно считать, что множества занумерованы
числами 1, 2, ..., k, и что это номера красок.
6.1. Плоскость как-то (неизвестно как) раскрашена двумя краска-
ми. Докажите, что найдутся две точки одного цвета на расстоянии
1.
6.2. Плоскость как-то (неизвестно как) раскрашена двумя краска-
ми. Докажите, что найдутся две точки разного цвета на рассто-
янии 1.
6.3. Плоскость как-то (неизвестно как) раскрашена тремя краска-
ми. Докажите, что найдутся две точки одного цвета на расстоянии
1.
6.4. Расположите 7 точек на плоскости так, чтобы среди любых
трех из них нашлись две на расстоянии 1.
6.5. Есть ли связь между задачами 6.4 и 6.3, и если есть, то в
чем она выражается?
6.6. Докажите, что можно раскрасить плоскость 9 красками так,
что не найдутся две точки одного цвета на расстоянии 1.
6.7. Докажите, что можно раскрасить плоскость 7 красками так,
что не найдутся две точки одного цвета на расстоянии 1.
6.8. Трехмерное пространство как-то раскрашено а) тремя, б) че-
тырьмя красками. Докажите, что найдутся две точки одного цвета
на расстоянии 1.
6.9. Обобщите задачу 6.8 на случай а) четырехмерного, б) n-мер-
ного пространства.
О задачах
Насколько я помню, задачи 6.1, 6.2, 6.6 и 6.7 были среди ре-
комендованных для проведения областных олимпиад Оргкомитетом
Всероссийской математической олимпиады в 1966 году. Они доступ-
ны учащимся 7-9 классов (и старше). Шестиклассники тоже кое-что
могут сделать, если будут подходить к этой математике с позиций
здравого смысла, как это было в древности, когда, например, для
числа pi знали только приближение и не имели алгоритма его
уточнения, а представление о доказательстве только формирова-
лось. Задача 6.3 появилась среди рекомендованных для областных
олимпиад в 1967, а 6.4 - в 1970 году. После этого эти задачи
стали обычными для математических кружков. Они доставляют логи-
ческие трудности, ведь в номерах 6.1 - 6.3 про раскраску ничего
не известно, а в задачах 6.6 и 6.7 на придумывание конкретных
раскрасок нужна еще и точность в сравнении разных расстояний.
Что касается математической литературы того времени, то сто-
ит, наверное, посмотреть вторую, посвященную планиметрии, книгу
Шклярского, Ченцова и Яглома из Библиотеки математического
кружка, издание 1967 года или более позднее, и книгу Хадвигера
и Дебруннера "Комбинаторная геометрия плоскости".
Но настояшее исследование по этим задачам и далее провел
Александр Сойфер < http://www.uccs.edu/~asoifer > в статье в
журнале "Математическое образование", N 1 за 1999 год:
http://www.fmop.dnttm.ru
Вот кое-что из этой его статьи.
Определение. Хроматическим числом плоскости называется наимень-
шее чмсло цветов, достаточное для раскраски плоскости так, что-
бы не нашлось двух точек одного цвета на расстоянии 1 друг от
друга.
Задача 6.3 говорит о том, что это число больше или равно 4,
а задача 6.7 -- что оно меньше или равно 7.
За все прошедшие годы ни одному из математиков не удалось
улучшить эти результаты, доступные школьникам. Так что неизве-
данное -- совсем рядом.
Задачу 6.4 школьники решают на кружках, и Вы тоже можете
найти ее решение. Оказывается, эта конструкция была придумана и
замечательным математиком этого столетия Эдвардом Нелсоном в
1950 году.
Оказывается, есть другая конструкция из 10 точек, тоже "ре-
шающая" задачу 6.3 (но Вы прежде решайте не вникая в истории
саму задачу 6.3, Вы найдете решение, оно будет лучше всех дру-
гих, потому что будет Ваше). Эта конструкция принадлежит изоб-
ретателю полимино Соломону Голомбу. Возьмите правильный шести-
угольник ABCDEF со стороной 1 и центром в точке O и правильный
треугольник XYZ тоже со стороной 1 и тем же центром O. Поверни-
те треугольник XYZ вокруг центра O так, чтобы точка X оказалась
на расстоянии 1 от точки A. Посмотрите на 10 точек OABCDEFXYZ.
Решений задачи 6.7 (возможных раскрасок) несколько. Найдите
свое решение или доведите до конца решение Ласло Шекели (1982
г., это не первое из решений). Идея его состоит в следующем. Я
буду "рисовать" используя то, что когда мы пишем электронные
письма в текстовом формате, а не html, у нас шрифт постоянной
ширины. Квадратик с диагональю (а не стороной) 1 я буду показы-
вать с помощью четырех одинаковых знаков, например:
XX
XX
Раскрасим полоску периодически повторяющимися квадратиками:
... 112233445566771122334455667711 ...
... 112233445566771122334455667711 ...
Снизу подложим такую же полоску, но сдвинутую вправо на рассто-
яние, кратное половине стороны квадратика (какое именно рассто-
яние нужно взять?), далее снизу тоже такую же полоску, но под-
ходящим образом сдвинутую, и так далее, чтобы картинка периоди-
чески повторялась по вертикали. Осталось только уточнить, как
сдвинуть, условиться, как красить точки границ квадратиков, и
провести проверку.
(С) С.И.Соболев, 1999-2002