Есть идея!

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

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

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

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

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

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

Задача Штейнера принадлежит к числу так называемых 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,

2 + 4 + 9 = 15,

2 + 5 + 8 = 15,

2 + 6 + 7 = 15,

3 + 4 + 8 = 15,

3 + 5 + 7 = 15,

4 + 5 + 6 = 15.

Теперь присмотримся повнимательнее к единственному магическому квадрату 3×3:

2 9 4

7 5 3

6 1 8

Если считать, что каждое число вписано в единичный квадрат (составляющий 1/9 от квадрата 3×3), то можно выделить 8 троек единичных квадратов, лежащих: на одной прямой: 3 горизонтали, 3 вертикали и 2 диагонали. Каждая из прямых соответствует одной из троек чисел, дающих в сумме 15. Следовательно, любой набор из 3 чисел, обеспечивающий победу в игре мистера Ярмара, соответствует либо горизонтали, либо вертикали, либо диагонали магического квадрата.

Нетрудно видеть, что любая партия в 15 эквивалентна партии а «крестики-нолики», разыгрываемой на магическом квадрате. У мистера Ярмара имеется магический квадрат, начерченный на листке бумаги, в который он тайком поглядывает. Хотя существует единственный квадрат ло-шу, но его можно повернуть четырьмя разными способами и, если угодно, подвергнуть зеркальному отражению. Любая из 8 разновидностей магического квадрата может служить тайным ключом к гроссмейстерской стратегии при игре в 15.

Играя с посетителем павильона в 15, мистер Ярмар мысленно играет с ним в «крестики-нолики» на магическом квадрате. Если игра в «крестики-нолики» происходит по всем правилам, то партия в 15 кончается вничью. Но легковерные посетители павильона, вздумавшие сразиться с мистером Ярмаром в 15, лишены огромного преимущества, так как не сознают, что в действительности играют в «крестики-нолики». Это облегчает задачу мистеру Ярмару, и он подстраивает своим партнерам каверзы и ловушки, вынуждая их делать ходы, ведущие к его выигрышу.

Чтобы разобраться, как действует мистер Ярмар, рассмотрим подробно партию, изображенную на картинках. Ходы приведены на диаграммах, показанных на рис. 1. Даже если мистер Ярмар ходит вторым (ставит нолики), то на шестом ходу он может поставить даме западню, которая обеспечит ему выигрыш на восьмом ходу независимо от того, как именно пойдет дама на седьмом ходу. Всякий, кто умеет играть на гроссмейстерском уровне в «крестики-нолики», взяв на вооружение магический квадрат, станет непобедимым игроком в 15.

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

Чтобы помочь вам глубже разобраться в сущности такого фундаментального понятия, как изоморфизм, рассмотрим следующую игру в слова, Берется 9 слов:

БУСЫ

ХЛЕБ

БАНЯ

ПЛУГ

СНЕГ

ГАТЬ

УРОН

ОРЕХ

МАРС

Двое игроков по очереди вычеркивают по одному слову, помечая каждый сделанный ход своими инициалами или условным значком. Выигрывает тот, кому первым удастся вычеркнуть три слова, имеющие общую букву. Пройдет немало времени, прежде чем игроки поймут, что и на этот раз они играют в добрые старые «крестики-нолики». Изоморфизм игр нетрудно установить, если вписать слова в клетки таблички, расчерченной для игры в «крестики-нолики» (рис. 2). Как нетрудно проверить, общая буква имеется лишь у трех слов, расположенных по горизонталям, вертикалям и диагоналям. Тем самым доказано, что играть в слова означает по существу играть в «крестики-нолики», и наоборот (или в 15).

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

Еще лучше играть во все эти игры, записав слова, знаки или цифры на 9 карточках. Разложив точки на столе исписанной стороной вверх, игроки могут по очереди брать по одной карточке до тех пор, пока одни из них не выиграет.

Разобравшись в изоморфизме игры в 15, «крестики-нолики» и игры в слова, приступим к новой игре — на дорожной сети. В нее играют на карте дорог, изображенной на рис. 4.

Между восемью городами проложены дороги. Вооружившись цветными карандашами (один игрок пусть выберет красный карандаш, а другой — синий), игроки по очереди закрашивают по одной дороге (каждую дорогу необходимо закрашивать целиком). Обратите внимание, что некоторые дороги проходят через города не обрываясь. В таких случаях закрашивать дорогу нужно не только до ближайшего города, а на всем ее протяжении. Выигрывает тот, кому первым удастся закрасить три дороги, ведущие в один и тот же город. На первый взгляд кажется, что новая игра не имеет ни малейшего отношения к трем уже рассмотренным нами играм. В действительности же и она изоморфна игре в «крестики-нолики»!

Чтобы установить изоморфизм, достаточно перенумеровать дороги так, как показано на рис. 4. Каждая дорога соответствует клетке магического квадрата, помеченной тем же числом. Каждый город на карте соответствует горизонтали, вертикали или диагонали в магическом квадрате. Как и в предыдущих случаях, изоморфизм полный. Всякий, кто умеет на гроссмейстерском уровне играть в «крестики-нолики», не будет знать горечи поражений и в новой игре.

На рис. 5 изображен один из 880 различных (не переходящих друг в друга под действием поворотов и отражений) магических квадратов 4×4. Постоянная этого квадрата (сумма чисел, стоящих на любой горизонтали, вертикали и диагонали) равна 34. Может ли такой квадрат служить ключом для беспроигрышной игры в 34, то есть игры, в которой игроки по очереди выбирают число от 1 до 16 (ни одно число не разрешается выбирать дважды) до тех пор, пока у одного из игроков не наберется четыре числа, дающие в сумме 34. Изоморфна ли игра в 34 игре в «крестики-нолики» на магическом квадрате, изображенном на рис. 5? Нет, не изоморфна! Почему?

Можно ли так изменить правила игры в «крестики-нолики», чтобы победную комбинацию образовывали четыре клетки, не лежащие на одной горизонтали, вертикали или диагонали, и утраченный изоморфизм был восстановлен?

Как взвесить гиппопотама

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

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

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

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

Вождь племени был вне себя от ярости. Он вызвал сборщика податей.

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

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

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

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

Затем он свел гиппопотама на берег и принялся нагружать лодку золотыми слитками. Так он трудился до тех пор, пока лодка не погрузилась в воду по сделанную ранее отметку, после чего с полным основанием доложил вождю, что вес груды золота в лодке равен весу священного гиппопотама.

По закону Архимеда, плавающее тело вытесняет объем воды, масса которого равна массе тела. Следовательно, если священного гиппопотама ввести на лодку, то та погрузится в воду, вытеснив количество воды, масса которой равна массе гиппопотама.

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

Предположим, что мы принялись швырять монеты одну за другой за борт лодки на дно бассейна. Глубина погружения лодки в воду при этом уменьшается. А что произойдет с уровнем воды в бассейне? Будет он подниматься или опускаться?

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

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

Физик Дж. Гамов однажды привел яркий пример, поясняющий решение нашей задачи. Некоторые звезды состоят из вещества в миллионы раз более плотного, чем вода. Кубический сантиметр такого вещества весит не одну тонну. Если швырнуть его за борт лодки, он опустится на дно бассейна и вытеснит лишь 1 см³ воды, то есть ничтожно малое количество, поэтому вода в бассейне опустится. Ситуация с золотом точно такая же, только вода в бассейне опустится гораздо меньше.

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

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

А вот аналогичная задача, требующая иного решения. В бутыль неправильной формы из прозрачного стекла налит концентрированный раствор кислоты. На стенках бутылки имеются 2 отметки: одна соответствует 10 л кислоты, другая — 5 л.

Кто-то отлил немного кислоты, отчего уровень ее в бутыли стал чуть ниже отметки 10 л. Вам требуется отлить для опыта ровно 5 л кислоты. Кислота слишком опасная и летучая, чтобы ее можно было переливать в другие мерные сосуды. Как легко и просто отмерить ровно 5 л кислоты?

Одно из решений состоит в том, чтобы, бросая в бутыль стеклянные шарики (или шарики из любого другого материала, не разъедаемого кислотой), довести уровень кислоты до отметки 10 л, после чего отливать кислоту до тех пор, пока ее уровень в бутыли не сравняется с отметкой 5 л.

Как распределить домашние обязанности

Мистер и миссис Джонс только что поженились. У каждого из них есть постоянная работа, и они решили распределить между собой и обязанности по дому.

Стремясь к честному распределению обязанностей по дому, супруги Джонс составили перечень всех работ по дому на неделю.

Бастер. Я беру на себя половину обязанностей, дорогая. Остальные обязанности предоставляю тебе.

Жанет. Прошу прощения, Бастер, но, по-моему, ты распределил обязанности нечестно. Мне ты оставил всю грязную работу, а себе взял то, что чище и полегче.

С этими словами миссис Джонс взяла список обязанностей по дому и отметила те работы, которые бы ей хотелось взять на себя. Ее муж не согласился с новым распределением обязанностей.

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

Пока супруги пререкались, в дверь позвонили. Это пришла мать миссис Джонс.

Миссис Смит. Из-за чего драка, голубки? Ваши крики слышны на лестнице.

Выслушав доводы Бастера и его жены, миссис Смит улыбнулась.

Миссис Смит. Я нашла великолепное решение. Сейчас я покажу вам, как распределить обязанности по дому, чтобы вы оба остались довольны.

Миссис Смит. Пусть один из вас разделит перечень обязанностей на 2 части, каждую из которых он бы охотно взял на себя, а другой выберет себе любую половину. Тогда обязанности будут распределены в соответствии с желаниями каждого из вас, не так ли?

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

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

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

Она допускает следующее решение. Один из любителей пирога медленно ведет большим ножом над пирогом. Пирог может быть любой формы. Вести нож нужно так, чтобы доля пирога по одну сторону ножа непрерывно возрастала от нуля до максимума. Как только любой из трех участников раздела сочтет, что по одну сторону ножа осталась треть пирога, он произносит вслух: «Режь!» Тот, кто держит нож, немедленно отрезает кусок пирога и отдает тому, что подал команду. Если команду «Режь!» подадут одновременно двое или даже трое любителей пирога, отрезанный кусок вручается любому из них.

Двое остальных вполне удовлетворены куском пирога, доставшимся им на двоих: ведь этот кусок составляет не менее ⅔ от всего пирога. Задача о разделе этого куска сводится к предыдущей задаче о честном разделе между двумя претендентами и решается, если один режет, а другой выбирает.

Метод честного раздела допускает очевидное обобщение на случай n участников. Один из участников ведет ножом над пирогом. Первый, кто подаст команду «Режь!», получает первый кусок (если команду подадут сразу несколько человек, отрезанный кусок достается одному из них по жребию). Затем процедура повторяется с n − 1 остальными участниками. Так продолжается до тех пор, пока не останутся 2 участника. Последняя порция пирога делится между ними по принципу «я режу, ты выбираешь», или, если угодно, при помощи все той же универсальной процедуры: один ведет ножом над пирогом, и каждый может скомандовать «Режь!», если сочтет, что по одну сторону ножа осталось не менее ½ порции, доставшейся им на двоих. Общее решение задачи о справедливом разделе может служить прекрасным примером доказательства, проводимого при помощи метода математической индукции. Ясно, что тот же алгоритм справедливого раздела применим и к задаче о распределении домашних обязанностей между n обитателями квартиры, не оставляющем ни у кого ни малейшего повода для неудовольствия.

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

Воздушный акробат

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

Тони, бывший акробат, вознамерился похитить веревки — отрезать от каждой из них кусок побольше.

Тони. Как назло, колокола на самом верху звонницы заперты на семь запоров. Проникнуть можно только в комнату звонарей.

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

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

Что бы вы сделали на его месте?

Решение Тони было весьма остроумным. Прежде всего он связал свободные концы веревок. Затем залез по одной из них (обозначим ее A) под самый потолок.

Повиснув под потолком на веревке A, Тони перерезал веревку B примерно на полметра ниже потолка и свисающий из отверстия остаток связал в петлю.

Продев в петлю руку, Тони повис на веревке B и перерезал веревку A под самым потолком, приняв все меры предосторожности, чтобы отрезанный кусок веревки A не упал на пол. Затем он продел веревку A сквозь петлю и принялся протягивать ее, пока наверху не оказались связанные концы веревок A и B.

После этого Тони слез по сложенной вдвое веревке, выдернул ее из петли и ушел, унося с собой всю веревку A и почти всю веревку B.

А как бы вы это сделали?

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

Например, похититель мог бы завязать на веревке В так называемую колышку — специальный узел, используемый моряками и альпинистами для временного укорочения снасти (рис. 6). Повиснув на веревке B, он мог бы обрезать веревку A под потолком (и дать ей упасть на пол), после чего перерезать веревку B в точке X. Всем альпинистам хорошо известно, что узел будет держать, пока вор не соскользнет по веревке B вниз. Дернув за веревку B, он распустит колышку и получит почти всю веревку B, за исключением небольшого ее куска под самым потолком.

Другое возможное решение. Похититель взбирается наверх по веревке A. Ухватившись одной рукой за веревку B и вися на веревке A, он начинает перерезать волокно за волокном веревку A, пока не почувствует, что та вот-вот оборвется. Затем он стягивает обе веревки вместе и вися на двух веревках одновременно, начинает перерезать веревку B под самым потолком так же, как он перерезал веревку A, и спускается по двум веревкам вниз. Каждая из веревок в отдельности не выдержала бы его веса, но с половинной нагрузкой веревки справляются благополучно. Очутившись на полу, вор сильным рывком обрывает веревки по месту надреза.

Третий способ предполагает, что отверстия в потолке достаточно велики. Сначала похититель связывает свободные концы веревок A и B у пола. Затем взбирается по веревке A, перерезает веревку B под потолком и проталкивает ее длинный конец в отверстие для веревки B, пока тот не покажется из отверстия для веревки A, после чего начинает протягивать веревку B до тех пор, пока ее конец не окажется у пола, а узел — под потолком у отверстия для веревки B. Ухватившись у самого потолка за веревку B, продернутую сквозь отверстие для веревки A, и нижнюю часть веревки A, подтянутую теперь к потолку, похититель перерезает верхнюю часть веревки A (торчащую из отверстия для веревки A) как можно выше и, спустившись по двойной веревке, сдергивает ее на пол.

А вот более хитроумный вариант предыдущего решения. Свободные концы веревок остаются не связанными. Похититель взбирается по веревке A, перерезает веревку B, проталкивает ее длинный конец сквозь отверстие для веревки B и вытягивает его из отверстия для веревки A, после чего захлестывает его вокруг веревки B и завязывают узлом (рис. 7). Повиснув на веревке B, похититель перерезает веревку A и привязывает конец ее к узлу. Спустившись по веревке B, он тянет за веревку A, веревка В проскальзывает сквозь петлю и падает вниз.

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

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

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

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

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

Масса королевы 78 кг, масса ее дочери 66 кг и масса сына 36 кг. Укажите простейший, то есть состоящий из наименьшего числа шагов, алгоритм побега. Корзины достаточно велики, чтобы вместить либо 2 людей, либо одного человека и камень. При побеге августейшим пленникам никто не помогает, и они не могут помочь себе, потянув за веревку. Иначе говоря, блок действует только в том случае, если масса в одной корзине превосходит массу в другой корзине.

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

1. Сын вниз, камень вверх,

2. Дочь вниз, сын вверх.

3. Камень вниз.

4. Королева вниз, камень и дочь вверх.

5. Камень вниз.

6. Сын вниз, камень вверх,

7. Камень вниз.

8. Дочь вниз, сын вверх.

9. Сын вниз, камень вверх,

Задачи этого типа иногда усложняются введением животных, которые не могут самостоятельно влезать в корзины и вылезать из корзин. Льюис Кэрролл предлагает следующий вариант предыдущей задачи. На вершине башни вместе с королевой находились не только ее сын, дочь и груз, но и свинья массой 24 кг, собака массой 18 кг и кошка массой 12 кг. Спускать четвероногих нужно с теми же предосторожностями, что и людей, но теперь кто-нибудь непременно должен быть и наверху и внизу, чтобы класть животных в корзины и доставать их оттуда.

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

Катастрофа на острове

Орвилл поставил свою машину на берегу небольшого озера.

Орвилл. Какой ровный берег! Для запуска моей радиоуправляемой авиамодели лучшего места не найти. Ни тебе деревьев, ни скал. Единственное дерево — на островке посреди озера.

Орвилл хотел было заставить модель облететь вокруг дерева, но не рассчитал расстояние. Модель врезалась в дерево и упала на землю.

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

И вдруг Орвилла осенила простая и в то же время остроумная идея.

Орвилл. Делать нечего, придется намокнуть, зато модель будет спасена.

Как Орвилл достал свою модель?

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

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

Как, пользуясь двумя досками, путешественник может попасть на остров? Решение показано на рис. 9.

Обобщим классическую задачу: предположим, что путешественник нашел на берегу несколько досок. Сможет ли он добраться до острова, если доски окажутся более короткими, чем в классической головоломке?

С тремя досками вы справитесь довольно легко, построив мост, изображенный на рис. 10. Но найти решение с 5 или 8 короткими досками несравненно труднее. На рис. 11 изображен мост, построенный из 8 досок.

В идеализированной постановке остров вырождается в точку, доски заменяются отрезками прямых, а для «перекрытия» достаточно касания. Представим себе, что мы располагаем неограниченным запасом одинаковых «досок». Предельный случай показан на рис. 12. Если озеро имеет форму квадрата со стороной, равной 2 единицам длины, то каждая доска (даже если их у нас бесконечно много) не может быть короче √2/2. Доказать это можно с помощью теоремы Пифагора.

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

Ленивый донжуан

Джек считал себя величайшим в мире сердцеедом. Он решил снять квартиру в Вашингтоне.

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

На плане города Джек отметил те места, где живут его приятельницы.

Джек. Я бы хотел поселиться в таком месте, откуда было бы удобно добираться до всех моих приятельниц, то есть чтобы сумма расстояний от моего дома до тех мест, где живут они, была бы минимальной.

Джек прикидывал так и этак, но все было безуспешно: найти нужную точку никак не удавалось. Вдруг ему пришло в голову неожиданное и простое решение.

Джек. Есть идея! Теперь я знаю, как легко и просто выбрать, где мне поселиться.

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

Джек. Анита и Банни проголосовали бы за такое переселение, так как я перебрался бы поближе к ним, а Вика проголосовала бы против. Но в расстоянии я выиграл бы больше, чем проиграл, поэтому я подчинюсь мнению, за которое подано большинство голосов.

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

К его радости, квартирная плата в выбранном месте была ему по карману. Но через неделю Банни переехала на новую квартиру в 7 кварталах от своего прежнего дома.

Джек. Жаль, но придется переезжать на новую квартиру.

Но когда Джек достал план города, то, к своему удивлению, обнаружил, что может оставаться на месте.

Как это может быть?

Если Банни переедет на 7 кварталов к востоку от того места, где жила раньше, то ее переезд никак не скажется на выборе резиденции Джека. Более того, Банни могла бы переехать сколь угодно далеко на восток, и место, выбранное для своей квартиры Джеком, по-прежнему оставалось бы оптимальным.

Эффективность алгоритма с голосованием вы сможете лучше оценить, применив к более обширной территории с прямоугольной планировкой, на которой отмечено более трех точек. Вы обнаружите, что алгоритм Джека позволяет быстро находить положение точки x, сумма расстояний от которой до всех отмеченных точек минимально, если число отмеченных точек нечетно. Почему алгоритм перестает работать при четном числе точек? Причина довольно ясна: при четном числе отмеченных точек не исключен «ничейный» исход голосования, а как только голоса разбиваются поровну, алгоритм не срабатывает.

Попробуйте самостоятельно ответить на следующие вопросы:

1. Не могли бы вы предложить эффективный алгоритм, действующий при четном числе отмеченных точек?

2. При каких условиях перемещение одной или нескольких отмеченных точек не сказывается на положении точки x?

3. Изменится ли алгоритм с голосованием, если мы вздумаем учесть ширину улиц?

4. Изменится ли алгоритм, если точка x и отмеченные точки могут не располагаться на перекрестках?

5. Применим ли алгоритм с голосованием в том случае, если сеть улиц образована прямыми, идущими в самых разных, а не только в двух взаимно перпендикулярных направлениях?

6. Останется ли алгоритм в силе, если улицы будут кривыми или зигзагообразными?

Хотя алгоритм с голосованием применим к любым сетям, на «чистой» плоскости без выделенной сети он сразу утрачивает силу, и это понятно: по чистой плоскости мы можем перемещаться в любом направлении, не придерживаясь заданных маршрутов. Общая задача ставится так. На плоскости заданы n точек. Требуется найти такую точку x, чтобы сумма кратчайших расстояний от нее до заданных точек была минимальной. Рассмотрим, например, три города A, B и C. Где следовало бы построить аэропорт, чтобы суммарная протяженность воздушных маршрутов из него в эти города была минимальной? Ясно, что если бы речь шла о длине автомобильных маршрутов, связывающих некоторую точку на карте с городами A, B и C, то ответ был бы другой. Иначе говоря, идеальное место для аэропорта может не совпадать с идеальным местом для автобусной станции.

Ответ, основанный на довольно сложных геометрических соображениях, гласит: идеальным местом для строительства аэропорта была бы такая точка на карте, в которой лучи, проведенные к трем городам, образовывали бы между собой углы в 120°. Если бы число городов возросло до четырех, причем города располагались в вершинах выпуклого четырехугольника, то аэропорт выгоднее всего было бы построить в точке пересечения диагоналей. Доказать это утверждение совсем не трудно. Общая задача (найти точку x, сумма кратчайших расстояний от которой до n заданных точек плоскости минимальна) более трудная.

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

Усложним теперь исходную задачу. Предположим теперь, что в точках A, B и C находятся не населенные пункты с одинаковым количеством жителей, а три дома, причем в доме A живут 20 школьников, в доме B — 30 школьников и в доме C — 40 школьников. Все дети ходят в одну школу. Где следует выстроить школу, чтобы свести до минимума сумму расстояний, проходимых всеми детьми?

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

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

Сработает ли наше аналоговое устройство, если в одном доме учеников окажется больше, чем в двух других домах, вместе взятых, например, если 20 школьников живут в доме A, 30 школьников — в доме B и 100 школьников — в доме C? Да, сработает: грузик весом в 100 единиц будет тянуть свою веревочку до тех пор, пока узел не совместится с отверстием C. Это означает, что школу следует построить в точке C!

Будет ли наше аналоговое вычислительное устройство работать также безотказно при числе точек больше трех? Попробуйте придумать такое расположение четырех точек, при котором наше устройство даст заведомо неверный результат. Указание: что произойдет, если четыре точки расположены в вершинах невыпуклого четырехугольника?

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

На плоскости заданы n точек. Требуется соединить их отрезками прямых так, чтобы суммарная протяженность сети была наименьшей. Добавлять новые вершины к заданным запрещается. Сеть, которую требуется построить, естественно назвать минимальным деревом. Можете ли вы предложить алгоритм для построения минимального дерева?

Алгоритм Крускала (названный в честь Джозефа Б. Крускала, который впервые предложил его) позволяет свести построение минимальной сети к следующим этапам.

Определить расстояния между любыми двумя точками и расположить все расстояния в порядке возрастания (напомним, что расстоянием между двумя вершинами в графе называется число ребер, ведущих из одной вершины в другую). Кратчайшее расстояние равно 1, затем идет расстояние 2 и т. д. Если два расстояния одинаковы, то безразлично, какое из них считать первым. Соединить отрезками прямых все точки, расстояние между которыми равно 1. Затем соединить отрезками прямых все точки, расстояние между которыми равно 2, 3, 4, 5 и т. д. Никогда не проводить отрезок, замыкающий цикл. Если проведенная линия замыкает цикл, отбросить соответствующую пару точек и перейти к рассмотрению точек, разделенных следующим по величине расстоянием. Проделав все эти операции, мы получим минимальное дерево, соединяющее все заданные точки.

Минимальные деревья обладают интересными свойствами. Например, все рёбра пересекаются только в вершинах, причем в одной вершине пересекается не более 5 ребер.

Минимальные деревья отнюдь не обязательно совпадают с кратчайшей сетью, соединяющей n точек. Напомним, что дополнять сети новыми вершинами не разрешается. Если снять запрет на новые вершины, то сети могут стать короче. В качестве простого примера достаточно рассмотреть четыре вершины единичного квадрата. Минимальное дерево состоит из любых трех сторон квадрата (рис. 13, слева). Предположим, что разрешается вводить новые вершины. Существует ли тогда сеть короче 3, соединяющая четыре вершины?

Большинство людей считает, что минимальную сеть образуют две диагонали квадрата (рис. 13, посредине), но это не верно. Правильное решение изображено на рис. 13, справа. Суммарная длина двух диагоналей квадрата равна 2√2 ≈ 2,82… Суммарная длина сети на правом рисунке меньше, она равна лишь 1 + √3 ≈ 2,73…

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

Хирурги и инфекция

В чаще тропических джунглей расположен госпиталь, в котором работают три хирурга: Джонс, Смит и Робисон.

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

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

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

Мисс Клини. У меня для вас плохие новости, уважаемые эскулапы.

Мисс Клини. У нас остались только две пары стерильных перчаток: одна пара белых и одна пара синих.

Доктор Джонс. Только две пары? Если я оперирую первым, то обе стороны моих перчаток могут оказаться зараженными. После Смита, если он будет оперировать вторым, окажутся зараженными обе стороны другой пары перчаток, и Робисону не в чем будет оперировать.

Вдруг лицо доктора Смита просветлело.

Доктор Смит. А что если я надену две пары перчаток — синие поверх белых. Одна сторона каждой пары инфицируется, а другая останется стерильной.

Джонс быстро схватил мысль коллеги.

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

Сестра Клини. А о вожде вы не подумали? Ведь если кто-нибудь из вас является носителем инфекции, то вы можете заразить вождя во время операции.

Справедливое замечание медсестры повергло хирургов в замешательство. Что делать? И тут мисс Клини осенило.

Сестра Клини. Я придумала, как вам втроем оперировать вождя, не подвергая ни себя, ни его риску заражения.

Никто из трех врачей так и не смог ничего предложить, но когда мисс Клини объяснила, в какой последовательности надлежит надевать и выворачивать перчатки, все согласились, что ее план действительно обеспечивает полную безопасность и вождя и хирургов. Как предложила действовать мисс Клини?

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

Пусть Б1 — внутренняя, а Б2 — наружная сторона белых перчаток, С1 — внутренняя, а С2 — наружная сторона синих перчаток.

Доктор Смит надевает обе пары перчаток: сначала он натягивает белые перчатки, а поверх них синие. Сторона Б1 инфицируется, так как соприкасается с руками доктора Смита, сторону С2 может инфицировать вождь. После операции Смит снимает обе пары перчаток. Доктор Джонс надевает синие перчатки стерильной стороной С1 внутрь, а доктор Робинсон выворачивает белые перчатки наизнанку и надевает их стерильной стороной Б2 внутрь.

Переходим теперь к описанию процедуры, предложенной мисс Клини.

Доктор Смит по-прежнему надевает 2 пары перчаток. Стороны Б1 и С2 могут оказаться после операции инфицированными, но стороны Б2 и С1 останутся стерильными.

Доктор Джонс надевает синие перчатки стороной С1 внутрь.

Доктор Робисон выворачивает белые перчатки наизнанку и надевает их стороной Б2 внутрь. Поверх белых перчаток он натягивает синие перчатки стороной С2 наружу.

Во всех трех случаях вождя касается только сторона С2 синих перчаток, поэтому он не подвергается опасности заразиться от кого-нибудь из хирургов.

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