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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

Глава 26. ЗАНИМАТЕЛЬНАЯ ЛОГИКА

Слова Шерлока Холмса: «Сколько раз я говорил вам, отбросьте все невозможное, тогда то, что останется, и будет ответом, каким бы невероятным он ни казался», — могли бы послужить эпиграфом к этой главе.

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

Чаще всего встречается тип задачи, который любители головоломок иногда называют «задачей о Смите — Джонсе — Робинсоне» (по аналогии со старой головоломкой, придуманной Г. Дьюдени).

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

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

В дальнейшем каждого пассажира мы будем почтительно называть «мистер» (м-р).

2. М-р Робинсон живет в Лос-Анджелесе.

3. Кондуктор живет в Омахе.

4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже.

5. Пассажир — однофамилец кондуктора живет в Чикаго.

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

7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.

Как фамилия машиниста?

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

Рис. 139 Две таблицы к задаче о Смите, Джонсе и Робинсоне.

В каждую клетку впишем 1, если соответствующая комбинация допустима, или 0, если комбинация противоречит условиям задачи. Посмотрим, как это делается. Условие 7, очевидно, исключает возможность того, что Смит кочегар, поэтому в клетку, стоящую в правом верхнем углу левой таблицы, мы вписываем 0. Условие 2 сообщает нам, что Робинсон живет в Лос-Анджелесе, поэтому в левый нижний угол таблицы мы вписываем 1, а во все остальные клетки нижней строки и левого столбца — 0, чтобы показать, что м-р Робинсон не живет в Омахе или в Чикаго, а м-р Смит и м-р Джонс не живут в Лос-Анджелесе.

Теперь нам придется немного подумать. Из условий 3 и 6 известно, что специалист по математической физике живет в Омахе, но мы не знаем его фамилии. Он не может быть ни м-ром Робинсоном, ни м-ром Джонсом (ведь тот забыл даже элементарную алгебру).

Следовательно, им должен быть м-р Смит. Это обстоятельство мы отметим, поставив 1 в среднюю клетку верхней строки правой таблицы и 0 — в остальные клетки той же строки и пустые клетки среднего столбца. Третью единицу можно вписать теперь только в одну клетку: это доказывает, что м-р Джонс живет в Чикаго. Из условия 5 мы узнаем, что кондуктор тоже носит фамилию Джонс, и вписываем 1 в центральную клетку левой таблицы и 0 —во все остальные клетки средней строки и среднего столбца. После этого наши таблицы приобретают вид, показанный на рис. 140.

Рис. 140 Таблицы, изображенные на рис. 139, после предварительного заполнения.