Германия, Франция и Бельгия). Поскольку каждая из четырех стран граничит с тремя другими, необходимо четыре цвета (еще два примера дают Парагвай и Малави).
Во введении мы видели более тонкий случай, когда требуется четыре цвета. Столько необходимо для раскрашивания Невады, Калифорнии, Аризоны, Юты, Айдахо и Орегона, потому что Невада окружена нечетным числом стран (рис. 14.1). Оказывается, что Невада, Западная Вирджиния и Кентукки — единственные штаты США, для которых имеет место такая проблема. Правильно раскрасив эти штаты и их соседей, мы сможем распространить раскраску на все США, так что четвертый цвет придется использовать всего два раза.
Рис. 14.1. Карту США можно раскрасить в четыре цвета
Может ли A добиться большего? Может ли он заставить B использовать пять цветов? Как мы скоро узнаем, невозможно найти пять взаимно соседствующих стран (мы сразу запрещаем использовать «империалистические» страны, состоящие из неграничащих частей, как страна a на рис. 14.2). Достаточно ли этого, чтобы утверждать, что четырех цветов хватит для раскрашивания любой карты?
Рис. 14.2. При наличии разделенных на неграничащие части стран может понадобиться пять цветов
Рассказывают, что именно картографы первыми заметили, что четырех цветов достаточно для раскрашивания любой карты. Правда, подтверждающих фактов нет. Если они об этом и знали, то нигде не опубликовали. Кеннетт О. Мэй проштудировал многочисленные книги по картографии и истории изготовления карт, но не нашел ни единого упоминания теоремы о четырех красках110. При внимательном изучении атласа выясняется, что большинство карт раскрашено либо в один, либо во много цветов. Нет даже намека на то, что картографы старались минимизировать число цветов.
Насколько нам известно, впервые это было замечено в 1852 году. Фрэнсис Гатри (1831–1899), недавний выпускник математического факультета, увидел, что все английские графства можно раскрасить, используя всего четыре цвета, и задался вопросом, всегда ли это верно. Он сформулировал гипотезу, которая стала одной из самых трудных и широко известных проблем во всей математике: гипотезу четырех красок.
Гипотеза четырех красок
Любую карту можно раскрасить в четыре или меньшее число цветов, так что никакие две соседние страны не будут окрашены в один цвет.
Фрэнсис Гатри рассказал о своем наблюдении брату Фредерику, который, в свою очередь, поделился со своим профессором, уважаемым математиком Огастесом де Морганом (1806–1871). Де Морган был заинтригован. 23 октября 1852 г. он написал сэру Уильяму Роуэну Гамильтону (1805–1865):
Мой студент попросил меня сегодня объяснить один факт, про который мне ничего не было известно — и я до сих пор не уверен, что это действительно так. Он говорит, что если некая фигура разделена на части любым способом и ее части раскрашены по-разному, так что фигуры с общей границей в виде линии окрашены в разные цвета, то для этого может потребоваться четыре краски, но не больше… Вопрос: нельзя ли придумать случай для пяти красок или больше?.. Что скажете? И был ли этот факт, если он и вправду имеет место, замечен ранее?.. Чем больше я об этом думаю, тем более очевидным мне это кажется. если вы приведете мне в ответ какой-нибудь очень простой пример, который выставит меня глупым животным, думаю, что я должен буду поступить, как поступил Сфинкс111.
К счастью для де Моргана, ему не пришлось бросаться со скалы, как сделал Сфинкс, когда Эдип разгадал его загадку. Гамильтон даже не заинтересовался его задачей. Он ответил: «Маловероятно, что я займусь Вашим “кватернионом красок” в ближайшем будущем»112.
Хотя де Морган пытался уговорить еще несколько человек подумать над проблемой, математическое сообщество упрямо отказывалось рассматривать ее. Почти двадцать лет в печати не появлялось ничего. Поворотной точкой в проблеме четырех красок стал день 13 июня 1878 года, когда на собрании Лондонского математического общества уважаемый математик Артур Кэли спросил, решена ли эта задача, и признался, что сам решить ее не смог. Вопрос был опубликован в записках общества и широко разошелся по миру113.
Эта задача стала любимым времяпрепровождением любителей математики с тех пор, как Кэли привлек к ней внимание. Красота вопроса в том, что он формулируется настолько просто, что доступен даже пониманию ребенка. Безусловно, это математическая проблема, но для нее не требуется знания арифметики, алгебры, тригонометрии или анализа. Кажется, что до доказательства рукой подать. Вот что писал знаменитый геометр Г. С. М. Кокстер (1907–2003):
Наверное, чуть ли не каждый математик испытал ночной восторг, когда ему казалось, что он нашел доказательство, но утром обнаруживал, что попал в аналогичную ловушку114.
Работая в Scientific American, Мартин Гарднер раз в несколько месяцев получал длинное доказательство гипотезы четырех красок (конечно, все неверные). Поэтому в 1975 году он включил ее в колонку, вышедшую в первоапрельском номере. В статье «Шесть сенсационных открытий, которые каким-то образом ускользнули от внимания публики» он упомянул шесть главных открытий 1974 году, в т. ч. контрпример к гипотезе о четырех красках. Надпись под картой 110 областей говорила всё: «Теорема о четырех красках разнесена в пух и прах»115. Но до многих читателей шутка не дошла. От простофиль, не понявших, что это розыгрыш, пришло больше тысячи откликов на статью, в которых содержалось свыше сотни раскрашенных копий «контрпримера».
Хотя сейчас мы приписываем постановку проблемы четырех красок Фрэнсису Гатри, во многих старых текстах эту честь отдают немецкому математику Августу Мёбиусу (1790–1868). Мёбиус, последователь Мартина Лютера, был тихим и замкнутым семьянином. Повзрослев, он редко путешествовал, но в бытность аспирантом посещал Лейпцигский университет, Гёттингенский университет (на протяжении двух семестров работал вместе с Гауссом), Университет в Галле, а затем вернулся в Лейпциг, где закончил работу над докторской диссертацией по астрономии. После этого периода частых переездов он предпочел остаться в своей любимой Саксонии. Несмотря на многократные предложения работы в других университетах, он сохранял верность Лейпцигу на протяжении всей оставшейся жизни.
В Лейпциге Мёбиус работал астрономом и стоял во главе тамошней обсерватории. Он любил математику и именно в математику, а не в астрономию, внес наиболее важный свой вклад. Больше всего он известен работами по барицентрическому исчислению, проективной и аффинной геометрии и основаниям топологии. Благодаря уединенному образу жизни и скрупулезному подходу к математике он создавал отличные работы, но это не делало его талантливым лектором. Поэтому на его занятия ходило очень мало платных студентов.
Ошибка атрибуции проистекает из истории, рассказанной одним из студентов Мёбиуса Ричардом Бальцером (1818–1887). Бальцер писал, что в 1840 г. Мёбиус поставил перед аудиторией проблему пяти
