Есть идея! - [49]
Вы познакомитесь также с законом Архимеда (в задаче о взвешивании священного гиппопотама), с нерешенной задачей о справедливом разделе (в задаче о распределении домашних обязанностей), с некоторыми классическими комбинаторными задачами (в комментариях к задаче о краже веревки с колокольни) и с важными задачами теории графов (в задаче о ленивом искателе любовных приключений).
Теория графов занимается изучением различных множеств точек (вершин), соединенных линиями (ребрами). Многие практические задачи исследования операций допускают моделирование на графах. Некоторые из таких задач допускают изящные решения, например задача о построении минимального дерева, решаемая при помощи алгоритма Крускала. С задачей о минимальном дереве тесно связана еще одна задача — так называемая задача о дереве Штейнера. Общее решение ее пока не известно. Деревья Штейнера находят многочисленные приложения, поэтому специалисты по теории графов ведут весьма интенсивный поиск эффективных алгоритмов построения таких деревьев на ЭВМ.
Задача Штейнера принадлежит к числу так называемых NP-полных задач. Эти задачи неразрешимы в том смысле, что эффективные алгоритмы их решений не известны и, возможно, не существуют. Например, даже при использовании лучшего из известных алгоритмов построения дерева Штейнера для n точек время, затрачиваемое на решение, с увеличением n возрастает экспоненциально. Даже при сравнительно небольшом числе точек (порядка нескольких сотен) на построение дерева Штейнера лучшее решение может быть найдено… через несколько миллионов лет! Вот что значит экспоненциальный рост.
Между NP-полными задачами существует удивительная взаимосвязь: если бы для решения одной из них удалось построить эффективный алгоритм, но он был бы применим и ко всем остальным задачам, а если бы удалось доказать, что для решения какой-то из задач эффективного алгоритма не существует, то это означало бы отсутствие эффективного алгоритма для решения и всех остальных задач. Математики подозревают, что в случае NP-полных задач мы имеем дело со второй альтернативой. Ведется широкий поиск эффективных алгоритмов, позволяющих находить не оптимальное дерево Штейнера, а дерево, достаточно близкое к оптимальному.
В этой главе чаще, чем в других, упоминаются последние результаты исследований, проводимых лучшими умами современной математики.
Игра в 15 на новый лад
Когда на окраине городка открывается ярмарка, всех от мала до велика охватывает радостное возбуждение (говоря о всех, я имею в виду «всех, кроме коров»).
В этом году в одном из павильонов ярмарки желающие могли сыграть в новую игру, которая так и называется — «игра в 15».
Мистер Ярмар. Рад приветствовать вас! Добро пожаловать к нам! Правила игры в 15 очень просты. Мы с вами по очереди ставим по монете на эти числа от 1 до 9. Кто ходит первым, безразлично.
Мистер Ярмар. Вы отмечаете свои ходы центами, я отмечаю свои ходы серебряными долларами. Выигрывает тот, кто первым накроет своими монетами 3 числа, дающие в сумме 15. Выигравший забирает все монеты, выложенные на стол.
Посмотрим, как играют в 15. Первый ход — дама ставит цент на 7. Поскольку цифра 7 накрыта, ставить на нее в дальнейшем нельзя; ни доллары, ни центы. То же можно сказать и обо всех остальных цифрах: ни одну из них нельзя накрывать монетами дважды, будь то центы или доллары.
Мистер Ярмар ставит доллар на 8.
Дама делает второй ход и ставит цент на 2. Если ей удастся поставить цент на 6, она выиграет.
Мистер Ярмар, желая воспрепятствовать выигрышу партнера, ставит доллар на 6. Он выиграет, если ему удастся поставить доллар на 1.
Дама замечает угрозу и блокирует мистеру Ярмару путь к выигрышу, ставя цент на 1.
Мистер Ярмар с усмешкой ставит доллар на 4. Дама замечает, что если он следующим ходом поставит доллар на 5, то выиграет, и отрезает ему этот путь к выигрышу.
Дама ставит цент на 5.
Но мистер Ярмар ставит доллар на 3 и выигрывает, так как 8 + 4 + 3 = 15. Дама проиграла свои 4 цента.
Мэру города игра в 15 очень понравилась. Пронаблюдав за игрой в течение почти целого дня, он пришел к убеждению, что мистер Ярмар придерживается тайной беспроигрышной стратегии.
Всю ночь напролет мэр пытался разгадать, в чем состоит тайная стратегия мистера Ярмара.
Внезапно мэра озарила поразительная по простоте идея.
Мэр. Я так и знал, что должна быть какая-то система! У доверчивых простаков, надеющихся заполучить серебряные доллары мистера Ярмара, нет ни шанса на выигрыш.
Какая идея осенила мэра? Не могли бы вы самостоятельно разработать беспроигрышную стратегию для игры в 15?
Выигрышную стратегию указать нетрудно, если догадаться, что игра в 15 мистера Ярмара математически эквивалентна игре в «крестики-нолики». Установить эквивалентность нам поможет ло-шу — магический квадрат 3×3, впервые открытый в древнем Китае.
Чтобы в полной мере оценить изящество этого магического квадрата, выпишем прежде всего все возможные тройки однозначных чисел (попарно не равных и отличных от нуля), которые в сумме дают 15. Существует 8 таких троек:
1 + 5 + 9 = 15,
1 + 6 + 8 = 15,
