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

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

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

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

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

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

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

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

а) Можно.

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

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

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

Расстояние (см. рис. 3) между ближайшими шестиугольниками одного цвета можно найти по теореме Пифагора из треугольника , , откуда , и . Значит, второе ограничение на a имеет вид , или Таким образом, взяв сторону шестиугольника равной, например, см, мы получим правильную раскраску плоскости в 7 цветов. (Подумайте, почему два шестиугольника одного цвета в такой раскраске не могут оказаться ближе друг к другу, чем два красных шестиугольника на рис. 3.)

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

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

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

б) Нельзя.

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


Теперь остаётся совсем немного: для произвольной точки нетрудно построить такие точки и , что см, а см. Тогда точки и (на расстоянии см друг от друга) по лемме будут того же цвета, что и точка , то есть одноцветны — противоречие с предположением о правильности раскраски. Задача решена.

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

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

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

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

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

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

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

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

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

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

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