Рис. 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. Но до многих читателей шутка не дошла. От простофиль, не понявших, что это розыгрыш, пришло больше тысячи откликов на статью, в которых содержалось свыше сотни раскрашенных копий «контрпримера».