Мартин Гарднер - Математические головоломки и развлечения

• Название: Математические головоломки и развлечения
• Автор: Мартин Гарднер
• Издательство: "Мир"
• Жанр: Развлечения
• Год: 1999
• ISBN: 5-03-003340-8

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

---

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

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

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

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

Ответы

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

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

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

при четном —

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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