Есть идея!

Стоит подумать, прежде чем пускаться вплавь

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм с голосованием

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

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

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

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