Жемчужина Эйлера

— Иллинойс зеленый, а Индиана розовая. Ну-ка, покажи мне внизу что-нибудь розовое, если можешь. Нет, сэр, тут все зеленое.

— Гек Финн, да неужто ты воображаешь, что каждый штат в природе такого же цвета, как на карте?

— Том Сойер, для чего, по-твоему, существует карта? Ведь она сообщает нам о фактах?

— Разумеется.

— Ну, а как же она может сообщать нам о фактах, если она все врет?

— Марк Твен, «Том Сойер за границей»¹⁰⁹

Математик Чарльз Лютвидж Доджсон (1832–1898), больше известный как Льюис Кэрролл, автор «Алисы в Стране чудес», изобрел следующую игру для двух человек. Игрок A рисует карту континента с любым числом стран. Затем игрок B раскрашивает эту карту, так чтобы соседние страны (имеющие общую границу, касание в одной точке не считается) были выкрашены в разные цвета. Для A цель игры заключается в том, чтобы нарисовать как можно более сложную карту, вынудив B использовать много цветов. Наоборот, B должен раскрасить карту в наименьшее возможное число цветов.

Простую карту типа шахматной доски можно раскрасить всего в два цвета, но даже самый неумелый картограф сможет нарисовать карту, для которой нужно три цвета. Нетрудно также нарисовать карту, требующую четырех цветов, — нужно лишь сделать так, чтобы страну окружали ровно три другие страны (как Люксембург окружают Германия, Франция и Бельгия). Поскольку каждая из четырех стран граничит с тремя другими, необходимо четыре цвета (еще два примера дают Парагвай и Малави).

Во введении мы видели более тонкий случай, когда требуется четыре цвета. Столько необходимо для раскрашивания Невады, Калифорнии, Аризоны, Юты, Айдахо и Орегона, потому что Невада окружена нечетным числом стран (рис. 14.1). Оказывается, что Невада, Западная Вирджиния и Кентукки — единственные штаты США, для которых имеет место такая проблема. Правильно раскрасив эти штаты и их соседей, мы сможем распространить раскраску на все США, так что четвертый цвет придется использовать всего два раза.

Рис. 14.1. Карту США можно раскрасить в четыре цвета

Может ли A добиться большего? Может ли он заставить B использовать пять цветов? Как мы скоро узнаем, невозможно найти пять взаимно соседствующих стран (мы сразу запрещаем использовать «империалистические» страны, состоящие из неграничащих частей, как страна a на рис. 14.2). Достаточно ли этого, чтобы утверждать, что четырех цветов хватит для раскрашивания любой карты?

Рис. 14.2. При наличии разделенных на неграничащие части стран может понадобиться пять цветов

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

Насколько нам известно, впервые это было замечено в 1852 году. Фрэнсис Гатри (1831–1899), недавний выпускник математического факультета, увидел, что все английские графства можно раскрасить, используя всего четыре цвета, и задался вопросом, всегда ли это верно. Он сформулировал гипотезу, которая стала одной из самых трудных и широко известных проблем во всей математике: гипотезу четырех красок.

Гипотеза четырех красок

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

Фрэнсис Гатри рассказал о своем наблюдении брату Фредерику, который, в свою очередь, поделился со своим профессором, уважаемым математиком Огастесом де Морганом (1806–1871). Де Морган был заинтригован. 23 октября 1852 г. он написал сэру Уильяму Роуэну Гамильтону (1805–1865):