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

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

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

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

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

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

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

На первый-второй рассчитайсь!

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

Рис. 3.15. Младшеклассники

Наилучшим решением будет поместить Алекса и Кэти в одну группу, а Барбару, Дэвида и Эрика – в другую: так мы разорвем всего две дружеские связи, Алекс-Эрик и Кэти-Эрик. Очевидно, что разбиения, которое разлучило бы лишь одну пару друзей, просто не существует.

Рис. 3.16. Группы младшеклассников

Директор школы обратился за помощью в институт, подчеркнув, что учителя хотят разлучить минимально возможное число друзей. Оказалось, что для решения задачи существует довольно много эффективных алгоритмов, поскольку она эквивалентна задаче о нахождении минимального разреза в графе. Институтские исследователи сумели разбить 500 учеников на две группы, «разрезав» при этом всего 17 дружеских связей.