Хроматическое число плоскости

Докажем сначала немного более слабые утверждения.

а) Покажем, что плоскость можно покрасить в 9 цветов так, чтобы выполнялось нужное условие.

Рис. 1. Возьмём квадрат со стороной 3a, разобьём его на 9 равных квадратов со стороной a и раскрасим их в 9 разных цветов

Для этого возьмём квадрат со стороной 3a (значение a мы выберем позже), разобьём его на 9 равных квадратов со стороной a и раскрасим эти 9 квадратов в 9 разных цветов. Теперь посмотрим, какое нужно выбрать a, чтобы при замощении всей плоскости так раскрашенными квадратами (см. рис. 1) любые две точки на расстоянии 1 см были разноцветными.

С одной стороны, внутри одноцветных квадратиков не должно быть точек на расстоянии 1 см. Для этого достаточно, чтобы диагональ квадрата, равная a√2, была меньше сантиметра, то есть должно выполняться неравенство a < 1/√2 = 0,707... . С другой стороны, между ближайшими квадратиками одного цвета расстояние должно быть больше сантиметра. Для этого должно выполняться неравенство 2a > 1, или a > 0,5. Значит, если взять сторону маленького квадратика равной, например, 0,6 см, мы получим требуемую раскраску плоскости в 9 цветов.

б) Докажем, что если цветов у нас всего два, то обязательно найдутся две точки одного цвета на расстоянии в 1 см друг от друга. Для этого достаточно взять три точки в вершинах правильного треугольника со стороной 1 см. По принципу Дирихле какие-то две из них имеют один цвет — они-то нам и нужны.

Для решения пункта а) можно покрыть плоскость более подходящими для этого многоугольниками, чем квадрат; можно обойтись и равными квадратами, но замостить ими плоскость немного по-другому.

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

а) Можно.
Разобьём плоскость на равные правильные шестиугольники со стороной a и раскрасим их в 7 цветов, как показано на рис. 2.

Рис. 2. Разобьём плоскость на равные правильные шестиугольники со стороной a и раскрасим их в 7 цветов. Рисунок из книги А. М. Райгородского «Хроматические числа»

Определим, чему должно быть равно a, чтобы раскраска удовлетворяла условию задачи. С одной стороны, внутри каждого одноцветного шестиугольника не должно быть двух точек на расстоянии 1. Самые далёкие друг от друга точки в шестиугольнике — на концах любой из главных диагоналей; длина этих диагоналей равна 2a, откуда получаем неравенство 2a < 1, или a < 0,5.

Рис. 3. Расстояние AB между ближайшими шестиугольниками одного цвета можно найти по теореме Пифагора из треугольника ABC

Расстояние AB (см. рис. 3) между ближайшими шестиугольниками одного цвета можно найти по теореме Пифагора из треугольника ABC: AC = 3a√3/2, BC = a/2, откуда AB² = AC² + BC² = 7a², и AB = a√7. Значит, второе ограничение на a имеет вид a√7 > 1, или a > 1/√7 = 0,378... Таким образом, взяв сторону шестиугольника равной, например, 0,4 см, мы получим правильную раскраску плоскости в 7 цветов. (Подумайте, почему два шестиугольника одного цвета в такой раскраске не могут оказаться ближе друг к другу, чем два красных шестиугольника на рис. 3.)

Есть и другие способы раскрасить плоскость в 7 цветов, чтобы соблюдались требуемые условия. Например, можно снова использовать равные квадраты, но каждый следующий их слой сдвигать относительно предыдущего на две с небольшим стороны квадрата (см. рис. 4). На рисунке сдвиг равен 2 ³/₇ x, где x — сторона квадрата; подойдёт и любое другое число, большее (1 + √2)x и меньшее 2,5x. Сторону квадрата можно выбрать, как и в Подсказке 1, такой, чтобы диагональ одного квадрата была чуть меньше 1 см. Проверьте, что при правильном выборе стороны квадрата одноцветных пар точек на расстоянии 1 см не возникнет.

Рис. 4. Можно раскрасить плоскость в 7 цветов, разбив ее на равные квадраты. Каждый следующий их слой надо сдвигать относительно предыдущего на две с небольшим стороны квадрата

б) Нельзя.
Предположим, что мы раскрасили плоскость в 3 цвета так, что любые две точки на расстоянии 1 см окрашены в разные цвета. Докажем сначала вспомогательное утверждение:

Лемма. В этом случае любые две точки на расстоянии √3 см друг от друга одноцветны.

Доказательство. Рассмотрим произвольный правильный треугольник ABC со стороной 1 см; все три его вершины окрашены в разные цвета. Пусть точка D симметрична A относительно прямой BC; тогда BCD — тоже правильный треугольник со стороной 1, его вершины также окрашены в разные цвета, а значит, цвет вершины D совпадает с цветом вершины A. Легко проверить, что длина отрезка AD составляет как раз √3 см.

Теперь остаётся совсем немного: для произвольной точки K нетрудно построить такие точки L и M, что KL = KM = √3 см, а LM = 1 см. Тогда точки L и M (на расстоянии 1 см друг от друга) по лемме будут того же цвета, что и точка K, то есть одноцветны — противоречие с предположением о правильности раскраски. Задача решена.

Начнём с самого интересного: ничего больше про минимальное число цветов, требующихся для раскраски плоскости с выполнением того же условия, не известно. Можно ли покрасить плоскость в 4, или в 5, или в 6 цветов — не знает никто, хотя известна эта задача уже больше 60 лет!

Относится она к теории графов. Графом называется произвольное множество точек, или вершин, некоторые из которых соединены с другими вершинами отрезками или дугами — обычно их называют рёбрами. Можно представлять себе граф, например, как компанию людей, некоторые из которых знакомы друг с другом; при этом если Надя знает Катю, то Катя знает Надю, то есть граф знакомств неориентированный, как, например, в сети ВКонтакте. (Бывают и ориентированные графы, как, например, граф друзей в Живом Журнале: там, если ты добавляешь кого-то в друзья, то сам не попадаешь к нему в список друзей, — но о них мы сейчас говорить не будем.)

Теория графов — достаточно старый раздел математики; её родоначальником считается Леонард Эйлер — один из величайших математиков в истории. Кстати, хотя родился он в Швейцарии, последние 17 лет жизни провёл в России и оказал большое влияние на становление науки в нашей стране.

Первой задачей теории графов считается задача о семи мостах Кёнигсберга (ныне Калининграда): жители пытались обойти семь мостов города так, чтобы ни по одному из них не пройти дважды, но сделать это никому не удавалось. Эйлер заинтересовался ей в 1736 году и в том же году нашёл правило, позволяющее определить возможность такого прохода для любой схемы мостов. По 7 мостам Кёнигсберга, как оказалось, нужным образом действительно пройти нельзя. На рис. 5 изображены эти 7 мостов на карте Кёнигсберга и соответствующий им граф.

Рис. 5. 7 мостов на карте Кёнигсберга (слева) и соответствующий им граф. Изображения из статьи Википедии «Проблема семи мостов Кёнигсберга»

(Рассказывают, что немецкий кайзер Вильгельм, славившийся своей прямотой, узнал об этой задаче на одном из приёмов и сказал, что если ему принесут лист бумаги и перо, то он решит её за полторы минуты. Учёные умы, предложившие ему эту задачу, быстро нашли перо и бумагу; а Кайзер написал на листе приказ построить восьмой мост, с которым задача действительно решается совсем легко. Верите или нет, но мост Кайзера действительно был построен.)

Назовём правильной раскраской графа такую раскраску его вершин в несколько цветов, что любые две вершины, соединённые ребром, раскрашены в разные цвета. Хроматическим числом графа G (обозначение: χ(G)) называется минимальное число n, при котором существует правильная раскраска графа в n цветов. Например, ясно, что хроматическое число каждого графа не меньше единицы (если в нём есть хотя бы одна вершина) и не больше числа вершин в графе — ведь можно каждую вершину покрасить в свой цвет.

Граф, с которым мы имеем дело в нашей задаче, имеет довольно страшный вид: его вершины — это все точки плоскости (это множество обычно обозначают ), а рёбрами соединены все пары вершин, отстоящие друг от друга на расстояние 1 см. Тем не менее, в задаче мы небезуспешно получали оценки на его хроматическое число, и в итоге несложными методами (правда, у математиков на то, чтобы их придумать, ушло 11 лет!) доказали, что 4 ≤ χ(G) ≤ 7. Задачу о нахождении хроматического числа плоскости математики называют обычно задачей Нельсона–Хадвигера (Hadwiger–Nelson problem) или задачей Эрдеша–Хадвигера. Впервые она была сформулирована, судя по всему, 18-летним Эдвардом Нельсоном в 1950 году; нижняя оценка χ(G) ≥ 4 была доказана в 1961 году братьями Мозерами, а верхняя χ(G) ≤ 7 — в том же 1961 году Хьюго Хадвигером. Подробный рассказ об этой задаче, путях её решения и разных обобщениях, в том числе на многомерные пространства, желающие смогут найти в уже упомянутой нами свободно распространяемой брошюре А. М. Райгородского «Хроматические числа».

Нам же интересно в первую очередь то, что ничего лучше, чем отрезок от 4 до 7, про хроматическое число плоскости не известно. А ведь на вид формулировка такая простая! Этой задачей за 60 лет занимались очень многие; например, известно, что если все одноцветные множества измеримы по Лебегу, то нужны по крайней мере 5 цветов, а если множества точек каждого отдельного цвета представляют собой объединение непересекающихся выпуклых многоугольников, то цветов нужно по крайней мере 6. Более того, не исключено, что точного ответа здесь не существует, как и в знаменитой континуум-гипотезе. В 2003 году Сойфер и Шелах привели доводы в пользу того, что ответ может зависеть от выбора аксиоматики теории множеств (статья на английском, PDF, 79 Кб).

Задача о хроматическом числе плоскости, несмотря на её на первый взгляд бесполезность для общества, вызвала развитие самых разных методов вокруг задач комбинаторной геометрии (см. Combinatorial geometry). А задачи раскраски графов получили самые разные непосредственные применения в нашей жизни: например, они помогают решать задачи составления расписаний (для образовательных учреждений и для транспорта), распределения регистров в микропроцессорах, распараллеливания численных методов, установки цифровых водяных знаков, решения судоку. Подробнее об этом можно прочитать, опять же, в Википедии (см. Практическое применение раскраски графов).

Задач, формулировка которых понятна и школьнику, а решение не известно никому, по-прежнему очень много. Если вы хотите оставить своё слово в истории, обратите внимание на эту ссылку: список открытых математических проблем. Вы удивитесь, на какие простые вопросы математики до сих пор продолжают искать ответ!