Математика для гуманитариев. Живые лекции

Как вы видите, каждые три ближайшие вершины закрашены разными цветами, как и должно быть по условию. Ведь расстояние между ними как раз равно 1. Обратите внимание, что третий ряд раскрасок совпадает с первым, четвертый со вторым, и т. д. до бесконечности. В данном случае (когда мы используем только три разных цвета) это не случайность — легко понять, что две вершины «через ребро» будут одноцветными (см. рис. 104). В самом деле, если разрешенных цветов только три, то для «отраженной» вершины просто нет выбора. Однако при любой попытке продолжить раскраску на ребра паркета (и далее на собственно плитки) нас постигнет неудача. Эта неудача не является случайной (из-за того или иного неверного подхода к этой задаче), а является следствием такой (уже доказанной) теоремы: Для правильного закрашивания плоскости заведомо не хватит трех красок. Доказано и полезное добавление к этой теореме: для успешного закрашивания заведомо хватит СЕМИ разных красок. Таким образом, в настоящее время известно следующее: минимальное количество красок для закрашивания плоскости равно либо 4, либо 5, либо 6, либо 7.

Эту теорему можно доказать вполне школьными вычислениями, и мы это сделаем — жалко было бы не познакомить вас с таким элегантным доказательством. (Его придумали братья Мозеры. Просто взяли и предъявили 7 конкретных точек на плоскости и доказали, что даже эти 7 точек НЕЛЬЗЯ закрасить тремя разными цветами. Значит, всю плоскость и подавно нельзя ими раскрасить. Эти семь точек образуют замысловатую конструкцию, похожую на два веретена, нижние концы которых соединены, а прочие два конца связаны веревочкой длины 1 (понятно, почему 1?). С тех пор в жаргоне математиков появилось звучное выражение «Веретено братьев Мозеров»).

Сейчас я покажу, что на самом деле нужно хотя бы 4 цвета.

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

Рис. 105. Веретено. Будем вращать его вокруг нижней точки «К».

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

Рис. 106. Веретено братьев Мозеров. Длина всех ребер равна 1. Конструкция содержит 7 вершин (точки кажущегося пересечения на оси симметрии вершинами не являются).

На рис. 106, строго говоря, ребра нам вообще не нужны, а нужны только 7 вершин. Ребра нарисованы только для лучшего понимания идеи доказательства. Раскрасим вершины правого веретена с помощью цветов К, С, 3 (мы предположили от противного, что тремя цветами можно правильно раскрасить вершины «двойного веретена») (см. рис. 105). Если нижняя вершина окрашена цветом «К», то и противоположная вершина левого веретена должна быть покрашена цветом «К». Так как горизонтальное верхнее ребро нарочно выбрано так, чтобы длина его была равна 1, то нарушается основное условие закраски. Теорема доказана от противного.

Человечество научилось красить плоскость в 7 цветов; ни в 6, ни в 5, ни в 4 оно красить плоскость не умеет и не знает, возможно ли такое.

Андрей Михайлович Райгородский, который очень любит эту проблему, считает, что возможно покрасить плоскость в 4 цвета. Но это пока никаким абсолютным доказательством, не подтверждено.

Рис. 107

Чтобы покрасить в 7 цветов, делается (рис. 107) 6-угольное замощение плоскости (шестиугольный паркет). Подбирается размер 6-угольника и предъявляется аккуратная раскраска.

С этой задачей связана еще одна проблема. Посмотрите на рис. 106 не как на схему соединения вершин «двойного веретена», а как на карту некоего 5-угольного острова, на котором расположились 9 различных государств (каждый связный кусочек, даже самый маленький, является государством). Стало быть, на географической карте этого острова каждое из государств надо было бы, по-хорошему, закрасить своим собственным цветом. Но государств на свете имеется ужасно много, а количество цветов, различаемое человеком, ограничено. Да и при изготовлении карты полиграфисты хотели бы иметь сильно ограниченный набор цветов (резко отличающихся друг от друга). Возникает чисто математический вопрос («проблема четырех красок»):

Можно ли любую карту на плоскости раскрасить в 4 цвета так, чтобы страны, имеющие общую границу ненулевой длины, были разных цветов? Или нужно 5 цветов? (То, что 3 цветов мало, довольно быстро показывается на примере.)

Вопрос: можно ли карту 5-угольного острова раскрасить 2; 3; 4 цветами? (см. рис. 106).