Читать «Золотой билет» онлайн - страница 28

А вот для следующей схемы решения, как выяснилось, не существует.

Рис. 3.11. Передай скипетр – 2: решения нет

Новые правила выглядят проще. Поначалу детям даже кажется, что вторая игра легче, чем первая, однако при увеличении числа участников играть в нее становится намного сложнее. В 1857 году математик Уильям Роуэн Гамильтон изобрел головоломку «Икосиан», или «Путешествие по додекаэдру», в которой нужно было выполнить обход вершин правильного двенадцатигранника, или додекаэдра.

Рис. 3.12. «Путешествие по додекаэдру»

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

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

Рис. 3.13. Додекаэдр

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

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

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

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

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

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