Глава 24. Мартышка и кокосовые орехи

 

9 октября 1926 года в газете «Сатердей ивнинг пост» был напечатан небольшой рассказ Б. Э. Уильямса под названием «Кокосовые орехи». Сюжет этого рассказа сводился к тому, что некий строительный подрядчик хотел во что бы то ни стало помешать своему конкуренту получить важный заказ. Находчивый клерк подрядчика, зная страсть конкурента к занимательной математике, подсунул тому задачу настолько захватывающего содержания, что бедный конкурент, всецело поглощенный ее решением, забыл подать заявку в установленный срок и упустил контракт.

Вот эта задача в том виде, как ее сформулировал клерк из рассказа Уильямса.

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

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

Через некоторое время проснулся другой «робинзон» и сделал то же самое. У него тоже остался один лишний орех, и он отдал его мартышке. И так один за другим поступили все пятеро потерпевших кораблекрушение. Каждый из них взял себе одну пятую орехов из той кучи, которую он нашел при пробуждении, и каждый отдал один орех мартышке. Утром они поделили оставшиеся орехи, и каждому досталось поровну — по одной пятой. Разумеется, каждый из матросов не мог не знать, что части орехов не хватает, но так как у каждого из них совесть была одинаково нечиста, то никто ничего не сказал. Сколько кокосовых орехов было первоначально?

В рассказе Уильямса ответа не давалось. Говорят, что уже в течение первой недели после опубликования рассказа редакция «Сатердей ивнинг пост» получила около 2000 писем. Джордж X. Лоример, занимавший в то время пост главного редактора газеты, направил Уильямсу следующую историческую телеграмму: Ради бога, сообщите, сколько было орехов. В редакции творится черт знает что.

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

Задачу о кокосовых орехах придумал не Уильяме. Он лишь видоизменил уже известную до него задачу, чтобы сильнее запутать ее. Более старая версия задачи почти полностью совпадает с приведенной в рассказе Уильямса. Единственное различие заключается в том, что утром при окончательном разделе орехов в старом варианте задачи один орех снова оказывается лишним и достается мартышке, в то время как в рассказе окончательный раздел производится точно, без остатка. Некоторые диофантовы уравнения имеют лишь одно решение (например, уравнение х2 +2 = у3); другие допускают конечное число решений, третьи (например, уравнение х3 + у3 = z3) не имеют ни одного решения. Задача о кокосовых орехах и в изложении Уильямса, и в формулировке его предшественников допускает бесконечно много решений в целых числах.

Наша задача состоит в том, чтобы найти среди них наименьшее положительное число.

Более старый вариант задачи можно свести к следующим шести неопределенным уравнениям:

N = 5A + 1, 4C = 5D + 1,

4А = 5В + 1, 4D = 5E + 1

4B = 5C + 1, 4E = 5F + 1

Смысл каждого из этих уравнений очевиден: имеющееся количество орехов делят на пять равных частей (причем эту операцию проделывают шесть раз). Буква N означает первоначальное число орехов, буква F — число орехов, которое получил каждый моряк при окончательном разделе, единицы в правых частях уравнений — те орехи, которые достались мартышке, а каждая из букв — некоторое (пока неизвестное) целое положительное число.

С помощью хорошо известных из алгебры приемов эти уравнения нетрудно свести к одному диофантову уравнению с двумя неизвестными:

1024N = 15 625F+11529.

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

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

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

Очевидно, что небольшого положительного значения N, которое бы удовлетворяло условиям задачи, не существует. Может быть, простое решение удастся найти в отрицательных числах? Простым подбором можно без особого труда обнаружить удивительный факт: такое решение действительно существует. Это N = —4.

Убедимся в том, что это число в самом деле удовлетворяет всем условиям задачи.

Первый моряк подходит к куче, в которой имеется -4 кокосовых ореха, бросает один (положительный) кокосовый орех мартышке (получает мартышка свой орех до или после того, как вся куча будет разделена на пять частей, роли не играет). Таким образом, в куче оказывается —5 орехов. Это количество он раскладывает на пять кучек, по —1 ореху в каждой. Затем он прячет —1 орех, после чего остается —4 кокосовых ореха—ровно столько, сколько было вначале! Следующий моряк проделывает тот лее ритуал с несуществующими орехами, и после окончательного раздела «имущества» у каждого моряка оказывается по —2 ореха. В самом лучшем положении при таком «пополнении запасов наоборот» оказывается мартышка: она умчится, получив свои +6 орехов! Чтобы найти ответ, то есть наименьшее целое положительное число, удовлетворяющее данным задачи, нам остается только прибавить 15 625 к —4 и получить искомое решение: 15 621.

Этот же подход к задаче позволяет сразу же дать общее решение для случая п моряков, каждый из которых, разделив лежащие перед ним орехи на п равных частей, берет себе одну n -ю. Когда моряков четверо, мы начинаем с —3 кокосовых орехов и прибавляем 4⁵. Если моряков шестеро, мы начинаем с —5 орехов и прибавляем 6⁷. Аналогично можно поступать и при других значениях n.

Рассуждая более формально, можно записать, что первоначальное число кокосовых орехов равно k(nⁿ+1) — m(n — 1), где n — число людей, m — число орехов, отдаваемых мартышке при каждом разделе, а k — произвольное целое число, называемое параметром.

Когда n = 5, а m = 1, наименьшее положительное решение (в целых числах) мы получим, положив параметр к равным 1.

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

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

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

* * *

Если использование «отрицательных» кокосовых орехов для решения старого варианта задачи Уильямса кажется не вполне законным, то по существу тот же самый трюк молено проделать, выкрасив четыре кокосовых ореха в синий цвет. Впервые раскрашивание как способ решения задачи было открыто еще в 1912 году профессором Н. Эннингом. В его задаче 3 человека делили между собой яблоки. Применительно к задаче о кокосовых орехах способ Эннинга заключается в следующем.

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

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

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

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

Тем, кого интересует стандартный метод решения диофантовых уравнений первой степени с помощью непрерывных дробей, можно порекомендовать четкое изложение этого метода в книге Элен Меррил.[45] Его полезно знать всем любителям занимательных задач, поскольку многие известные головоломки основаны на уравнениях именно такого типа (см., например, задачу 8 в главе 29). Существуют и другие, весьма разнообразные методы решения задачи о кокосовых орехах, в частности один из методов использует числовую систему с основанием 5, но все они слишком сложны для того, чтобы на них стоило останавливаться.

 

Ответы  

Число кокосовых орехов в принадлежащем Уильямсу варианте задачи равно 3121. Из разбора старой задачи известно, что 5⁴ — 4 = 3121 есть наименьшее число орехов, которое можно пять раз делить на пять равных долей, отдавая при каждом делении один кокосовый орех мартышке. После пятикратного деления останется 1020 орехов. Это число делится на 5 нацело, что и позволяет произвести шестое деление на пять равных частей так, чтобы обезьяна не получила ни одного ореха.

В этом варианте задачи более общее решение записывается в виде двух диофантовых уравнений. При нечетном числе людей n следует брать уравнение

Число кокосовых орехов = (1 + nk)nⁿ — (n — 1),

при четном —

Число кокосовых орехов = (n — 1+nk)nⁿ — (n — 1).

Величина к и в том и в другом уравнении означает параметр, который может принимать любые целые значения. В задаче Уильямса число людей равно 5 (нечетное число), следовательно, 5 следует подставить вместо п в первое уравнение. Чтобы получить наименьшее положительное решение, параметр к следует выбрать равным 0.

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

 

Глава 25. ЛАБИРИНТЫ

 

В одном из древнегреческих мифов рассказывается о единоборстве юного Тезея с чудовищем Минотавром, обитавшим в кносском лабиринте на Крите. Выбраться из лабиринта Тезею помог клубок ниток, подаренный ему Ариадной. Лабиринты — архитектурные сооружения со сложными коридорами, которые строились для того, чтобы приводить в трепет непосвященных, — в древнем мире отнюдь не были редкостью. Геродот описывает египетский лабиринт, в котором было 3000 комнат. Довольно простой лабиринт изображен на монетах из Кносса; более сложные узоры в виде лабиринтов встречаются в рисунках римских мостовых и на одеждах древнеримских императоров. Такими же узорами украшали стены и полы многих соборов континентальной Европы во времена средневековья.

В Англии самым знаменитым архитектурным лабиринтом была беседка Розамунды. Повторно она была построена в вудстокском парке в XII веке королем Генрихом II, который попытался спрятать в этом лабиринте возлюбленную Розамунду Прекрасную от своей супруги Элеоноры Аквитанской. Предание рассказывает, что нить Ариадны помогла Элеоноре проникнуть в центр лабиринта, где ослепленная ревностью королева заставила несчастную Розамунду принять яд. Легенда эта поразила воображение многих авторов. На ее сюжет написал оперу Эддисон, а драматическая поэма Суинберна «Розамунда» представляет собой, по-видимому, наиболее впечатляющую версию.

Любопытно, что в Англии не принят распространенный на европейском континенте обычай украшать полы соборов мозаичными лабиринтами. Вместо этого англичане часто выкладывали лабиринты из дерна рядом с церковью. Прохождение такого лабиринта как бы являлось частью религиозного ритуала. Эти «причудливые лабиринты в пышной зелени», как назвал их Шекспир, были широко распространены в Англии вплоть до XVIII века. Садовые лабиринты из высоких кустарников, предназначенные исключительно для развлечений, вошли в моду в эпоху позднего Возрождения. В Англии самый известный лабиринт из живых изгородей, через который и по сей день пытаются отыскать путь сконфуженные туристы, был сооружен в 1690 году при дворце Вильгельма Оранского в Хэмптон-Корте. План этого лабиринта в его современном виде показан на рис. 136.

 

Рис. 136 План лабиринта из живых изгородей в Хэмптон-Корте.

 

В США единственный лабиринт из кустарников, имеющий историческую ценность, был создан лишь в XIX веке членами немецкой протестантской секты, поселившимися в небольшом городке Гармония (штат Индиана). (Теперь этот городок носит название Новая Гармония. Его дал городку в 1826 году шотландский социалист-утопист Роберт Оуэн, основавший там утопическое поселение.) Лабиринт в Гармонии, подобно средневековым лабиринтам, украшавшим полы соборов, символизирует змееподобные извивы греха и трудности удержания на праведном пути. Восстановлен он был в 1941 году. К сожалению, его первоначальный план не сохранился, и лабиринт был создан по совершенно новой схеме.

С математической точки зрения лабиринт представляет собой топологическую задачу. Если его план нарисовать на куске резины, то правильный путь от входа в лабиринт до цели будет топологическим инвариантом, то есть останется правильным, как бы ни сжимали и ни растягивали резину. Лабиринт, нарисованный на бумаге, можно решить очень быстро: достаточно заштриховать все тупики, тогда останутся только прямые пути к цели. Совсем иное дело, если вам, подобно королеве Элеоноре, нужно пробраться в лабиринт, планом которого вы не располагаете. Если у лабиринта имеется только один вход, а задача заключается в том, чтобы найти дорогу к единственному выходу, то ее всегда можно решить. Для этого достаточно, идя по лабиринту, все время одной рукой касаться стенки. Таким образом вы всегда найдете выход из лабиринта, хотя ваш путь вряд ли будет кратчайшим.

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

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

 

Рис. 137 Односвязный (слева) и многосвязный (справа) лабиринты.

 

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

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

Существует ли способ (или, говоря языком математики, алгоритм), позволяющий находить верный путь в любых лабиринтах, в том числе и в многосвязных с замкнутыми петлями вокруг цели?

Оказывается, существует. Лучше всего такой алгоритм сформулировал Э. Люка[46] (правда, честь изобретения алгоритма он приписывает М. Тремо). Суть алгоритма заключается в следующем.

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

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

Для читателей, которые захотят испробовать предлагаемый метод на более сложном лабиринте, на рис. 138 показан план многосвязного лабиринта, который построил в своем саду английский математик У. У. Роуз Болл. Цель указана точкой внутри лабиринта.

 

Рис. 138 Лабиринт в саду У. У. Роуза Болла.

 

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

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

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

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

Позднее научились строить и других роботов, умеющих находить дорогу в лабиринте. Одного из самых «хитроумных» из них сконструировал Ярослав А. Дейч из Оксфордского университета.

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

Робот Дейча умеет также находить кратчайшие пути в лабиринте и проделывать другие удивительные вещи.

Все эти устройства, безусловно, лишь первые шаги новой отрасли техники. Весьма вероятно, что будущие обучающиеся машины, обретя огромную мощь, станут выполнять самые неожиданные функции среди автоматов космического века. Лабиринты и космический век — эта комбинация снова возвращает нас к греческому мифу, уже упоминавшемуся в начале этой главы. Лабиринт Минотавра был построен для царя Миноса никем иным, как Дедалом, тем самым Дедалом, который изобрел крылья и чей сын Икар погиб, поднявшись слишком высоко в небо. «Столь хитро придуманного лабиринта еще не видели на свете ни до, ни после, — пишет Н. Хоуторн, пересказывая миф о Дедале. — Ничто не может сравниться с ним по сложности, разве что мозг такого человека, как Дедал, чей разум создал его, или сердце обыкновеннейшего из людей…»