Есть идея!

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

В стене за фонтанчиком было зеркало. Когда девушка подняла голову и увидела, что у нее за спиной в угрожающей позе с огромным кинжалом в руке стоит мужчина, она громко вскрикнула.

Джон упал в обморок.

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

Что произошло в холле гостиницы?

Видение в зеркале

Странное поведение девушки объясняется очень просто: ее мучила икота, а мужчина пытался испугать ее (как вы должно быть знаете, по весьма распространенному поверью, испуг — лучшее средство от икоты).

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

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

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

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

Ответы на эти загадки приведены в конце книги.

Глава 5 Процедурные находки

Неожиданные решения задач на исследование операций

С появлением современных ЭВМ слово «алгоритм» прочно вошло в математический лексикон. Означает оно процедуру решения, состоящую из множества шагов, выполняемых в строго определенной последовательности. Если требуется разделить одно большое число на другое, то найти частное вам помогает алгоритм деления. ЭВМ не умеет решать задачи самостоятельно: программисту приходится каждый раз составлять точный перечень тех действий, которые необходимо произвести, чтобы получить решение. Искусство программирования для ЭВМ сводится главным образом к искусству построения эффективных алгоритмов. Мы говорим об искусстве, а не о технике программирования потому, что таинственные озарения, удачные догадки и интуиция играют решающую роль в создании хороших алгоритмов.

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

Хотя в этой главе собраны процедурные задачи занимательного характера, они позволят вам легко и приятно познакомиться со многими глубокими математическими понятиями. Например, первая задача позволит вам составить весьма ясное представление о том, что имеют ввиду математики, когда толкуют об изоморфизме двух, казалось бы, не связанных между собой задач: игра в 15, в которой так силен мистер Ярмар, оказывается структурно-изоморфной знаменитой игре в «крестики-нолики». В свою очередь эта весьма популярная игра изоморфна хитроумной игре в слова, изобретенной канадским математиком Лео Мозером, и еще одной игре на «дорожной сети». Все эти игры обладают стратегиями, основанными на использовании одного из наиболее древних комбинаторных курьезов — магического квадрата 3x3.

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

Теория графов занимается изучением различных множеств точек (вершин), соединенных линиями (ребрами). Многие практические задачи исследования операций допускают моделирование на графах. Некоторые из таких задач допускают изящные решения, например задача о построении минимального дерева, решаемая при помощи алгоритма Крускала. С задачей о минимальном дереве тесно связана еще одна задача — так называемая задача о дереве Штейнера. Общее решение ее пока не известно. Деревья Штейнера находят многочисленные приложения, поэтому специалисты по теории графов ведут весьма интенсивный поиск эффективных алгоритмов построения таких деревьев на ЭВМ.

Задача Штейнера принадлежит к числу так называемых NP– полных задач. Эти задачи неразрешимы в том смысле, что эффективные алгоритмы их решений не известны и, возможно, не существуют. Например, даже при использовании лучшего из известных алгоритмов построения дерева Штейнера для n точек время, затрачиваемое на решение, с увеличением n возрастает экспоненциально. Даже при сравнительно небольшом числе точек (порядка нескольких сотен) на построение дерева Штейнера лучшее решение может быть найдено… через несколько миллионов лет! Вот что значит экспоненциальный рост.

Между NP– полными задачами существует удивительная взаимосвязь: если бы для решения одной из них удалось построить эффективный алгоритм, но он был бы применим и ко всем остальным задачам, а если бы удалось доказать, что для решения какой-то из задач эффективного алгоритма не существует, то это означало бы отсутствие эффективного алгоритма для решения и всех остальных задач. Математики подозревают, что в случае NP– полных задач мы имеем дело со второй альтернативой. Ведется широкий поиск эффективных алгоритмов, позволяющих находить не оптимальное дерево Штейнера, а дерево, достаточно близкое к оптимальному.

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

Игра в 15 на новый лад

Когда на окраине городка открывается ярмарка, всех от мала до велика охватывает радостное возбуждение (говоря о всех, я имею в виду «всех, кроме коров»).

В этом году в одном из павильонов ярмарки желающие могли сыграть в новую игру, которая так и называется — «игра в 15».

Мистер Ярмар. Рад приветствовать вас! Добро пожаловать к нам! Правила игры в 15 очень просты. Мы с вами по очереди ставим по монете на эти числа от 1 до 9. Кто ходит первым, безразлично.

Мистер Ярмар. Вы отмечаете свои ходы центами, я отмечаю свои ходы серебряными долларами. Выигрывает тот, кто первым накроет своими монетами 3 числа, дающие в сумме 15. Выигравший забирает все монеты, выложенные на стол.