Можно ли раскрасить плоскость в два цвета красиво
— то есть так, чтобы любые две точки на расстоянии 1 были разного цвета?
Вообразим, что можно: плоскость удалось раскрасить в два цвета красиво.
Положим на нее правильный треугольник со стороной 1. Все его три вершины не могут быть разноцветными (вершин три, а цветов всего два), значит, есть две вершины одного цвета, а расстояние между ними 1 — вот мы и нашли изъян в раскраске. Итак, в два цвета плоскость раскрасить красиво нельзя.
А в три? В четыре? В пять? .... Чтобы не ставить бесконечно много вопросов, обобщим их в один:
В какое наименьшее число цветов можно раскрасить плоскость красиво?
История
Эдвард Нельсон сообщил А.Сойферу, что именно он пришел к формулировке задачи, и рассказал как именно. Он набрел на эту задачу, пытаясь доказать знаменитую гипотезу о четырех красках. Вот она:
Имеется карта мира, в которой отмечены страны и границы между ними. Требуется ее раскрасить так, чтобы соседние страны были окрашены в разные цвета. Соседними считаются страны, у которых есть некоторый общий участок границы (не точка, а линия). Гипотеза в том, что для любой карты достаточно четырех красок.
Хотя гипотеза была выдвинута еще в середине XIX века, решить ее удалось только в 1976 году В.Хакену и К.Аппелю, они выполнили огромный перебор на компьютере. Научное сообщество тогда еще долго спорило — это настоящее доказательство или нет. В целом эти споры уже утихли, хотя до сих пор нельзя сказать, что такие методы решения считаются общепринятыми. Такое компьютерное решение не породило новых идей, понятий или теорий в комбинаторной геометрии, зато заставило задуматься о природе математического доказательства, о том, что это такое. Ну и выяснилось, что единой точки зрения у математиков на этот вопрос нет.
Задачу о раскраске карты можно поставить иначе, в терминах графов. Каждую страну обозначим точкой — вершиной графа. Если у двух стран есть общая граница, то соответствующие вершины графа соединяют ребром. Задача теперь состоит в том, чтобы раскрасить вершины графа так, чтобы вершины, соединенные ребром, были раскрашены в разные цвета. Сколько красок потребуется для раскраски такого графа? Вот что писал Эдвард Нельсон профессору Сойферу:
«Такие графы можно изобразить как узлы, соединенные проволочками. Я задался вопросом, нельзя ли представить достаточно богатый класс таких подграфов подграфы одного большого графа, который можно раскрасить раз и навсегда — например, графа всех точек плоскости, находящихся на расстоянии 1 друг от друга (тогда «проволочки» становятся жесткими, прямыми, одинаковой длины, но могут пересекаться). Эта идея не осуществилась, однако новая задача представляла самостоятельный интерес, и я сообщил о ней нескольким людям.»
Новую свою задачу Эдвард Нельсон назвал «второй задачей о четырех красках». Он рассчитывал, что если ее решить, то удастся продвинуться в решении первой задачи. Вышло все наоборот. Первую задачу уже решили, а со второй все еще есть трудности.
Сформулируем ее так:
Найти хроматическое число плоскости.
Хроматическое число плоскости — это наименьшее число цветов, в которые можно раскрасить все точки плоскости так, чтобы расстояние между точками одного цвета не могло оказаться равным 1.
Какие есть достижения?
Несложно (хотя и совсем неочевидно) доказать, что хроматическое число плоскости не больше 7. Для этого нужно раскрасить ее в 7 цветов красиво — то есть так, чтобы на расстоянии 1 не было одноцветных точек.
Как же указать раскраску всей плоскости, она же бесконечна? Удобно раскрасить кусочек, а потом указать, как одинаковыми кусочками замостить плоскость. Хадвигер предложил решение, в котором кусочком служил цветик-семицветик, составленный из 7 правильных шестиугольников:
Можно так подобрать сторону шестиугольника, что при такой раскраске расстояние между одноцветными точками никогда не будет равно 1. Такое замощение показывает, что хроматическое число плоскости не больше семи — это верхняя оценка.
Что касается нижней оценки, то вот система из 10 точек:
Раскрасить эти точки в три цвета красиво не получится, это можно проверить небольшим перебором.
Самые простые рассуждения привели нас к тому, что хроматическое число плоскости лежит где-то между 4 и 7. Полвека эту оценку улучшить не удавалось. В апреле 2018 года британский математик-любитель (по профессии геронтолог) совершил прорыв — предъявил еще более сложную конструкцию, граф с единичными расстояниями между вершинами, который нельзя раскрасить в 4 краски.
А это значит, что хроматическое число плоскости больше 4.
Задачка. На этом рисунке длины всех проведенных отрезков равны 1. Каким наименьшим числом красок можно раскрасить выделенные точки, чтобы соединенные отрезком обязательно были разных цветов? Иначе говоря, каким наименьшим числом красок можно раскрасить этот граф?