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

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

22 июля 1976 г., спустя почти сто лет после ошибочного доказательства Кемпе, два исследователя из Иллинойского университета, Кеннет Аппель (1932–2013) и Вольфганг Хакен (родился в 1928 г.), объявили, что нашли неизбежное множество, содержащее 1936 приводимых конфигураций. К моменту появления своих двух статей в следующем году они сумели упростить работу, исключив избыточность и уменьшив количество до 1482121. (Они также добавили в одну из статей третьего автора, Джона Коха, за помощь в вычислениях.) Теорема о четырех красках наконец-то пала!

Теорема о четырех красках

Любую карту можно раскрасить четырьмя или меньшим количеством цветов.

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

Причина такого холодного приема заключалась в том, что после того как Аппель и Хакен подготовили конфигурации графов, что заняло семьсот страниц рукописного текста, они загрузили их в компьютер и запрограммировали его на проверку многих тысяч частных случаев. Работу компьютера даже нельзя было проверить вручную. Вычисления заняли шесть месяцев, свыше тысячи часов машинного времени, и результатом стала гора распечаток высотой 1,2 м. Хотя люди в основном верят, что доказательство правильно, большинство чистых математиков находят его неэлегантным, неудовлетворительным и неспортивным. Все равно, как если бы Эвел Нивель похвастался, что пересечет Большой Каньон на мотоцикле, а потом построил мост и переехал по нему. Быть может, такие чувства испытывают настоящие альпинисты при виде людей, использующих бутылочки с кислородом во время высокогорного восхождения.

Рис. 14.12. Кеннет Аппель и Вольфганг Хакен

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

Доказательство теоремы о четырех красках стало первым широко обсуждаемым доказательством, полученным с помощью компьютера. И вряд ли последним. Еще один дискуссионный пример — доказательство гипотезы Кеплера, полученное в 1998 году Томасом К. Хейлсом122. Хейлс доказал, что Кеплер был прав, утверждая, что самый эффективный способ упаковки шаров в ящик — гранецентрированная кубическая упаковка: как бакалейщики укладывают апельсины, а артиллеристы ядра. Хотя этот результат был опубликован в престижном журнале Annals of Mathematics, редакция тянула с публикацией несколько лет (статья вышла в 2005 году), и даже тогда редакторы оговорились, что не стали и не смогли бы проверить тысячи строк компьютерного кода.

За годы, прошедшие с момента опубликования Аппелем и Хакеном своего спорного доказательства, оно было подвергнуто независимой проверке. Другие математики нашли меньшие неизбежные множества приводимых конфигураций и более эффективные способы доказательства теоремы, но и по сей день все доказательства нуждаются в проверке на компьютере.

Пауль Эрдёш (1913–1996), знаменитый венгерский математик, известный своей эксцентричностью, говаривал о «Книге» — воображаемом томе, содержащем самые красивые и элегантные доказательства математических теорем. Сегодня дверь перед теоремой о четырех красках почти закрыта, но мы все еще ждем старомодной проверки с помощью карандаша и бумаги — пока что мы не видели доказательства, достойного войти в Книгу.

Приложения к главе

109. Twain (1894), 42–43.

110. May (1965).

111. Graves (1889), 423.

112. Там же.

113. Cayley (1878).

114. Quoted in Dudley (1992).

115. Gardner (1975b); Gardner (1988).

116. Baltzer (1885), цитируется по Coxeter (1959).

117. Там же.

118. Kempe (1879).

110. Quoted in Wilson (2002), 119.

120. Gardner (1995).

121. Appel and Haken (1977); Appel, Haken, and Koch (1977).

122. Hales (2005).

Глава 15

Новые проблемы и новые доказательства

Первые важные понятия топологии были открыты в процессе изучения многогранников.

— Анри Лебег 123

Допустим, вам задали вопрос: какие деревья меняют цвет и сбрасывают листья осенью? Сказав «клены», вы дали бы правильный ответ. Но всякий, кто ездил на машине по Пенсильванской глубинке в октябре, знает о раскрашенных в самые разные цвета дубах, березах и буках, возвышающихся посреди куч опавших листьев. Так что хотя ответ верный, он не содержит полного перечня таких деревьев. Можно ли сказать, что все деревья осенью меняют цвет? Нет. У сосен, елей и кедров нет листьев, им нечего сбрасывать. Чтобы высказать общее и при этом истинное утверждение, следует внимательно изучить различные деревья. Более полный ответ мог бы звучать так: листопадные деревья меняют цвет и сбрасывают листья осенью.

Для выпуклых многогранников имеет место соотношение V — E + F = 2. Это истинное утверждение. Мы знаем об этом из доказательств Эйлера, Лежандра, Коши и других. Однако мы знаем и то, что его можно усилить. Как заметил Пуансо, формула Эйлера справедлива не только для выпуклых многогранников, а, например, еще и для звездных. Математик Д. М. Я. Сомервилль (1879–1934) писал: «Выпуклость — это в какой-то мере акцидентальное свойство, выпуклый многогранник можно трансформировать, например путем сминания или вдавливания одной или нескольких вершин, в невыпуклый с точно такими конфигурационными характеристиками»124. Поэтому было бы неточностью и ненужным упрощением говорить, что только для выпуклых многогранников имеет место формула Эйлера. Эрнест де Жонкьер полагал, что, «ссылаясь на Лежандра и других высоких авторитетов, мы лишь способствуем широкому распространению предрассудка, от которого не свободны даже лучшие умы: будто теорема Эйлера верна только для выпуклых многогранников»125.

Можно ли зайти настолько далеко, чтобы утверждать, что все многогранники