Athenaeum. Слухи о заметке пересекли Атлантику и дошли до США, где под колдовское обаяние гипотезы подпал философ Чарльз Пирс. Пирс заявил, что «со стороны логики и математики непростительное упущение, что такое простое утверждение до сих пор не доказано», и в конце 1860-х годов предложил собственное гипотетическое доказательство гарвардскому математическому обществу. Никаких сведений о нем не сохранилось. Однако впоследствии Пирс был вынужден признать верность доказательства, которое предоставил другой ученый, и поспособствовать его публикации в Nation в Рождество 1879 года. Тем самым Пирс невольно подтвердил истинность доказательства, которому предстояло стать самым знаменитым примером пагубного заблуждения в истории математики.
Здесь, пожалуй, уместно сказать несколько слов о том, как математики вообще относятся к доказательствам утверждений, особенно таких, которые, подобно проблеме четырех красок, охватывают бесконечное множество случаев. Один из методов доказательства называется математической индукцией. Иногда его сравнивают с тем, как падает бесконечный ряд косточек домино. Главное в методе математической индукции – показать, что если такое-то и такое-то утверждение верно для числа n, то тогда оно верно и для n+1. Аналогия с домино означает, что каждая падающая косточка сбивает следующую в очереди, и в конце концов упадут все. Чтобы применить математическую индукцию к проблеме четырех красок, нужно показать, что если каждая карта, на которой обозначено n областей, может быть раскрашена четырьмя красками, это возможно и для карты, на которой n+1 областей. Как выяснилось, это чудовищно трудно. Когда добавляешь на данную карту «эн-плюс-первую» область, иногда приходится перекрасить некоторые или все n остальных областей, чтобы новая область вписалась в четырехцветную схему. Общее правило такой перекраски никому сформулировать не удалось. Так что никакого падения доминошек.
К счастью, есть и другой подход к доказательству утверждения, охватывающего бесконечно много случаев: доказательство от противного. Берешь утверждение, противоположное тому, которое хочешь доказать, и доводишь его до абсурда. В случае проблемы четырех красок это означает, что мы предполагаем, что существуют контрпримеры, то есть карты, для которых нужно пять и более красок, а затем выводим из этого предположения противоречие. Поскольку подобные контрпримеры нарушают принцип четырех красок, их принято в обиходе называть «криминальными». Если криминальные карты существуют, в них может быть любое количество областей, но полезно сосредоточиться на тех, где областей абсолютный минимум. Такие карты называют «минимальными» криминальными картами. (Очевидно, чтобы потребовалось пять цветов, на минимальной криминальной карте должно быть не меньше пяти областей.) Любая карта с меньшим числом областей, чем минимальная криминальная, по определению законопослушна, то есть ее можно раскрасить в четыре цвета.
Мы оказались в занятном положении. Возьмем карту, которая может оказаться минимальной криминальной. Выберем любую область и сожмем ее в точку. Это уменьшит количество областей на одну. Теперь у редуцированной карты не хватает областей, чтобы считаться криминальной, поскольку у нее на одну область меньше, чем у минимальной криминальной карты, с которой мы начали. Следовательно, редуцированная карта законопослушна, а значит, ее можно раскрасить четырьмя красками. Раскрасим ее.
Теперь обратим процесс. Вернем на карту область, которую мы сжали в точку – раздуем эту область обратно. Теперь у нас есть первоначальная карта, на которой как следует раскрашены все области, кроме той, которую мы сжали, а потом восстановили. Зададимся вопросом: есть ли способ раскрасить восстановленную область так, чтобы она вписалась в четырехцветовую схему, которую мы применили к редуцированной карты? Это, конечно, зависит от того, какую область мы выбрали для сжатия и восстановления. Если, например, была выбрана область, граничащая только с тремя другими, вам повезло: когда вы ее восстановите, из четырехцветной схемы останется один цвет, который отличит восстановленную область от трех соседок. Но тогда вы смогли раскрасить исходную карту четырьмя красками. Значит, предполагаемая минимальная криминальная карта вовсе не была криминальной!
Тогда очевидно, что карта, претендующая на звание минимальной криминальной, не должна содержать областей, граничащих только с тремя другими областями. Иначе (1) можно сжать такую область в точку, таким образом снизив число областей на одну и сделав так, чтобы карта оказалась ниже минимально-криминального порога и, следовательно, оказалась законопослушной, (2) раскрасить редуцированную законопослушную карту четырьмя красками, (3) затем восстановить сжатую область, раздув ее снова, и (4) раскрасить восстановленную область одним из четырех цветов, не совпадающим с цветами ее трех соседок, тем самым включив восстановленную область в четырехцветную схему. И тогда исходная карта в конце концов оказывается законопослушной.
Если карта поддается этому процессу сжатия-раскрашивания-восстановления, говорят, что у нее «редуцируемая конфигурация». Как мы только что видели, один их типов редуцируемой конфигурации – это область, граничащая только с тремя другими областями. Увы, такая область найдется не на каждой карте. Но, вероятно, есть и другие типы редуцируемых конфигураций. И, вероятно, можно показать, что любая карта, какой бы сложной она ни была, обязательно содержит хотя бы одну редуцируемую конфигурацию. Если да, это решило бы вопрос. Карта, содержащая редуцируемую конфигурацию, не может быть минимальной криминальной, такая карта всегда может быть раскрашена в четыре цвета в результате процесса сжатия-раскрашивания-восстановления. Так что если любая карта содержит хотя бы одну разновидность редуцируемой конфигурации, значит, минимальных криминальных карт не бывает. А если не бывает минимальных криминальных карт, значит, криминальных карт не существует, и точка. (Если криминальные карты существуют, среди них должны быть карты с минимальным числом регионов.) А если не существует криминальных карт, значит, любая карта законопослушна, то есть может быть раскрашена в четыре цвета.
Именной этой логикой руководствовался и Альфред Брэй Кемп, лондонский адвокат и математик-любитель, который в 1879 году заявил, что доказал гипотезу четырех красок. Рассуждения Кемпа были полны математических хитростей, но показались убедительными, и не только Чарльзу Пирсу. Лучшие математики Британии, Континента и Соединенных Штатов признали, что перед ними долгожданное решение проблемы четырех красок. Кемпа приняли в Королевское общество, а затем и посвятили в рыцари. Его «доказательство» продержалось десять лет, пока в нем не обнаружили неочевидную, но фатальную ошибку. Нашел ее ученый-классик и математик Перси Хивуд, он же «Котик» Хивуд, как прозвали его друзья за роскошные усы.
Хивуд, который чуть ли не извинялся за то, что опроверг доказательство Кемпа, обладал некоторыми странностями характера, которые выделяют его даже среди героев этой саги, полной всевозможных чудаков и эксцентриков. Был он тощ и слегка сутул и, как правило, одевался в плащ с пелериной в необычных узорах и не расставался с древним саквояжем. Его повсюду сопровождала собака – даже на лекциях. Он любил заседать в ученых комитетах и считал, что день прошел зря, если он не поучаствовал хотя бы в одном заседании. Время на своих вечно отстававших часах он выставлял раз в год, в Рождество, а потом весь год подсчитывал в уме, какой нынче час. «Нет, они не на два часа спешат, а на десять часов отстают!» – уверял он коллегу. Однако были у него и практические таланты: когда Даремский замок XI века едва не сполз с утеса, на котором был построен, в реку Уир, Хивуд почти в одиночку собрал денег на его спасение.
А теперь еще одна математическая интерлюдия. Если доказать гипотезу четырех красок трудно, попробуем задачу попроще: так называемую гипотезу шести красок. Это аналог проблемы четырех красок, только, очевидно, слабее: гипотеза гласит, что для того, чтобы раскрасить любую возможную карту так, чтобы соседние области всегда были разного цвета, достаточно шести красок. Гипотеза шести красок достойна рассмотрения, поскольку выявляет математические корни проблемы четырех красок, восходящие к середине XVIII века и к великому швейцарскому математику Леонарду Эйлеру (чья фамилия на самом деле произносится «Ойлер»).
Эйлер, вероятно, был самым плодовитым математиком в истории. Среди открытий, которые он совершил, курсируя между дворами Фридриха II и Екатерины II, была формула V-E+F=2; недавно ее признали второй по красоте теоремой в математике. (Победителем конкурса красоты, по данным опроса 1988 года в журнале Mathematical Intelligencer, стало тождество e=-1)[16]). Формула Эйлера описывает любой многогранник, то есть любое тело, ограниченное плоскими поверхностями, вроде куба или пирамиды. Она гласит, что если сосчитать все вершины многогранника (V), вычесть количество ребер (E) и прибавить количество граней (F), в результате всегда получается 2. Например, у куба 8 вершин, 12 ребер и 6 граней. И в самом деле, 8-12+6=2.
Какое отношение многогранники имеют к картам? Если взять многогранник и после некоторых хирургических манипуляций развернуть его в плоскость, каждая грань будет похожа на область на карте. Напротив, из карты можно сшить многогранник. При этом формы и размеры областей изменятся, но это не повлияет на общую конфигурацию карты и на количество цветов, необходимых, чтобы ее раскрасить. Таким образом, проблема четырех цветов – это задача по топологии, отрасли математики, занимающейся свойствами, не меняющимися при растяжении и скручивании.
А теперь применим формулу Эйлера к карте. Тогда F – это число областей, E – число границ, а V – число точек пересечения этих границ. Теперь можно вывести результат, без которого невозможно подойти к проблеме раскрашивания: