Книга: Золотой билет

Раскраска домов

Раскраска домов

В Королевстве вышел новый закон: по причинам эстетического характера соседние дома должны быть выкрашены в разные цвета (независимо от того, дружат их хозяева или враждуют). Нововведение вызвало волну общественного протеста: жители не желали тратить свои кровные на краски и рабочих. В результате правительство согласилось оплатить все счета при условии, что оно само выберет цвета.

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

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

Когда в 1852 году английский (а впоследствии южноафриканский) математик Франсис Гатри раскрашивал карту графств Англии, ему пришло в голову, что любую карту можно раскрасить в четыре цвета таким образом, чтобы любые две смежные области получили разные цвета. Его гипотеза широко обсуждалась в математической среде; через некоторое время появились целых два доказательства: первое в 1879 году выдвинул Альфред Кемпе, второе – годом позже – Питер Тэт. Оба были опровергнуты, хотя второе продержалось одиннадцать лет, прежде чем в нем нашлись существенные изъяны. После этого проблема раскраски карт почти сто лет оставалась открытой.

Наконец, в 1976 году математики Кеннет Аппель и Вольфганг Хакен сумели доказать, что для правильной раскраски хватит четырех цветов. Правда, способ доказательства был довольно спорным: для проверки многочисленных примеров, на которых строились рассуждения, ученые использовали компьютер. Консервативно настроенные математики такой метод не приняли, поскольку не все его этапы можно было проверить вручную. Впрочем, формально доказательство Аппеля–Хакена так и не было опровергнуто, и сегодня уже мало кто сомневается в том, что любую карту действительно можно правильно раскрасить в четыре цвета.

А вдруг четыре – это не предел? Можно ли обойтись всего тремя цветами? Оказывается, нельзя, и сейчас мы с вами в этом убедимся. Давайте рассмотрим штат Невада и всех его соседей.

Неваду окружает кольцо из пяти штатов: Калифорния, Орегон, Айдахо, Юта и Аризона. Пять – число нечетное, поэтому для раскраски штатов кольца потребуется не менее трех цветов. Действительно, предположим, что цветов у нас всего два, к примеру – голубой и зеленый. Покрасим Калифорнию зеленым, соседний с ней Орегон – голубым, Айдахо – зеленым, и Юту – голубым. Осталась Аризона, которая граничит и с зеленой Калифорнией, и с голубой Ютой, так что мы не можем покрасить ее ни в зеленый цвет, ни в голубой. Следовательно, для раскраски всех пяти штатов кольца нужно как минимум три цвета. Пусть Аризона будет желтой.

Рис. 3.14. Невада и ее соседи

Невада имеет общие границы со всеми перечисленными штатами, а значит, мы не можем покрасить ее ни зеленым, ни голубым, ни желтым, и для правильной раскраски требуется четвертый цвет.

На базе доказательства теоремы о четырех красках были разработаны алгоритмы, позволявшие правильно раскрашивать карты четырьмя цветами за приемлемое время. Основываясь на этих алгоритмах, в институте создали такую схему раскраски, в которой любые два соседних дома получали разные цвета. Цветов было всего четыре, однако правительство потребовало сократить их число до трех. Доказать, что это невозможно, исследователи не сумели, поскольку на всей территории Королевства не нашлось ни одного дома, окруженного нечетным числом соседей. Отвертеться от задания не удалось.

Начались поиски решения. Через некоторое время, так и не добившись результата, исследователи вынуждены были признать, что они не в состоянии найти способ раскрасить дома в три цвета. Правительству пришлось закупать краски четырех цветов; с тех пор институту уже нечасто удавалось выбить себе грант.

Оглавление книги