Однако задачу можно переформулировать так, что она становится утверждением о кватернионах, так что Гамильтон, сам того не желая, попал в яблочко.
Де Морган, потерпев неудачу в поиске доказательства, рассказал о задаче всем своим знакомым математикам в надежде на то, что кто-нибудь сможет предложить полезную идею. В конце 1860-х гг. американский логик, математик и философ Чарльз Пирс заявил, что нашел решение задачи о четырех красках, а также ответы на аналогичные вопросы о картах на более сложных поверхностях. Предполагаемое доказательство так и не было опубликовано, но вряд ли доступные ему методы были адекватны задаче.
Хотя в задаче о четырех красках говорится вроде бы о картах, сама она не имеет применения в картографии. Практика раскраски карт отражает в основном политические различия, и если при этом соседние регионы должны иметь один цвет, то их и красят одинаково. Смысл этой задачи лежит в области чистой математики — новой области, которая тогда только начала развиваться — топологии. Это «геометрия на резиновом листе», в которой фигуры можно непрерывно деформировать любым способом. Но даже там задача о четырех красках не укладывалась в основное русло исследований, а представлялась всего лишь диковинкой.
Одним из пионеров топологии был Август Мёбиус, известный сегодня благодаря своей односторонней ленте (см. рис. 9). Модель такой ленты несложно изготовить: для этого нужно взять полоску бумаги, свернуть ее в кольцо, похожее на короткий толстый цилиндр, повернуть один из концов на 180° и склеить концы. Однажды друг Мёбиуса лингвист Бенджамин Вейске загадал ему загадку: может ли индийский царь разделить свое царство на пятерых сыновей так, чтобы часть, принадлежащая одному принцу, имела границу ненулевой длины с частями всех остальных? Мёбиус задал эту загадку своим студентам в качестве упражнения, но на следующей лекции извинился за то, что попросил их сделать невозможное. Подразумевалось, что он может доказать невозможность ее решения{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}. Поскольку речь в задаче вроде бы шла о картах, издание показалось подходящим для публикации. Может быть, статью автору даже заказали. Но на самом деле выбор оказался не слишком удачным — ведь картографам решение этой задачи не нужно и не интересно, разве что из чистого любопытства. По той же причине, к несчастью, мало кто из математиков заметил эту статью, а жаль: в ней Кейли объяснил, почему задача может оказаться сложной.
В главе 1 я писал, что доказательство чем-то напоминает сражение. В военном деле четко различаются тактика и стратегия. Тактика — это искусство выигрывать локальные сражения, а стратегия определяет общую структуру кампании. Тактика определяет передвижение каждой войсковой части; стратегия формирует обширные планы, в рамках которых на каждой стадии возможны самые разные тактические решения. Статья Кейли не блистала тактическими находками, но содержала легчайший намек на стратегию, которая по прошествии времени позволила расколоть этот орешек и решить задачу о четырех красках. Кейли заметил, что добавление областей последовательно, по одной, ничего не дает, если следовать очевидному ходу рассуждений. Но, может быть, если найти другой, менее очевидный ход, из этого что-нибудь получится.
Предположим, мы возьмем произвольную карту и уберем оттуда одну область — сольем ее с соседней или сожмем в точку. Предположим также, что получившуюся карту можно раскрасить в четыре цвета, и мы так и сделаем. А теперь вернем удаленную область на место. Если нам повезет, ее соседи окажутся раскрашенными только в три цвета. Тогда нам останется всего лишь закрасить восстановленную область четвертым — свободным — цветом. Кейли указал, что эта процедура может и не сработать, поскольку соседи нашей области могут оказаться раскрашенными в четыре разных цвета. Но это не означает, что все плохо. Такое препятствие можно обойти двумя способами: сделать вывод либо о том, что мы выбрали не ту область, либо о том, что мы неверно раскрасили уменьшенную карту.