Текст книги "Величайшие математические задачи"

4. Загадки картографии. Теорема о четырех красках

Многие великие задачи уходят корнями в глубокие и сложные вопросы давних и хорошо известных областей математики. Это те случаи, когда серьезные препятствия вдруг возникают уже после того, как эта область была тщательно изучена. Они, как правило, имеют технический характер, и все заинтересованные лица заранее знают, что они очень сложны, – еще бы, ведь многие специалисты пытались одолеть их и потерпели неудачу. При этом для соответствующей области часто уже разработаны множество мощных методик и объемный математический аппарат, которым может воспользоваться всякий подготовленный человек, но при этом, если задача до сих пор не решена, значит, все очевидные способы воспользоваться этими методиками уже испробованы и не сработали. Так что для решения этой задачи нужно либо использовать испытанные инструменты каким-то другим способом, либо изобретать новые.

Бывало и так, и этак.

Но существуют великие задачи, у которых все иначе. Они появляются из ниоткуда – небрежный чертеж на песке, заметка на полях книги, мимолетная причуда. Их формулировки просты, но поскольку вокруг них нет обширного математического фона, то нет и традиционных методов и подходов к ним. Иногда проходит много лет, прежде чем становится ясен уровень сложности задачи: кажется, что должен существовать какой-то хитрый, но несложный трюк, при помощи которого ее можно решить, и что решение не займет и полстранички. Задача о четырех красках относится именно к этой категории. Прошло не одно десятилетие, прежде чем математики начали осознавать, насколько она сложна. Мало того, большую часть этого времени все думали, что она уже решена, причем именно на нескольких страничках. Вообще, задача казалась второстепенной, и мало кто принимал ее всерьез, а когда это все же происходило, то в существовавшем вроде бы решении обнаруживались изъяны. Окончательное решение устранило все недостатки, но к тому моменту дискуссия стала настолько сложной, что пришлось привлекать на помощь мощные компьютеры.

В конечном итоге оба типа задач, несмотря на разное происхождение, схожи тем, что решение тех и других невозможно без новых подходов. Несмотря на то что задачи первого типа коренятся в хорошо изученных областях математики, традиционных методов для их решения не хватает. А задачи второго типа не принадлежат ни к одной известной области – более того, стимулируют возникновение новых, – и поэтому традиционных методов, которые можно было бы к ним применить, просто не существует. В обоих случаях решение задачи требует изобретения новых методов и установления новых связей с существующим массивом математических знаний.

Происхождение задачи о четырех красках известно, и оно – не математическое. В 1852 г. молодой южноафриканский математик и ботаник Фрэнсис Гутри, готовившийся к получению ученой степени по юриспруденции, попытался раскрасить графства на карте Англии. Он хотел быть уверенным, что любые два смежных графства можно будет раскрасить в разные цвета, чтобы границы между ними были хорошо различимы. Гутри выяснил, что для выполнения задачи ему будет достаточно четырех различных цветов, и после некоторого количества экспериментов убедил себя в том, что это заявление будет верным для абсолютно любой карты. Говоря о «смежных» графствах, он имел в виду, что эти графства имеют общую границу ненулевой длины; если же два графства соприкасались в точке или, к примеру, в нескольких изолированных точках, их можно было при необходимости раскрасить в один и тот же цвет. Без этой оговорки число цветов может быть бесконечным, поскольку в одной точке может встретиться неограниченное число регионов (см. рис. 8 слева).

Заинтересовавшись, не является ли его вывод известной математической теоремой, Гутри задал этот вопрос своему брату Фредерику, изучавшему в то время математику под руководством известного, но эксцентричного ученого Огастеса де Моргана в Университетском колледже Лондона. Де Морган не знал ответа на этот вопрос, поэтому написал еще более известному математику – ирландцу сэру Уильяму Гамильтону:

«Один мой студент [позже выяснилось, что это был Фредерик Гутри] попросил меня сегодня объяснить один факт, про который мне ничего не было известно, – и я до сих пор не уверен, что это действительно факт. Он говорит, что если некая фигура разделена на части любым способом и ее части раскрашены по-разному, так что фигуры с общей границей в виде линии любой длины окрашены в разные цвета, то для этого может потребоваться четыре краски, но не больше… Вопрос: нельзя ли придумать случай для пяти или более красок… Что скажете? И был ли этот факт, если это правда, замечен ранее?»

Фредерик позже упоминал некое «доказательство», предложенное его братом, но говорил также, что основной идеей там был рисунок, примерно соответствующий рис. 8, а он доказывает лишь, что меньше, чем четырьмя красками, не обойдешься.

Ответ Гамильтона был краток: «Я вряд ли займусь в ближайшее время вашим “кватернионом” красок». В то время Гамильтон работал над алгебраической системой, которой суждено было на всю жизнь стать его пунктиком и любимым коньком. Это система, аналогичная комплексным числам, но включающая четыре типа чисел вместо двух (действительные и мнимые) в комплексной системе. Свои числа он называл «кватернионами». Предложенная им система до сих пор сохраняет свое значение в математике. Мало того, сегодня ее роль, вероятно, более важна, чем во времена Гамильтона. Но высот, о которых мечтал автор, она так и не достигла. Гамильтон просто пошутил в академическом стиле, употребив слово «кватернион» по отношению к четырем краскам. Долгое время действительно казалось, что между его системой и задачей о четырех красках нет никакой связи. Однако задачу можно переформулировать так, что она становится утверждением о кватернионах, так что Гамильтон, сам того не желая, попал в яблочко.

Де Морган, потерпев неудачу в поиске доказательства, рассказал о задаче всем своим знакомым математикам в надежде на то, что кто-нибудь сможет предложить полезную идею. В конце 1860-х гг. американский логик, математик и философ Чарльз Пирс заявил, что нашел решение задачи о четырех красках, а также ответы на аналогичные вопросы о картах на более сложных поверхностях. Предполагаемое доказательство так и не было опубликовано, но вряд ли доступные ему методы были адекватны задаче.

Хотя в задаче о четырех красках говорится вроде бы о картах, сама она не имеет применения в картографии. Практика раскраски карт отражает в основном политические различия, и если при этом соседние регионы должны иметь один цвет, то их и красят одинаково. Смысл этой задачи лежит в области чистой математики – новой области, которая тогда только начала развиваться – топологии. Это «геометрия на резиновом листе», в которой фигуры можно непрерывно деформировать любым способом. Но даже там задача о четырех красках не укладывалась в основное русло исследований, а представлялась всего лишь диковинкой.

Одним из пионеров топологии был Август Мёбиус, известный сегодня благодаря своей односторонней ленте (см. рис. 9). Модель такой ленты несложно изготовить: для этого нужно взять полоску бумаги, свернуть ее в кольцо, похожее на короткий толстый цилиндр, повернуть один из концов на 180° и склеить концы. Однажды друг Мёбиуса лингвист Бенджамин Вейске загадал ему загадку: может ли индийский царь разделить свое царство на пятерых сыновей так, чтобы часть, принадлежащая одному принцу, имела границу ненулевой длины с частями всех остальных? Мёбиус задал эту загадку своим студентам в качестве упражнения, но на следующей лекции извинился за то, что попросил их сделать невозможное. Подразумевалось, что он может доказать невозможность ее решения{16}16
  Если границы могут быть по-настоящему сложными, не как на карте, а гораздо более извилистыми, то общую «границу» могут иметь сколько угодно стран. Этот неочевидный результат иллюстрирует конструкция, известная как «озера Вады».


[Закрыть].

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

Сеть – чрезвычайно простое понятие: набор вершин (они обозначаются точками), некоторые из которых связаны ребрами (обозначаются линиями). Возьмем произвольную карту (см. рис. 10 слева). Чтобы представить ее в виде сети, поставим в каждой области по точке (см. рис. 10 в середине). Там, где две области имеют общий участок границы, соединим соответствующие точки линией, проходящей через этот участок. Если две области имеют несколько общих участков границы, проведем через каждый по отдельной линии. Проделаем все это для всех областей и всех участков границы так, чтобы линии не пересекались друг с другом и не имели самопересечений, а встречались только в точках. Затем выбросим первоначальную карту и оставим себе только точки и линии. Это двойственная сеть – двойник нашей карты (см. рис. 10 справа).

Слово «двойственный» используется потому, что при этой процедуре области, линии и точки (пересечения областей) превращаются в точки, линии и области. Область на карте соответствует точке двойственной сети. Участок границы на карте соответствует линии двойственной сети; не той же самой линии, а линии, которая пересекает границу и связывает соответствующие точки. Точка, в которой на карте сходятся три или больше областей, соответствует области двойственной сети, ограниченной со всех сторон линиями. Так что двойственная сеть – сама по себе карта, поскольку линии здесь ограничивают области; кроме того, оказывается, что двойственной схемой к двойственной схеме является первоначальная карта плюс-минус кое-какие технические подробности, исключающие ненужные точки и линии.

Рассматривая двойственную сеть, задачу о пяти принцах можно сформулировать иначе: можно ли соединить пять точек на плоскости непересекающимися линиями? Ответ – нет, а ключ к нему – формула Эйлера, согласно которой, если карта на плоскости состоит из F участков (областей), E ребер (линий) и V узлов (точек), то F + V – E = 2. Здесь остальная плоскость, оставшаяся вне сети, считается одной большой областью. Эта формула в свое время стала первым указанием на то, что топологические вопросы достойны рассмотрения. Она вновь появится в главе 10.

Доказательство того, что задача о пяти принцах не имеет решения, начинается с предположения о том, что такое решение существует, и это приводит к противоречию. Любое решение должно иметь число точек V = 5. Поскольку каждая пара точек соединяется линиями, а точек у нас 10 пар, то E = 10. Тогда по теореме Эйлера F = E – V + 2 = 7. Области двойственной сети ограничены замкнутыми петлями линий, и каждую пару точек соединяет только одна линия, поэтому каждая из петель должна содержать по крайней мере три линии. Если областей семь, то линий получается по крайней мере 21… Правда, каждая из них считается дважды, поскольку разделяет две области. Так что линий по крайней мере 10,5. Число линий должно быть целым, значит, на практике у нас должно быть по крайней мере 11 линий. Однако мы уже знаем, что линий у нас 10. Это логическое противоречие доказывает, что такой сети не существует. Царь не сможет разделить свои земли так, как ему хочется.

В подобных рассуждениях обнадеживает то, что элегантные топологические методы позволяют нам доказывать интересные и неожиданные факты о картах. Однако, вопреки распространенному мнению, которое де Морган, судя по всему, разделял, невозможность решения задачи о пяти индийских принцах не доказывает теорему о четырех красках. Доказательство может быть неверным, даже если само умозаключение верно, или по крайней мере никому не известно о его неверности. Если где-то в предполагаемом доказательстве мне встретится треугольник с четырьмя сторонами, я прекращу читать, поскольку это доказательство неверно. При этом не имеет значения, что происходит в нем позже или какой из этого делается вывод. Наш ответ на загадку индийских принцев показывает лишь, что один из способов опровержения теоремы о четырех красках не работает. Однако из этого не следует, что не может работать какой-нибудь другой способ. В принципе, может существовать множество причин, по которым карту не удастся раскрасить в четыре цвета. Существование пяти областей, каждая из которых граничит со всеми остальными, лишь одна из этих потенциальных причин. Пока не доказано обратное, может существовать очень сложная карта, скажем, из 703 регионов, на которой, даже если вам удастся раскрасить в четыре цвета 702 из них, последний оставшийся все равно потребует пятой краски. Конечно, этот регион должен будет граничить по крайней мере с четырьмя другими, но это вполне представимо и не требует выполнения условий задачи о пяти принцах. Если бы подобная карта нашлась, она доказала бы, что четырех красок недостаточно. Любое доказательство должно исключить все подобные препятствия. И это утверждение сохраняет силу даже в том случае, если я не смогу продемонстрировать вам конкретный пример такой карты.

На какое-то время задача о четырех красках полностью пропала из виду, но в 1878 г. Артур Кейли упомянул ее на заседании Лондонского математического общества, и она вновь вызвала интерес. Несмотря на название, Общество это представляло всю британскую (или по крайней мере всю английскую) математику, а его основателем был де Морган. Кейли поинтересовался, удалось ли кому-нибудь получить решение этой задачи, и вскоре после заседания его вопрос был опубликован в журнале Nature. Годом позже он опубликовал обширную статью на эту тему в «Трудах Королевского географического общества»{17}17
  До недавнего времени статья в Nature считалась последней публикацией, посвященной этой проблеме, почти за 100 лет, но историк математики Робин Уилсон отыскал более позднюю статью Кейли.


[Закрыть]. Поскольку речь в задаче вроде бы шла о картах, издание показалось подходящим для публикации. Может быть, статью автору даже заказали. Но на самом деле выбор оказался не слишком удачным – ведь картографам решение этой задачи не нужно и не интересно, разве что из чистого любопытства. По той же причине, к несчастью, мало кто из математиков заметил эту статью, а жаль: в ней Кейли объяснил, почему задача может оказаться сложной.

В главе 1 я писал, что доказательство чем-то напоминает сражение. В военном деле четко различаются тактика и стратегия. Тактика – это искусство выигрывать локальные сражения, а стратегия определяет общую структуру кампании. Тактика определяет передвижение каждой войсковой части; стратегия формирует обширные планы, в рамках которых на каждой стадии возможны самые разные тактические решения. Статья Кейли не блистала тактическими находками, но содержала легчайший намек на стратегию, которая по прошествии времени позволила расколоть этот орешек и решить задачу о четырех красках. Кейли заметил, что добавление областей последовательно, по одной, ничего не дает, если следовать очевидному ходу рассуждений. Но, может быть, если найти другой, менее очевидный ход, из этого что-нибудь получится.

Предположим, мы возьмем произвольную карту и уберем оттуда одну область – сольем ее с соседней или сожмем в точку. Предположим также, что получившуюся карту можно раскрасить в четыре цвета, и мы так и сделаем. А теперь вернем удаленную область на место. Если нам повезет, ее соседи окажутся раскрашенными только в три цвета. Тогда нам останется всего лишь закрасить восстановленную область четвертым – свободным – цветом. Кейли указал, что эта процедура может и не сработать, поскольку соседи нашей области могут оказаться раскрашенными в четыре разных цвета. Но это не означает, что все плохо. Такое препятствие можно обойти двумя способами: сделать вывод либо о том, что мы выбрали не ту область, либо о том, что мы неверно раскрасили уменьшенную карту.

Действуя на основании ничем не подтвержденных предположений (это очень эффективный способ формирования рабочих идей, хотя в какой-то момент их все равно придется обосновать), считаем, что подобные препятствия всегда устранимы. Тогда получается, что любую карту можно раскрасить в четыре цвета, если известно, что некую меньшую карту можно так раскрасить. Может показаться, что такой вывод ничего нам не дает: как мы узнаем, что какую-то меньшую карту можно раскрасить нужным образом? Ответ в том, что эту же процедуру можно применить к меньшей карте, а затем к еще меньшей карте… и т. д. В конце концов, мы доберемся до карты настолько маленькой, что в ней будет всего четыре области, и это гарантирует, что ее можно раскрасить в четыре цвета. Теперь пройдем тот же путь в обратном направлении, на каждом шагу раскрашивая карту чуть побольше, чем в прошлый раз, и, в конце концов, доберемся до первоначальной карты.

Подобные рассуждения называют «доказательством по индукции». Это стандартный метод доказательства наиболее формализованных формулировок, и логику, на которой он основан, можно сделать строгой. Предложенная Кейли стратегия доказательства становится более понятной, если переформулировать ее с использованием логически эквивалентной концепции минимального контрпримера. В данном контексте контрпримером можно считать любую гипотетическую карту, которую невозможно раскрасить в четыре краски. Такая карта будет минимальной, если любую меньшую карту (т. е. карту с меньшим числом областей) можно раскрасить нужным образом. Если хотя бы один контрпример существует, то должен существовать и минимальный контрпример: чтобы его найти, нужно просто взять контрпример с минимальным возможным числом областей. Поэтому если минимального контрпримера не существует, то контрпримеров не существует вообще. А если их нет, то теорема о четырех красках верна.

Доказательство по индукции сводится примерно к следующему. Предположим, мы можем доказать, что минимальный контрпример всегда можно раскрасить в четыре краски, если можно раскрасить так некую связанную с ним меньшую карту. Тогда минимальный контрпример не может считаться собственно контрпримером. Поскольку эта карта минимальна, все меньшие карты можно раскрасить в четыре краски, поэтому, исходя из утверждения, которое, согласно принятому нами предположению, может быть доказано, то же верно в отношении первоначальной карты. Следовательно, минимального контрпримера не существует, а значит, не существует контрпримеров вообще. Эта идея сдвигает фокус проблемы, позволяя рассматривать не все карты сразу, а только гипотетические минимальные контрпримеры, и определяет процедуру редукции – способ последовательно вывести четырехкрасочность первоначальной карты из четырехкрасочности некой соответствующей меньшей карты.

Но зачем возиться с минимальными контрпримерами, не лучше ли поискать обычные? Это вопрос методики. Хотя первоначально мы не знаем, существуют ли контрпримеры, одно из парадоксальных, но очень полезных свойств этой стратегии заключается в том, что мы можем многое сказать о том, как должны выглядеть именно минимальные контрпримеры, если они существуют.

Для этого необходима способность рассуждать логически о гипотетических вещах – жизненно важное умение для любого математика. Чтобы дать вам почувствовать характер процесса, я докажу теорему о шести красках. Для этого мы позаимствуем прием из загадки о пяти принцах и переформулируем все в терминах двойственной сети, в которой области становятся точками. В этом случае задача о четырех красках эквивалентна другому вопросу: если на плоскости задана сеть, линии которой не пересекаются, можно ли раскрасить в четыре цвета точки так, чтобы две точки, соединенные линией, всегда были разного цвета? Точно так же можно переформулировать задачу с любым количеством красок.

Чтобы проиллюстрировать мощь метода минимальных контрпримеров, я докажу с их помощью, что любую плоскую сеть можно раскрасить в шесть цветов. Здесь главным нашим инструментом вновь станет формула Эйлера. Для точки плоской двойственной сети соседними точками назовем те, что соединены с ней линиями. У каждой точки может быть и множество соседей, и всего несколько. Можно показать, что, в соответствии с формулой Эйлера, у некоторых точек должно быть мало соседей. Точнее говоря, в плоской сети все точки не могут иметь по шесть и больше соседей. Доказательство этого момента я поместил в примечание, чтобы не прерывать ход мысли{18}18
  При работе в двойственной сети пусть F – число граней (включая одну большую грань, окружающую сеть целиком), E – число ребер, а V – число вершин. Можно считать, что каждая грань двойственной сети имеет по крайней мере три ребра – ведь если в ней есть грань только с двумя ребрами, то она соответствует «лишней» вершине первоначальной сети, в которой встречаются всего два ребра. Такую вершину можно удалить, а два ребра объединить в одно.
  Каждое ребро граничит с двумя гранями, и каждая грань имеет по крайней мере три ребра, потому E ≥ 3F/2 или, что то же самое, 2E/3 ≥ F. Согласно уравнению Эйлера, F + V – E = 2, так что 2E/3 + V – E ≥ 2. Из этого следует, что 12 + 2E ≤ 6V.
  Пусть V_m – это число вершин с m соседями. Тогда V = V₆ + V₇ + V₈ + …
  Поскольку каждое ребро соединяет две вершины:
2E = 6V6 + 7V7 + 8V6 + …  Подставив в неравенство, получаем:
12 + 6V6 + 7V7 + 8V8 + … ≤ 6V6 + 6V7 + 6V8 + …,  так что 12 + V₇ + 2V₈ + … ≤ 0,
  что невозможно.


[Закрыть]. Этот факт дает нам рычаг, необходимый для того, чтобы разбить задачу на более мелкие подзадачи. Рассмотрим гипотетический минимальный контрпример для теоремы о шести красках. Это сеть, которую невозможно раскрасить в шесть разных цветов, притом что любую меньшую сеть так раскрасить можно. А теперь я доказываю, что такая карта не может существовать. Согласно приведенному выше следствию из формулы Эйлера, в ней должна быть хотя бы одна точка, у которой пять или меньше соседей. Временно уберем эту точку и линии, соединяющие ее с соседями. В получившейся сети меньше точек, поэтому, исходя из минимальности контрпримера, ее можно раскрасить в шесть цветов. (Этот шаг, кстати говоря, мы не сможем сделать, если наш контрпример будет не минимальным.) А теперь вернем удаленную точку и ее линии на место. Эта точка имеет не более пяти соседей, так что шестой цвет для нее всегда найдется. Покрасим ее – и получим успешно раскрашенный в шесть цветов минимальный контрпример; но тогда получается, что это никакой не контрпример. Значит, минимальных контрпримеров для теоремы о шести красках не существует, а значит, теорема верна.

Это внушает оптимизм. До сих пор, насколько нам известно, для раскраски некоторых карт могло потребоваться 20 цветов, или 703, или несколько миллионов. Теперь мы знаем, что такие карты не более реальны, чем горшок золота под концом радуги. Мы знаем, что конкретного ограниченного числа красок точно хватит на любую карту. Это настоящий триумф метода минимальных контрпримеров. Математики, посмотрев на него, взялись за дело с еще большим энтузиазмом, надеясь усилить аргументацию и постепенно заменить шесть красок на пять, а если повезет, и на четыре.

Юристы иногда тоже интересуются математическими задачами. Адвокат по имени Альфред Кемпе присутствовал на том заседании, где Кейли упомянул задачу о четырех красках. В свое время он под руководством Кейли изучал математику в Кембридже, и за годы его интерес к этой науке нисколько не ослаб. Не прошло и года после заседания, а Кемпе уже убедил себя, что ему удалось справиться с задачей. Свое решение он опубликовал в 1879 г. в недавно основанном журнале American Journal of Mathematics. Еще через год он опубликовал упрощенное доказательство, где были исправлены некоторые ошибки, присутствовавшие в первом. Вот как он подошел к вопросу: «Очень небольшое изменение в части карты может привести к необходимости перекрашивать ее целиком. В результате достаточно сложного поиска мне удалось отыскать слабое звено, которое позволило одержать победу».

Я изложу идеи Кемпе в терминах двойственной сети. Опять же он начал с формулы Эйлера и следующего из нее вывода о существовании точки с тремя, четырьмя или пятью соседями. (Точка с двумя соседями лежит на линии и никак не влияет на структуру сети или карты: на нее можно просто не обращать внимания.)

Если существует точка с тремя соседями, то процедуру, которую я использовал для доказательства теоремы о шести красках, можно применить и к четырехкрасочному варианту. Удаляем саму точку и линии, которые в ней сходятся, раскрашиваем в четыре краски результат, возвращаем точку и линии на место и окрашиваем ее в оставшийся свободным цвет. Поэтому мы можем считать, что точки с тремя соседями не существует.

Если существует точка с четырьмя соседями, то вышеописанная методика не срабатывает, потому что при возвращении точки свободного цвета может и не оказаться. Кемпе придумал хитрый способ обойти это препятствие: он предложил так же точно удалить точку, но после этого поменять расцветку получившейся меньшей карты так, чтобы два из четырех ее бывших соседей получили один и тот же цвет. После такой модификации у соседей удаленной точки окажется не больше трех цветов – и в нашем распоряжении окажется свободный четвертый. Основная идея перекраски схемы по Кемпе заключается в том, что две соседние точки должны быть разных цветов – скажем, синего и красного, а еще в схеме используются зеленый и желтый. Если обе оставшиеся точки окажутся зелеными или желтыми, то второй цвет окажется свободным и может быть использован для удаленной точки. Исходя из этого, считаем, что одна из них зеленая, а вторая – желтая. Теперь найдем все точки, которые соединены с синей точкой последовательностью линий, проходящих только через синие и красные точки, и назовем их красно-синей цепочкой Кемпе{19}19
  Термин «цепочка» здесь неточен, потому что предполагает линейную последовательность. Цепочка Кемпе может содержать петли и разветвляться.


[Закрыть]. По определению, любой сосед любой точки в цепочке Кемпе, не принадлежащий цепочке, должен быть зеленым или желтым, поскольку синий или красный сосед там уже есть. Обратите внимание, что замена цветов в пределах цепочки Кемпе (синий на красный, и наоборот) дает новый вариант карты, в которой по-прежнему выполняется ключевое условие о том, что соседние точки должны быть разных цветов (см. рис. 11).

Если красный сосед нашей точки не является частью выделенной сине-красной цепочки, проведите такую замену. Синий сосед точки сделается красным, а красный останется красным по-прежнему. Теперь соседи нашей точки окрашены не более чем в три цвета: красный, зеленый и желтый, что позволяет нам окрасить точку в синий цвет – и дело сделано. Однако сине-красная цепочка может описать петлю и замкнуться на синем соседе нашей точки. Если так, оставьте в покое синий и красный цвета и проделайте ту же операцию с ее желтыми и зелеными соседями. Начните с зеленой точки и сформируйте желто-зеленую цепочку Кемпе. Заметьте: она не сможет замкнуться на желтого соседа, поскольку на ее пути непременно встретится предыдущая красно-синяя цепочка. Поменяйте желтый и зеленый цвета в цепочке местами, и дело сделано.

Остается последний случай: когда не существует точек с тремя или четырьмя соседями, но по крайней мере одна точка имеет пять соседей. Кемпе предложил аналогичное, но более сложное правило перекраски точек, которое, на первый взгляд, успешно решало и эту проблему. Вывод: теорема о четырех красках верна, и доказал ее Кемпе. Эта заявление попало даже в средства массовой информации: американский журнал The Nation упомянул решение Кемпе в своем обзоре.

Казалось, с проблемой четырех красок было покончено, и математики в большинстве своем с этим согласились. Правда, Питер Тэт продолжал поиски более простого решения и время от времени публиковал статьи на эту тему. Исследования привели его к нескольким полезным открытиям, но простое доказательство по-прежнему не давалось.

И тут на сцене появляется преподаватель математики из Университета Дарема Перси Хивуд, прозванный за свои великолепные ухоженные усы «Котом». Еще студентом в Оксфорде он услышал от профессора геометрии Генри Смита о теореме о четырех красках. Смит сказал ему, что теорема эта, хотя, вероятно, и верна, но не доказана, так что у Хивуда есть шанс. Кроме того, как-то он наткнулся на статью Кемпе и попытался ее понять. Результат своих размышлений Хивуд опубликовал в 1889 г. под названием «Теорема о раскраске карты», высказав при этом сожаление, что цель его статьи более «деструктивна, чем конструктивна, ибо в ней будет показано, что в признанном, кажется, на сегодня доказательстве есть дефект». Кемпе допустил ошибку.

Ошибка была достаточно тонкой и возникала в схеме перекраски в том случае, когда у удаляемой точки было пять соседей. В некоторых случаях изменение цвета одной точки (по схеме Кемпе) могло повлечь за собой невозможность дальнейших изменений. При этом Кемпе считал, что если какая-то точка меняет цвет, то происходит это лишь один раз. Хивуд же нашел карту (или сеть), в которой схема перекраски по Кемпе не срабатывала, и тем самым опроверг его доказательство. Кемпе, узнав об этом, без промедления признал ошибку и добавил, что ему «не удалось исправить этот дефект». Теорема о четырех красках вновь ждала желающих помериться с ней силой.

Хивуд отыскал в этой истории небольшое утешение для Кемпе: его метод успешно доказывал теорему о пяти красках. Кроме того, Хивуд работал еще над двумя обобщенными вариантами задачи: над вариантом с империями, где области могли состоять из нескольких несвязанных кусков, которые все требовали одного цвета, и над картами на более сложных поверхностях. Аналогичная задача на сфере решается точно так же, как на плоскости. Представьте себе карту на сфере, причем разверните сферу так, чтобы Северный полюс оказался внутри одной из областей. Теперь, если удалить точку полюса, то сферу с отверстием можно развернуть в поверхность, топологически эквивалентную бесконечной плоскости. Регион, в котором находился полюс, развернется в бесконечное пространство, окружающее карту. Однако, помимо сферы, существуют и другие, более интересные поверхности. Среди них тор, напоминающий по форме бублик с дыркой (см. рис. 12 слева).

Существует полезный способ визуализации тора, часто упрощающий математикам жизнь. Если разрезать тор вдоль двух замкнутых кривых (см. рис. 12 в середине), то можно развернуть его поверхность так, чтобы получился квадрат (см. рис. 12 справа). Такая трансформация меняет топологию тора, но эту сложность можно обойти, если объявить противоположные стороны получившегося квадрата тождественными. В результате (а строгое определение позволяет точно сформулировать принцип) мы договариваемся считать, что соответствующие точки на этих сторонах совпадают. Чтобы представить, почему так, посмотрите на рисунки в обратном порядке. Мы скатываем квадрат в трубочку, и противоположные его стороны действительно склеиваются, затем сгибаем трубочку в кольцо и соединяем концы. Готово. А теперь самое интересное. Не обязательно на самом деле скручивать квадрат в трубочку и соединять соответствующие стороны. Можно работать с плоским квадратом, достаточно просто помнить о том, что его противоположные стороны – это одно и то же. Всему, что мы будем делать на торе, включая и рисование кривых, имеется точное соответствие на квадрате. Хивуд доказал, что для раскрашивания любой карты на торе необходимо и достаточно семи красок. Рис. 13 (слева) показывает, что семь цветов необходимо; при этом квадрат, как уже говорилось, представляет поверхность тора. Обратите внимание, как сходятся участки на противоположных сторонах квадрата. Существуют поверхности, подобные тору, но имеющие больше отверстий (см. пример на рис. 13 справа). Число отверстий в такой фигуре называется родом и обозначается буквой g (genus – род). Хивуд придумал формулу для числа красок, необходимых для карты на торе с g отверстиями, если g ≥ 1: это наибольшее целое число, меньшее или равное