Читать книгу "Величайшие математические задачи - Йен Стюарт"

Одним из пионеров топологии был Август Мёбиус, известный сегодня благодаря своей односторонней ленте (см. рис. 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}. Поскольку речь в задаче вроде бы шла о картах, издание показалось подходящим для публикации. Может быть, статью автору даже заказали. Но на самом деле выбор оказался не слишком удачным — ведь картографам решение этой задачи не нужно и не интересно, разве что из чистого любопытства. По той же причине, к несчастью, мало кто из математиков заметил эту статью, а жаль: в ней Кейли объяснил, почему задача может оказаться сложной.