Города Задаченск и Решенск отстоят друг от друга на 100 км. Как-то погожим июньским днём в полдень из этих городов выходят навстречу друг другу два поезда, причём каждый движется со скоростью 50 км в час. В тот же момент пчела, уютно пристроившаяся на головной фаре поезда в Задаченске, вылетает в направлении Решенска и летит вдоль железнодорожного пути со скоростью 90 км в час. Встретившись с поездом, идущим из Решенска, пчела резко разворачивается и летит обратно всё с той же скоростью 90 км в час. Встретившись с поездом, идущим из Задаченска, она опять разворачивается и летит в противоположном направлении. Таким образом пчела снуёт между поездами до тех пор, пока они не встретятся. Какова будет полная длина пути, проделанного пчелой? Ответ к этой известной задачке, который будет дан в конце статьи, короткий. Это просто число.

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

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

Каким образом могут разминуться поезда?

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

Вытирая пот с лица красным в горошек носовым платком, машинист поезда, следующего из Задаченска, восклицает: «Я не знаю, как мы сможем пропустить друг друга. У нас есть только вон то небольшое ответвление». Машинист из Решенска настроен более оптимистично. Он излагает план, следуя которому поезда могут разминуться. Возможно ли это? Прежде чем читать дальше, давайте взглянем на рисунок. Для конкретности на нем изображены два поезда, каждый из пяти вагонов. В общей формулировке этой алгоритмической головоломки поезда имеют по n вагонов.

Подходя к решению этой сравнительно простой задачи, читатель, наверно, будет говорить себе под нос: «Так, посмотрим... А почему бы не провести состав из Задаченска по боковому пути по одному вагону? Поезд из Решенска мог бы сновать как челнок взад и вперёд, затаскивая каждый раз новый вагон задаченского поезда на боковой путь, затем, проезжая мимо него по основному пути на всю свою длину и прицепляя его с другой стороны, чтобы вывести с бокового пути перед тем, как вернуться за следующим вагоном».

Такое описание может послужить отправной точкой для построения ответа к алгоритмической головоломке, но его нужно сделать более ясным и чётким. Воспользуемся для этого алгоритмической системой записи, введя некоторые вспомогательные обозначения. При решении задачи можно выделить четыре участка железнодорожного полотна: участок от Задаченска до бокового пути (обозначим его A); отрезок основного пути между стрелками, соединяющими его с боковым путём (B); сам боковой путь (B') и участок от бокового пути до Решенска (C). Такая команда, как «Вперёд к A», означает, что поезд из Решенска, состоящий из локомотива и вагонов, прицепленных к нему на данный момент, продвигается вперёд до тех пор, пока полностью не окажется на участке пути A.

Напомним, что у каждого поезда по n вагонов. Локомотив задаченского поезда обозначим через P₁, а его вагоны пронумеруем как P₂, P₃ и т.д. Команда «Прицепить P_k» означает, что к данному моменту решенский поезд находится вплотную к k-му элементу задаченского поезда; состав из Решенска мягко подкатывается к вагону P_k и сцепляется с ним. Те из вас, кто когда-нибудь жил вблизи железнодорожной станции, наверное, хорошо помнят очень характерный, ни на что другое не похожий звук, которым сопровождается сцепка вагонов.

Теперь можно записать алгоритм решения:

расцепить поезд P

for k=1 to n+1

вперёд к A

прицепить P_k

назад к C

вперёд к B'

отцепить P_k

назад к C

вперёд к A

назад к B'

прицепить P_k

назад к C

отцепить P_k

сцепить поезд P

Сначала поезд из Задаченска расцепляется на отдельные вагоны и мы имеем n вагонов и локомотив. Затем в алгоритме начинается цикл из 11 шагов. Всю работу выполняет поезд из Решенска. Ни разу не отцепив ни одного из своих вагонов, он сначала проходит вперёд на участок A, где сцепляется с первым элементом (k=1) задаченского состава, т.е. с локомотивом. Он буксирует локомотив назад к участку C и после перевода стрелок загоняет его на боковой путь B', здесь локомотив отцепляется. Затем состав из Решенска снова возвращается на участок C, стрелки переводятся, и он идёт вперёд к участку A. После этого он возвращается, проходит на боковой путь, снова прицепляется к оставленному там локомотиву задаченского состава и буксирует его на участок C, где отцепляет и оставляет его. Ту же последовательность шагов поезд выполняет для каждого из оставшихся вагонов задаченского состава. Когда главный цикл завершён, все вагоны задаченского поезда оказываются на участке дороги между решенским составом и Решенском. Теперь, как только поезд придёт в себя от утомительных алгоритмических процедур, он запыхтит и тронется в направлении к Решенску.

Ещё одна алгоритмическая головоломка возникает, когда поезд из Задаченска, завершая своё путешествие, подъезжает к Решенску. Машинист, глядя на пробегающие мимо него пригороды, вдруг с ужасом вспоминает, что забыл взять с собой пакетик с бутербродами. Делать нечего, придётся возвращаться обратно. Он нажимает на тормоза, и постепенно тяжёлый состав из n вагонов останавливается. Пятиться всю дорогу до Задаченска не очень-то удобно. К счастью, машинист замечает справа небольшое боковое ответвление — тупик. Его длина достаточна лишь для одного вагона, у разветвления есть управляющие стрелки. Вдохновлённый алгоритмическим достижением машиниста из Решенска, наш скромный герой тоже хочет попробовать свои силы.

Прежде всего машинист задаченского состава рисует на клочке бумаги схему пути (см. рисунок).

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

Затем он расписывает алгоритм и тщательно проверяет его, водя пальцем по бумаге то туда, то сюда и бормоча что-то себе под нос. После проверки алгоритма он начинает длительную серию отцеплений, буксировок и сцеплений, пока это всё не заканчивается тем, что поезд оказывается полностью развёрнутым в обратном направлении. Причём не только порядок, в котором следовали локомотив и вагоны, сохранился, но и сами вагоны и локомотив оказались повёрнутыми в обратном направлении. Каким образом машинист проделал этот манёвр? Лучшее решение читателей будет опубликовано в одном из следующих номеров журнала. Под словом «лучшее» подразумевается наиболее ясное и наиболее остроумное решение. Эта задача не так бесхитростна, как может показаться на первый взгляд.

Уже на пути в Задаченск машинист понял, что решение задачи потребовало очень больших энергетических затрат. Угольный тендер паровоза оказался почти пустым. Количество работы, затраченной во время маневров поезда, было пропорционально n³. Только теперь, по пути домой, машинист задаченского поезда подумал о том, что, возможно, существует более эффективное решение. Давайте подумаем тоже, возможно ли развернуть состав за меньшее число шагов, скажем, порядка n² или даже n log n?

Чтобы ещё лучше потренировать однорельсовые умы в искусстве алгоритмических головоломок, вот ещё одна маленькая задачка. Локомотив без вагонов приближается к поворотному кругу, на котором стоят два пустых вагона. Между вагонами расположен небольшой железнодорожный мост, прочность которого позволяет выдержать один вагон, но локомотива он уже не выдержит (см. рисунок).

Локомотив должен поменять вагоны местами, не пересекая опасного моста

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

Со следующими двумя алгоритмическими головоломками я не был знаком раньше. Они продолжают транспортную тему, начатую в задачах о поездах, однако переводят наши исследования на более высокую ступень — теперь мы будем заниматься грузовиками. Задачи этой серии я буду называть задачами разведчика пустыни. В первой задаче патрульный автомобиль разведчика пустыни имеет бак, вмещающий 10 галлонов бензина. Бак автомобиля заполняется из цистерн ёмкостью 50 галлонов. Несколько таких цистерн хранятся на складе. Если автомобиль может везти в качестве груза одну цистерну с бензином и если он затрачивает 1 галлон горючего на 10 миль пути независимо от того, вёзет он с собой цистерну или нет, то каково максимальное расстояние, на которое он может удалиться от базы, прежде чем у него иссякнет горючее? Ответ, конечно, зависит от количества цистерн с бензином, хранящихся на базе. Как и во всех алгоритмических головоломках, предположим, что число цистерн на базе равно n.

На какое максимальное расстояние сможет уехать грузовик, располагая n цистернами с горючим?

Если n=1, то ответ получить несложно. Автомобиль заправляет свой бак из единственной цистерны, грузит её в кузов и отправляется в путь под жарким солнцем пустыни. Заправляясь при необходимости из цистерны, автомобиль, очевидно, пройдёт 500 миль, прежде чем горючее будет полностью исчерпано. А как далеко он сможет уехать на двух цистернах? Поскольку автомобиль может везти с собой лишь одну цистерну, то, очевидно, он отвезёт первую цистерну на какое-то расстояние в пустыню, заправится из неё, если это необходимо, а затем вернётся на базу за второй. Вторую цистерну разведчик повезёт по той же дороге. Он может остановиться для заправки, а может и не останавливаться у первой, оставленной им в пустыне цистерны, прежде чем продолжить свое путешествие. Как далеко он сможет уехать, совершая такие челночные перемещения между пунктами, в которых он оставляет запасы горючего? Внезапно задача перестаёт казаться тривиальной.

Приведём короткий алгоритм, позволяющий патрульному автомобилю проехать путь длиной 600 миль:

заправить бак и погрузить первую цистерну;

вперёд 100 миль;

снять цистерну и заправиться;

назад на базу за второй цистерной;

заправиться и погрузить цистерну;

вперёд 100 миль;

заправиться из первой цистерны;

вперёд 100 миль;

снять цистерну и заправиться;

назад к первой цистерне;

заправиться и погрузить цистерну;

вперёд 100 миль.

На этой стадии алгоритма автомобиль удалился от базы на 200 миль. У него две цистерны: в одной осталось 10 галлонов, а в другой — 30 галлонов бензина. Поездка продолжается после того, как водитель заправляет машину из первой цистерны (оставляя её пустой), погружает в кузов вторую цистерну и уезжает, скрываясь за барханами. Таким образом, он сможет проехать ещё 400 миль, прежде чем у него кончится горючее. Полное расстояние от базы составит 600 миль. Поскольку увеличение расстояния по сравнению с первым случаем, когда на базе была лишь одна цистерна, составляет всего 100 миль, у читателя, наверное, возникнет справедливое подозрение, что существует лучший алгоритм решения этой задачи. Действительно, можно добиться лучшего результата.

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

В другой части громадной песчаной территории проходит патрульный маршрут противника, объезжаемый им другим способом. В произвольных пунктах замкнутого маршрута самолёт сбрасывает n цистерн с горючим. В каждой цистерне содержится определённое количество бензина, однако это количество может варьировать в значительных пределах от одной цистерны к другой (см. рисунок ниже). Поскольку этот маршрут пролегает через неприятельскую территорию, машина и водитель сбрасываются на парашютах. Они приземляются у одной из цистерн, заправляются и начинают объезд. Бензобак машины растягивающийся: он может вместить любое количество горючего независимо от того, какой ёмкости цистерна ему встретится на пути.

Откуда должна начать путешествие машина, чтобы успешно объехать весь маршрут?

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

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

Предлагаю читателям самим поразмыслить и открыть секрет. Разумеется, речь идёт об алгоритме. Требуется шаг за шагом описать процедуру, в результате выполнения которой можно найти по крайней мере один заправочный пункт, где машина может начать (и завершить) свою патрульную поездку. Алгоритм должен также указывать направление, в котором следует двигаться машине. Ошибка в направлении может привести к катастрофе. Лучшие ответы к этой задаче будут опубликованы в одном из ближайших номеров журнала.

В начале статьи я обещал дать ответ на задачу о двух поездах и пчеле. Интересные головоломки часто отличаются тем, что вводят в заблуждение решающего, в особенности когда задача имеет простое решение. Описывая бесконечный процесс, в котором пчела мечется между двумя поездами, я намеренно пытался запутать читателей. Чтобы решить задачу, необходимо лишь понять, что пчела находится в полёте ровно столько времени, сколько требуется поездам для того, чтобы встретиться. Половину расстояния между Задаченском и Решенском они преодолевают ровно за час. Следовательно, пчела, скорость полёта которой всегда равна 90 км/ч, пролетит 90 км.

С этой задачей связана одна легенда, за правдивость которой я, впрочем, не могу поручиться. Говорят, что в своё время кто-то задал эту задачку Джону фон Нейману, одному из величайших математиков XX столетия. Он тотчас ответил:

— Конечно, 90 километров.

— Я так и знал, — сказал спрашивающий его, — что вы найдёте лёгкий способ.

— Какой лёгкий способ? — сказал фон Нейман.

Оказывается, он просуммировал в уме бесконечный ряд. [Ещё один пример вычислительных способностей фон Неймана. — E.G.A.]