Математика лабиринта

DjVu

      ПРЕДИСЛОВИЕ
      «Интенсификация» и «компьютер»...
      С этими словами мы сегодня сталкиваемся все чаще и чаще -не правда ли? И наверняка вы .уже заметили, что, как правило, они стоят рядом. Какая же между ними связь?
      Интенсификация сегодня — это повышение производительности труда за счет внедрения новейшей техники, достижений научно-технического прогресса.
      А при чем здесь компьютер? А вот при чем. По существу он — тот же станок, только особый, обрабатывающий не дерево или металл, а информацию.
      С увеличением масштабов производства, с ростом сложности производственных процессов объем информации резко возрастает. Человек уже не в состоянии собрать и проанализировать все необходимые для работы сведения. Из множества возможных решений он часто выбирает далеко не самое лучшее, так как человеческий мозг не может быстро просчитать последствия каждого из них. А любое отклонение от наилучшего решения — это потери для всего общества.
      Многие производственные процессы сегодня требуют высокой точности, такой скорости обработки информации, которые человеку не доступны. Научные исследования в биологии и физике, экологии и экономике, да практически во всех областях науки и техники, также требуют быстрой обработки колоссального количества данных.
      Таким образом, в современной научно-технической рево люции компьютер выступает в качестве одного из главных действующих лиц, поскольку открывает индустриальную эру в переработке информации. Именно поэтому интенсификация производства подразумевает и компьютеризацию.
      Итак, компьютеры заняли сегодня в жизни общества особое положение, но, как бы велика ни была их роль, нельзя забывать о значении математики для плодотворной их работы. На компьютеры мы должны смотреть не как на цель, а как на средство доводить исследования до конца, до возможности применения математической теории явления, до практического использования. Ведь прежде чем ввести в действие компьютер, необходимо провести собственно математическое исследование явления, составить программу для компьютера и лишь после этого ввести ее в действие. Так, компьютер не смог бы управлять полетом самолета, если бы предварительно не были
      созданы математические модели соответствующих процессов и затем превращены в программы — алгоритмы, записанные на понятном для компьютера языке.
      Знания, умения и навыки, которые позволяют успешно использовать компьютер при решении разнообразных задач, представляют собой важнейшие компоненты компьютерной грамотности, именуемой нередко «второй грамотностью».
      Чтобы овладеть компьютерной грамотностью, прежде всего необходимо научиться составлять алгоритмы решения различного рода задач. (Ведь компьютер и предназначен для осуществления алгоритма — детального пошагового набора указаний по решению некоторого типа задач.) Прекрасным практикумом по составлению алгоритмов являются лабиринтные задачи, предлагаемые в этой книге Заметим также, что решение многих лабиринтных задач имеет непосредственный выход к важнейшим разделам математики: топологии, теории информации, игр, исследования операций, вероятностей и др.
      Предлагаемые в книге лабиринты даны в игровой форме. И зто не случайно. Ведь игры старше любой науки, они ровесники человечества. Когда на Земле появился homo sapiens (человек разумный), он немедленно стал и homo ludens (человеком играющим.), постоянно попадая в ситуации, которые современные ученые определили как игровые.
      Искусство игры требует не только интеллектуальных навыков, но и мастерского применения алгоритма ее исполнения. Игра мобилизует наши знания, дисциплинирует мышление.
      Один из творцов математического анализа Г. В. Лейбниц (1646 — 1716) в работе «Примечание к некоторым играм» (1710 г.) писал: «Мы часто замечали, что люди проявляют более всего изобретательности в играх, и поэтому математические игры заслуживают внимания, не сами по себе, а потому, что развивают находчивость».
      Следовательно, наши лабиринтные прогулки будут не только интересными, но и полезными тренажерами воспитания качеств, необходимых представителям многочисленных земных и космических профессий. Конечно же, всякая задача или игра становится по-настоящему привлекательной только после того, как попробуешь ее решить сам. Поэтому, в основной своей части, это книга не для развлекательного чтения, а активной творческой работы.
     
      ...История математики — не только история развития понятий, но одна из частей истории человеческой деятельности..
      Д. Стройк
     
      ЧТО ТАКОЕ ЛАБИРИНТ?
      Лабиринт... Как таинственно звучит это слово, сколько чудесных мифов и преданий, героических и трагических реальных событий связано с ним!
      Лабиринтами (от греч. Xapipiyog) античные авторы называли сооружения с многочисленными сложно соединяющимися комнатами, из которых трудно найти выход. Первый рассказ о лабиринте находим в «Истории» древнегреческого историка и путешественника Геродота (ок. 484--425 до н. э.), где описана история создания огромного Фаюмского лабиринта на севере Египта.
      В центре Фаюмской области один из правителей XVIII династии египетских фараонов Аменемхет III (ок. 1456 1419 до н. э.) возвел пирамиду, заупокойный храм при которой был построен в виде лабиринта. Вот что писал о нем Геродот-«Я видел этот лабиринт: он выше всякого описания. Ведь если бы собрать все стены и великие сооружения, воздвигнутые эллинами, то в общем оказалось бы, что на них затрачено меньше труда и денежных средств, чем на один этот лабиринт А между тем храмы в Эфесе и на Самосе — весьма замечательны. Конечно, пирамиды — это огромные сооружения, и каждая из них по величине стоит многих творений (эллинского строительного искусства), вместе взятых, хотя и они также велики. Однако лабиринт превосходит (размерами) и эти пирамиды. В нем двенадцать дворов с вратами, расположенными одни против других, причем шесть обращены на север, а шесть на юг, прилегая друг к другу. Снаружи вокруг них проходит одна-единственная стена. Внутри этой стены расположены покои двух родов: одни подземные, другие над землею, числом 3000, именно по 1500 тех или других. По наземным покоям мне самому пришлось проходить и осматривать их, и я говорю о них как очевидец. О подземных же покоях знаю лишь по рассказам: смотрители-египтяне ни за что не желали показать их, говоря, что там находятся гробницы царей, воздвигших этот лабиринт, а также гробницы священных крокодилов. Поэтому-то я говорю о нижних покоях лишь понаслышке. Верхние же покои, которые мне пришлось видеть, превосходят (все) творения рук человеческих. Переходы через покои и извилистые проходы через дворы, будучи весьма запутанными, вызывают чувство бес-
      конечного изумления: из дворов переходишь в покои, из покоев в галереи с колоннадами, затем снова в покои и оттуда опять во дворы.» (Г е р о д о т. История. — Л.: Наука, 1972. — С. 126 — 127).
      В 111 в. до н. э. греки составили список грандиознейших сооружений — «семи чудес света» — и включили в него знаменитый лабиринт. Но лишь в наши дни стало известно, что Аменемхет III соорудил два лабиринта.
      В 1982 г. газета «Правда» в заметке «Пирамиды и лабиринты» сообщала: «Интересное открытие сделали археологи при раскопках в районе Саккары под пирамидой Аменемхета III... . В результате кропотливых работ обнаружена погребальная камера, в которой находились три саркофага с мумиями. По мнению ученых, это — останки двух жен Фараона и его дочери, похороненных в так называемой «усыпальнице цариц». Там же найден обшитый золотыми листами сундук с амулетами, украшениями и предметами домашней утвари.
      Это примечательно и тем, что раскопки, приведшие к этому открытию, проходили в сложных условиях. Дело в том, что при Аменемхете III строились пирамиды с замысловатыми коридорами, с десятками тупиков, ям-ловушек и ложных камер. Так, близ пирамиды в Фаюме, где похоронен он сам, был сооружен погребальный храм с такими запутанными ходами, что еще древние греки называли его «лабиринтом». Не удивительно, что долгое время археологам не удавалось разгадать тайну саккарской пирамиды, хотя такие попытки предпринимались неоднократно. Впрочем, как считают ученые, вполне возможно, что нынешняя находка — не последняя» (П ересада В. Пирамиды и лабиринты. Правда. 1982. — 10 марта. — С. 6).
      Грандиозность пирамид символизировала вечность и неизменность верховной власти. О том гласила и надпись на фронтоне главного сооружения: «Все на земле боится
      времени, а время боится пирамид». Эти каменные исполины создавались ценой неисчислимых жертв: 100 ООО рабов в течение 20 лет осуществляли замысел деспота.
      Первые известные рисунки лабиринтов в Египте сохранились на печатях из Мемфиса, относящихся к эпохе строительства великих пирамид (3000 лет до н. э.) (рис. 1.1). Справа в лабиринте изображен фараон IV династии. Выходит, что идея лабиринта существовала в Египте задолго до сооружения лабиринта Аменемхета III.
      Один из прекраснейших древнегреческих мифов также связан с лабиринтом.
      Критский царь Минос приказал знаменитому художнику и архитектору Дедалу построить лабиринт. В этот лабиринт, с бесчисленными коридорами, тупиками и переходами, Минос поселил Минотавра - кровожадное чудовище с человеческим телом и головой быка — и потребовал от афинян, убивших его сына, раз в 9 лет присылать на съедение чудовищу семерых сильнейших юношей и семерых красивейших девушек. Их отводили в лабиринт, и юные афиняне, блуждая там, становились жертвами Минотавра. Когда афиняне готовили кровавую дань в третий раз, сын афинского царя Эгея, Тесей, задумал освободить родной город от позорной и жестокой обязанности. Вместе с очередной группой жертв Минотавра он отбыл на Крит с целью убить чудовище. Корабль в знак траура отплыл под черным парусдм с условием, что в случае победы спасенные афиняне возвратятся под белым парусом, имевшемся на корабле.
      Дочь Миноса Ариадна полюбила мужественного Тесея и решила помочь ему в уничтожении Минотавра. Взяв у Дедала волшебный клубок ниток, с помощью которого можно было найти выход из лабиринта, Ариадна передала его Тесею. Он привязал у входа в лабиринт конец нити и отправился на поиски чудовища, постепенно разматывая клубок. (В других вариантах этого мифа клубок сам катился до того отдаленного места, где жил Минотавр.) Поединок закончился победой Тесея, который затем при помощи нити Ариадны вышел из лабиринта и вывел оттуда всех обреченных.
      На обратном пути в Афины герой забыл сменить парус на белый. Эгей, увидев черный парус — знак гибели сына, бросился в море, которое поэтому и стали называть Эгейским Узнав о роли Дедала в победе Тесея, Минос заключил художника вместе с сыном Икаром в лабиринт. Они были освобождены женой Миноса. Сделав крылья из скрепленных воском перьев, Дедал вместе с Икаром улетели с острова. В пути Икар поднялся слишком высоко, солнце растопило
      воск, и юноша упал в море, которое впоследствии назвали Икарийским.
      Миф о критском лабиринте преисполнен веры в могущество человека, отстаивающего справедливость в борьбе со злом.
      В 1900 г. английский археолог Артур Эванс провел раскопки на северном побережье острова Крит, где обнаружил воспетый в Гомеровой «Одиссее» и многократно упоминаемый в мифах главный город острова - Кносс и кносский дворец-лабиринт. Его архитектура поражает замысловатым чередованием самых разнообразных строительных элементов и отсутствием какой бы то ни было четкости и симметрии (рис. 1.2). На каждом шагу множество неожиданных переходов, причудливых лестниц и коридоров.
      В 1941 г. Крит захватили немецкие фашисты, и музей дворца-лабиринта сгорел вместе со всеми находками экспедиции Эванса.
      В древности изображение лабиринта было своеобразной эмблемой Крита. Очертания лабиринтов встречаем на печатях, которыми скреплялись государственные документы, а также на монетах (рис. 1.3).
      Очевидно, что на таких важных государственных атрибутах, как печати и деньги, изображались символы, несущие информацию о каких-то очень важных событиях.
      Ученые считают, что в мифе о Тесее и Минотавре отражены реальные драматические эпизоды династической или дворцовой борьбы за власть.
      Один из вариантов исторической предпосылки мифа предложил В. И. Левин в книге «Свидетели Каповой пещеры» (М.: Дет. лит., 1982. — 222 с.)
      И на территории нашей страны описаны удивительные лабиринты. Еще в 1592 г. русские дипломаты Г. Б. Васильчи-ков и С. Г. Звенигородский писали с северной окраины России: «А в Веренге, на побоище немецком... на славу свою принесши с берегу камень в вышину от земли есть и нынче больше сажени, а около него подале выкладено каменьем как бы городовой оклад в 12 стен, а назван был у него тот оклад Вавилоном...» [20,5].
      Это, вероятно, первое упоминание о памятниках неизвестной ранее культуры, явившихся еще одной вариацией идеи лабиринта. На севере нашей страны — на Кольском полуострове, Соловецких островах, в Карелии на побережье Белого моря, а также в Англии, Дании, Германии, Швеции, Норвегии и Финляндии открыли более ста лабиринтов — подковообразных, круглоспиральных, почкообразных и концентрически круговых. На рисунке 1.4. изображены:
      I. Подковообразные лабиринты — лабиринты так называемого «классического типа»: (1), Швеция; (2), Финляндия; (3), Англия; (4), Карельский полуостров, СССР.
      К этой группе относятся дерново-растительные лабиринты: (5), Англия; (6 — 8), Соловецкие острова; (9), ГДР. В центре таких сооружений непременно помещалась каменная пирамидка.
      II. Круглоспиральные лабиринты: (10), (13), Соловецкие острова; (11), Греция; (12), Югославия; (14), Англия.
      III. Почкообразные лабиринты — взаимно вписанные спирали: (15), Соловецкие острова; (16), (17), Кольский полуостров.
      IV. Концентрически-круговые лабиринты: (18), Кольский полуостров; (19), (20), Соловецкие острова.
      На этом же рисунке представлены аналоги каменных лабиринтов; (21), подковообразный лабиринт на кносских серебряных монетах III — I вв. до н. э.; (22), лабиринт в одном из соборов на территории Финляндии; (23), лабиринт на северорусском скальне. Архангельская область.
      Знаменитые каменные лабиринты — самые древние и самые загадочные памятники Соловецкого музея-заповедника. Всего в мире их известно около 60, в том числе на Соловецких островах — 33.
      Северные каменные лабиринты — одна из сложнейших археологических загадок. Построены они в конце II — начале I тысячелетия до н. э. и, вероятнее всего, имели культовое назначение. Неясным остается то, почему одинаковые архитектурные решения лабиринтов встречаются в разных местах земного шара. Например, схема спиралей одного из лабиринтов на Кольском полуострове почти полностью повторяет план лабиринта, изображенного на кносских серебряных монетах III — 1 вв. до и. э.; аналогичные лабиринты ученые обнаружили в наскальных изображениях - на юге Аргентины, в рисунках индо-тибетских народов (1.5), на глиняных табличках из Шумера.
      Древние люди изображали окружающий их мир в виде круга или концентрических окружностей, а мир мертвых — в виде спирали или лабиринта. Например, аборигены Австралии изображали на могилах лабиринты как символ переселения умершего в иной непостижимый мир (1.6).
      Каковы же истоки идеи лабиринта?
      Чтобы ответить на этот вопрос, обратимся к временам, отдаленным от нас более чем на 3,5 миллиарда лет, когда возникали удивительные лабиринты, созданные самой природой, — пещеры. Многие из них были жилищами первобытного человека и до сих пор сохраняют следы его пребывания; орудия труда, быта, украшения. Среди таких пещер известная пещера Альтамира (Испания) с росписями на потолке, Кунгурская ледяная пещера на Урале, Агтелекские сталактитовые пещеры Венгрии, пещеры в Лазурном гроте на итальянском острове Капри. В США обнаружено около одиннадцати тысяч пещер, в Италии — более восьми тысяч, во Франции — семь, в Югославии — свыше пяти тысяч.
      Около двух миллионов лет назад образовалась сложная система подземных пустот-лабиринтов на территории Тернопольской области.
      Неподалеку от Бахчисарая находится один из наиболее сохранившихся и наиболее доступных для обозрения и изучения пещерных городов Крыма — город Чуфут-Кале.
      Легендарна история киевских пещер, служивших убежищем человеку уже около 4000 лет назад.
      Многие легенды об этих пещерах перекликаются с древне греческими мифами. Например, легенда о Змеиной пещере вблизи Кирилловского монастыря повествует о том, что жил в ней когда-то жестокий змий-людоед, требовавший от киевлян дани в виде живых людей. Славный киевский богатырь Никита Кожемяка сразился со змием и победил его.
      Киевские пещеры хранят еще много тайн. В 1984 году сотрудники Института археологии АН СССР открыли в подземном лабиринте Киево-Печерской лавры неизвестную до сих пор галерею с настенными надписями, датированными XII в (Подробнее см.: Б i л о д i д А., Харламов В. I повщав иапис НестеровоТ печери11Знания та праця. — 1984. — № 9. — С. 22 — 23.)
      Используя идею лабиринта, люди сооружали крепости и целые города. Именно такой крепостью-лабиринтом было Тигашевское городище, существовавшее в Волжской Болгарии в X в. (1.7). Лабиринты сооружали вокруг замков и в их подземельях.
      План лабиринта знал только владелец замка и некоторые его. приближенные. В случае опасности они прятали там свои сокровища и спасались сами.
      Большие подземные лабиринты сооружали под многими городами в средние века. Некоторые из них сохранились до наших дней. Например, в городе Брно (ЧССР) несколько лет назад на одной из улиц в историческом центре города внезапно провалился участок мостовой и появились трещины в кладке соседних зданий. Тогда же, в 1978 году, начались работы по выявлению причин этого происшествия и предотвращения дальнейшей осадки почвы. Оказалось, что под центральной частью Брно находится разветвленный лабиринт катакомб, ходов, подземных залов. Все они появились еще в средние века и были прорыты в целях защиты города от врагов.
      Некоторые народы сооружали и сооружают жилища в форме лабиринта. Вот отрывок из книги Л. М. Минца «Последние из каменного века»: «Среди голых гор Северного Камеруна рассыпаны деревни племени матакамов. От деревни до деревни дня два пути, а то и больше. Гуще селиться люди не могут — им нечем было бы себя прокормить. Каждая деревня обнесена высокой и толстой стеной. В этих местах строят надежно, чтобы не проникли в деревню непрошеные гости — ночной зверь или лихие люди, которые еще не так давно частенько встречались в этих местах. А из-за стены торчат острые конусы крыш из просяной соломы. Сгрудились они так плотно, что, кажется, налезают одна на другую в беспорядке. На самом же деле хижины стоят за стеной продуманно, по установившемуся издавна порядку: впритык, подперев друг друга глиняными своими боками, — жилые помещения, амбары, поднятые над землей на камнях, дом, где «проживает» бог — покровитель племени, «клуб», куда приходят вечером мужчины поговорить о жизни.
      Ни в одно из помещений деревни нельзя войти, миновав другие, ибо вход во все дома один. Получается что-то вроде гигантской квартиры с бесчисленными смежными комнатами. Так все это запутано, что посторонний человек непременно заблудится здесь и уж, во всяком случае, не останется незамеченным.
      Сами жители, естественно, знают план лабиринта, как свои пять пальцев. Они ведь здесь выросли и большую часть жизни проводят в своей квартире-деревне. У каждой хижины есть свое имя: Мутуки, Аболеке, Ква и так далее. И каждый матакам зиает: за Мутуки всегда следует Аболеке, а из Ква можно пройти- в Сон только через Нута и Гвина.
      Есть у жилого лабиринта и другие достоинства: в любое место можно пройти под крышей. А в жару или в сезон дождей это преимущество немалое.
      Если разрастется население деревни и придется основывать другую, в ней будет все точно так же: за Мутуки — Аболеке, за ней — Ква. Соплеменник в любой деревне матакамов разберется. А чужому и знать не надо, для того и лабиринт построен» (М.: Просвещение, 1981. — С. 10).
      Многие племена Мали, Зимбабве и других стран Африки и сегодня сооружают свои жилища по такому же принципу.
      Итак, человек формировал идею лабиринта, находя прообразы ее в тех объектах окружающего мира, которые он включал в свою практическую деятельность, все глубже проникая в тайны природы. Например, наблюдая смесь прозрачных магнитной и немагнитной жидкостей в магнитном поле, мы увидим, что каждая частица магнитнойжидкости отталкивает другие частицы и жидкость стремится раздробиться на мелкие порции. Но поскольку всякое деление сопряжено с затратами энергии, жидкость «идет на компромисс» и в результате возникает неустойчивая мало организованная структура — лабиринт (1.8).
      В конце 50-х годов нашего столетия в некоторых химических соединениях окиси железа с окисями других металлов обнаружили «магнитные пузырьки», изолированные однократно намагниченные подвижные области (домены) ферромагнетика или ферримагнетика — цилиндрические магнитные домены. Их получают в тонких плоскопараллельных пластинках (пленках) монокристаллических ферримагнетиков. В отсутствии внешнего подмагничивающего поля доменная структура имеет неупорядоченный лабиринтообразный вид (1.9, слева). При наложении подмагничивающего поля домены, не имеющие контакта с краями пластины, стягиваются (1.9, справа).
      Напрашивается вывод: идея лабиринта возникла как результат практического освоения человеком различных неупорядоченных объектов и их систем.
      На следующих страницах подтвердим этот вывод, неоднократно обращаясь к нему при рассмотрении многих интересующих нас вопросов.
     
      СКРЫТАЯ ЭНЕРГИЯ ЛАБИРИНТА
      Заметим, что далеко не все лабиринтные структуры поддаются непосредственному наблюдению. Структурой именно такого рода является, например, модель развития индоевропейских языков (1.10), а также любой языковый (лингвистический) лабиринт.
      Действительно, язык — великолепное средство не только выражать мысли, но, как это ни парадоксально, и скрывать их.
      Древние греки, готовясь к важному военному походу, отправляли послов в Дельфы, в храм Аполлона, и вопрошали оракулов о воле богов. Так поступил и могущественный лидийский царь Крез (596 — 546 до н. э.), задумав войну против персидского царя Кира II. Оракулы ответили послам Креза: «Если царь пойдет войной против персов, то сокрушит великое царство». Уверенный в своей победе, Крез выступил против Кира II, но потерпел жестокое поражение и сам попал в плен. Кир II позволил Крезу еще раз направить послов в Дельфы, чтобы упрекнуть оракулов в обмане. Оракулы ответили, что не ошиблись, а вот Крез неправильно истолковал фразу «сокрушит великое царство», имелось в виду царство самого Креза.
      Двусмысленное предсказание явилось для Креза своеобразным языковым лабиринтом. Вообще зашифрованная каким-либо образом словесная информация представляет собой не что иное, как языковой лабиринт.
      Уже в глубокой древности были изобретены различные системы символов — коды (от лат. codex — свод законов) как средство засекречивания (кодирования), хранения и передачи информации.
      Коды разрабатывались в виде криптограмм. Вместе с кодированием, или шифрованием, развивалось и искусство дешифровки, или криптоанализа.
      В переводе на математический язык кодированием называется отображение произвольного множества А в множество конечных последовательностей (слов) в некотором алфавите, а декодированием — обратное отображение.
      Спартанцы, например, имели специальные приборы, кодировавшие важные сообщения. Знаменитый античный сатирик Аристофан (ок. 445 — ок. 385 до н. э.) в комедии «Ли-систрата» упоминает о Лаконском посохе — способе шифровки писем в Спарте. Текст писали на ремне или пергаменте, охватывающем посох в виде спирали, адресат читал его, намотав полученную шифровку на посох такой же длины и толщины.
      Интересно отметить, что изобретением тайных шифров и способов дешифровки занимались многие выдающиеся математики.
      Итальянский математик Д ж. Кардано (1501 — 1576) изобрел способ криптографии — «решетку Кардано». Эта решетка представляет собой лист плотной бумаги, в котором прорезаны прямоугольные отверстия постоянной высоты и переменной ширины, расположенные на разных расстояниях друг от друга. Шифровальщик клал решетку на чистый лист бумаги и в отверстиях писал текст сообщения так, что в каждом отверстии помещались либо буква, либо слог, либо целое слово. Затем решетка убиралась, а оставшиеся пробелы заполнялись произвольным набором букв. Именно он и был словесным лабиринтом, засекречивающим данное сообщение. Математики разработали требования, которым должна удовлетворять шифровальная решетка, чтобы каждая клетка квадрата в каком-то совмещении оказалась под «окошечком» решетки, причем по одному разу. Для квадрата 8X8 и набора поворотов на 90°, 180° и 270° существует 164 вариантов шифровальных решеток.
      Французский математик Ф. Виет (1540 — 1603) прославился как искусный дешифровщик. Франция вела тогда войну с Испанией. Испанские шпионы использовали чрезвычайно сложный шифр, состоящий из 500 знаков. Они были настолько уверены в недоступности шифра, что даже не беспокоились, когда отдельные секретные донесения попадали к французам. Французский король Генрих III попросил Виета раскрыть секрет шифра, и ученый справился с этой чрезвычайно сложной задачей. Два года французы перехватывали и читали шифровки испанских шпионов, что помогло им нанести ряд поражений испанской армии.
      Различные способы кодирования информации часто использовались и в научных целях. Например, итальянский ученый Г а л и л е й (1564 — 1642) свое открытие колец Сатурна зашифровал с помощью анаграммы (от греч. ava — пере — и ypappa — литера). Слово или словосочетание, образованное перестановкой букв другого слова или словосочетания. Анаграмма Галилея, состоявшая из 37 латинских букв, очень заинтересовала немецкого астронома И. Кеплера (1571 — 1630). Чтобы ее прочесть, нужно было найти единственную перестановку из всех возможных перестановок, количество которых определяется 35-значным числом. Кеплера не испугал такой сверхлабиринт. Выбросив две буквы, он составил из оставшихся фразу: «Слава вам, о, близнецы, щитоносное Марсово племя» — и решил, что Галилей открыл спутники Марса. На самом деле, Галилей с помощью анаграммы зашифровал такую фразу, относящуюся к Сатурну: «Высочайшую планету тройной наблюдал». Лишь спустя почти полвека нидерландский ученый X. Гюйгенс (1629 — 1695) открыл кольцо Сатурна и тоже зашифровал свою догадку анаграммой из латинских букв. Если переставить их в нужном порядке, то получится фраза: «Окружен кольцом тонким, плоским, нигде не подвешенным, наклоненным к эклиптике». Чтобы расшифровать эту тайнопись, нужно было бы сделать примерно 10 60 перестановок.
      Гюйгенс, открыв первый спутник Сатурна, Титан, определил, что время его обращения вокруг планеты равно 15 суткам, и составил по этому поводу анаграмму, которую послал своим коллегам. Один из них был выдающийся английский математик и большой мастер криптоанализа Дж. Валлис (1616 — 1703). Он расшифровал анаграмму Гюйгенса и ответил ему собственной анаграммой.
      Р. Бэкон (1214 — 1292) — один из самых ярких ученых средневековья, человек, широчайшие познания которого дали повод современникам звать его «удивления достойный», около 1249 года написал книгу «Письмо о тайнах искусства и природы и о ничтожности магии». Шесть с половиной столетий лучшие криптографы мира пытались разгадать, что зашифровал ученый в трех самых интересных ее главах. Неразгаданный текст оказался своеобразной анаграммой, с помощью которой Бэкон зашифровал химический состав черного пороха.
      Таинственные документы — излюбленный прием авторов фантастических и приключенческих произведений. Достаточно вспомнить «Матиаса Шандора», «Путешествие к центру Земли» и «Дети капитана Гранта» французского писателя К. Верна (1828 — 1905).
      В ромаие Жюля Верна «Дети капитана Гранта» в записке, извлеченной из бутылки, текст превращен в сложнейшую шифрограмму, допускающую 10 200 возможных прочтений.
      Рассмотрим еще одну шифрограмму: 52880681 (#9;48; (88;4(#?34;48)4#;161;: 188;#? Так кончается небольшой набор знаков на кусочке старого пергамента, случайно попавшегося на глаза большому любителю головоломок Леграну, герою рассказа Эдгара По «Золотой жук». К разгадке )той фразы ведет также сверхсложный лабиринт 10 18 возможных вариантов прочтения текста записки.
      Блестящий образец расшифровки тайнописи дал английский писатель А. Конан Дойл (1859 — 1930) в «Записках о Шерлоке Холмсе».
      В истории с пляшущими человечками, которую рассказал Холмс своему другу доктору Ватсону, преступник присылал избранной жертве странные записки с фигурками пляшущих человечков. Холмс определил, что перед ним шифр. Найдя ключ к нему, знаменитый сышик послал преступнику записку, написанную с помощью пляшущих человечков, которая означала «Приходи немедленно» и... преступник попал в руки правосудия.
      И конечно же, подлинными лингвистическими лабиринтами являются загадочные письмена древних народов. О захватывающих путешествиях по таким лабиринтам можно узнать из «Энциклопедического словаря юного филолога» [22].
      Отметим еще одно важное свойство лабиринта: с его помощью был найден метод изучения поисковой деятельности живых организмов. Рассмотрим его подробнее.
      В естественной среде живые организмы часто вынуждены преодолевать в пространстве всевозможные препятствия и запоминать сложные пути.
      Простейшие лабиринты, в которых проводился интересующий нас эксперимент, 7-образные. В начале опыта дождевых червей помещали на площадку (1.11, 1). Когда площадку ярко освещали, червь начинал двигаться, стремясь найти более удобное место. На развилке коридора он мог поворачивать влево или вправо. К левому коридору было подключено электрическое поле, а правый коридор приводил червя в затемненную и влажную камеру, где он чувствовал себя превосходно. В процессе многократного преодоления лабиринта и «принятия решения» о выборе коридора при разветвлении червь постепенно обучался поворачивать только в правый коридор. Другими словами, не имея никакой первоначальной информации об особенностях среды обитания, червь в процессе взаимодействия с окружающим миром вырабатывал целесообразный способ поведения в нем. Внезапное изменение среды делало поведение обученного червя нецелесообразным. Но через некоторое число безуспешных попыток найти в правом коридоре уютную камеру для отдыха червь впервые поворачивал в левый коридор. Шло переучивание. И снова наступала его адаптация к изменившейся среде.
      В другом експерименте (1.11, 2) в каждом из коридоров подопытное животное (нли насекомое) ждёт неприятных ощущений от раздражения электрическим током. Эти раздражения происходят с фиксированными вероятностями Рп и Рл (подробнее о вероятности см. с. 90), которые не изменяются в одной серии опытов. Например, на 10 опытов в правом коридоре электрический ток раздражает животное 7 раз, то есть Pn=1i, а в левом — только 3 раза — Рл= 1з- Целью эксперимента было определить, сможет ли животное научиться выбирать только тот коридор, в котором вероятность раздражения меньше. После некоторого периода обучения наступал момент, когда животное интуитивно правильно оценивало разницу в значениях Рп и Рл и принимало целесообразное решение по выбору маршрута движения к пище. При незначительной разнице в значениях вероятностей болевых раздражителей выбор пути движения происходил без заметных предпочтений. Например, муравьи после обучения преодолевают лабиринт с десятью разветвлениями:
      Опыты показали, что животные сначала медленно разведывали, изучали лабириит (1.12, 1), а затем с каждым разом преодолевали маршрут все быстрее, и, наконец, наступал момент, когда животные автоматически решали задачу, находя камеру с приманкой (1.12, 2).
      Не всех животных приходится «обучать» лабиринтным прогулкам. Летучая мышь, например, и без тренировок ловко ориентируется в темном лабиринте. Она посылает в пространство ультразвуки и ловит их отражение от возникающих на пути преград. Подробнее об этом вы можете прочесть в книге крупнейшего нидерландского этолога, лауреата Нобелевской премии Н. Тинбергена «Поведение животных» (М.: Мир, 1985. — 192 с.).
      Но опыты с животными не раскрыли алгоритм, которым пользуются они в поисках выхода из лабиринта. Пришлось подняться еще на одну ступень сложности и попробовать разобраться, как это будут делать машины.
      Американский ученый, один из создателей математической теории информации К. Шеннон (р. 1916), для обучения решению лабиринтных задач сконструировал мышь-робот — «Тесей». «Мышь» сначала последовательно изучает незнакомый лабиринт. При этом в случае выбора дальнейшего пути мышь не действует наугад, как поступал бы человек, а, двигаясь в одну определенную сторону, всегда выбирает ближайший коридор. После того как «мышь» нашла дорогу к цели, запоминающие устройства позволяют ей второй раз пройти через лабиринт без ошибок — идя к цели, она не заходит в тупики, хотя может прокладывать маршрут и не кратчайшим путем. (Живая мышь обучается отыскивать дорогу в лабиринте гораздо медленнее, поскольку использует
      метод проб и ошибок, и только после многократных успехов правильный путь закрепляется в ее памяти.)
      Сконструирован робот, который, обучившись в одном лабиринте, может перенести приобретенный опыт на любой другой аналогичный лабиринт, как ни была бы изменена длина и форма стенок. Он может находить также кратчайший путь в лабиринте и решать другие лабиринтные задачи.
      Конструкторы ЭВМ рассматривают роботов, умеющих находить дорогу в лабиринтах, как составную часть программы создания самообучающихся машин, то есть машин, способных, подобно живым организмам, извлекать ценную для себя информацию из опыта. Очевидно, что именно самообучающиеся машины — роботы - станут выполнять самые неожиданные и сложные виды работ в автоматизированных системах будущего.
      Лабиринты оказались удобным средством для изучения сложных механизмов памяти (1.13), а также поведения живого организма в экстремальных ситуациях.
      Конечно, механизмы этих сложных процессов моделируются сначала на поведении животных. Для этого используется лабиринт (1.14), который создает постоянный психоэмоциональный стресс.
      Идея лабиринта как неупорядоченной структуры пространства нашла многочисленные применения в технике. Например, в любой гидравлической системе наиболее ответственными элементами, обеспечивающими надежность и эффективность работы, являются уплотнения. Уплотнение это устройство, предотвращающее или уменьшающее утечку жидкости или газа через зазоры между деталями машины илн какого-либо иного сооружения, а также защищающее детали от проникновения грязи и пыли. Уплотнения бывают контактными и бесконтактными или лабиринтными. Уплотняющий эффект в лабиринтных уплотнениях достигается за счет возникновения гидравлического сопротивления при течении через малый зазор вязкой жидкости. Для повышения гидравлического сопротивления делают лабиринтные канавки, которые изменяют площадь сечения.
      Если магнитный кристалл (элемент ЭВМ четвертого поколения) поместить под микроскопом и высветить лазерным лучем, то обнаружится, что структура его неупорядочена и похожа на лабиринт (1.15). Нарушив эту структуру магнитной иглой, а затем постепенно намагнитив, получают элементарные магнитики — домены. Каждый из них несет единицу информации. На 10 см2 можно разместить миллион таких магнитиков, то есть записать 106 единиц информации.
     
      СКВОЗЬ ЛИКИ МИРА
      Вот уже более 25 столетий миф о Тесее (Тезее) и Лрипдпс вдохновляет художников, писателей, поэтов, драматургов и архитекторов. Ему посвящены многочисленные картины, скульптуры, пьесы и поэмы.
      Самос древнее изображение поединка Тесея и Минотавра выполнено на золотой пластинке около 600 г. до н. э. Древнегреческие вазописцы часто изображали ключевые события мифа на киликах — специальных глиняных сосудах для жидкости. Один из наиболее знаменитых вазописцев — мастер Клеофрад около 470 г. до н. э. изобразил поединок Тесея и Минотавра (1.16).
      Римские художники, поэты и скульпторы также отдали дань лабиринтной теме. Она представлена на фресках и мозаиках города Помпеи, засыпанного пеплом в 79 г. при извержении Везувия. Мозаика лабиринта с изображением победы Тесея в центре дала само название строению — «Дом лабиринта» (1.17). На другой римской мозаике изображены на фоне лабиринта четыре ключевые сцены мифа (1.18). Лабиринт на мозаике из виллы Диомеда в Помпее (1.19), вероятно, уже служил для игр. В нем только через центральную арку можно было проникнуть в лабиринт.
      Мозаиками в форме лабиринтов украшены полы многих средневековых соборов Европы, например Шартрского (1.20), Сиенского (1.21), святого Квентина (1.22) и других.
      Образ и символ лабиринта особенно часто использовали мыслители XVII в. В 1631 г. вышел философско-социальный роман выдающегося чешского педагога и писателя Я. А. К о-менского (1592 — 1670) «Лабиринт света и рай сердца».
      Один из первых (не дошедший до нас) учебников Комен-ского, построенный в форме загадок и решений, назывался «Лабиринт премудрости для молодежи, изучающей мир». Школа того времени была настоящим лабирин?ом, а педагогический метод Коменского был нитью Ариадны для выхода из него.
      Интересно отметить, что в средневековье для лабиринтов находили вполне мирные и практические применения: разбивали грядки огородов в форме лабиринтов (1.23). Слова лабиринт и Ариаднина нить стали именами нарицательными: лабиринт — запутанное, безвыходное состояние и Ариаднина нить — путь к правильному решению сложной задачи, счастливая идея в запутанной и, казалось бы, безнадежной ситуации.
      Приведем отрывок нз воспоминаний нашего современника, заслуженного штурмана СССР В. Аккуратова, красноречиво озаглавленных «Нить Ариадны»: «Это произошло сорок лет назад, когда мы высаживали героическую четверку папанинцев на дрейфующие льды Северного географического полюса. Карта, надежно служившая на протяжении нескольких веков, вызвала у нас замешательство. Даже самые опытные навигаторы оказались в сложнейшем лабиринте, ничуть не уступавшем критскому лабиринту царя Миноса... Лабиринт? Да еще какой! Как мы завидовали мифическому Тесею, обладавшему в лабиринте клубком Ариадны!» (Техника молодежи. — 1977. — № 8. — С. 52 — 53).
      Не менее популярны образы Дедала — создателя критского лабиринта и его сына Икара. С античных времен сохранились фрески, изображающие приготовление Дедала и Икара к полету. Одно из лучших произведений замечательного нидерландского живописца П. Брейгеля (между 1525 и 1530 — 1569) называется «Падение Икара». Образы Дедала и Икара воспеты древнеримским поэтом Овидием (43 до н. э. — ок. 18 н. э.) в произведении «Метаморфозы».
     
      ПЕРЕХОДИМ К ИГРЕ
      Лабиринты были слишком загадочным и заманчивым объектом, чтобы оказаться вне волшебного мира игр. Неизвестно только, кто раньше начал использовать их в играх. Во всяком случае детн древних греков и римлян уже увлекались ими. Это доказывает сохранившийся на стене одного из домов Помпеи детский рисунок лабиринта и надпись возле него на латинском языке: «Лабиринт. Здесь живет Минотавр» (1.24).
      В Англии знаменитым архитектурным лабиринтом была беседка Розамунды (1.25).
      К началу нового времени вошли в моду парковые лабиринты из кустов, деревьев или решеток. О таких лабиринтах упоминается в пьесах английского драматурга У. Шекспира (1564 — 1616).
      Самый знаменитый и существующий до сих пор кустарниковый лабиринт был сооружен в 1690 году при дворе Вильгельма Оранского в Хэмптон-Корте. Вот как описал его посещение английский писатель-сатирик Дж. К. Джером (1859 — 1927) в повести «Трое в лодке (не считая собаки)»: «Гаррис спросил, случалось ли мне бывать в Хэмптон-Кортском лабиринте. Он сказал, что однажды зашел туда, чтобы показать его одному своему родственнику. Гаррис предварительно изучил лабиринт по плану и обнаружил, что он до смешного прост, — жалко даже платить за вход два пенса. Гаррис сказал, что он считал, будто план был составлен нарочно, чтобы дурачить посетителей; изображенное на нем вообще не было похоже на лабиринт и могло только сбить с толку. Гаррис повел туда своего кузена, приехавшего из провинции. Гаррис сказал ему:
      — Эта ерунда не стоит выеденного яйца, но мы все-таки зайдем туда, чтобы ты мог рассказать, что побывал в лабиринте. Собственно, это не лабиринт, а одно название. Надо только на каждой развилке поворачивать направо — вот и все. Мы обойдем его за минут десять и пойдем закусить.
      Когда они вошли туда, им попались навстречу люди, которые, по их словам, крутились там уже битый час и были сыты этим удовольствием по горло. Гаррис сказал им, что ничего не имеет против, если они последуют за ним: он, мол, только что зашел в лабиринт, обойдет его и выйдет наружу.
      Все выразили Гаррису искреннюю признательность и пошли гуськом вслед за ним.
      По дороге они подбирали других людей, блуждавших по лабиринту и жаждавших выбраться оттуда, пока все, находившиеся в лабиринте, не присоединились к процессии. Несчастные, уже утратившие всякую надежду выбраться когда бы то ни было на волю, отказавшиеся от мысли узреть друзей и родных, при виде Гарриса и его команды вновь обрели бодрость духа и, призывая благословения на его
      голову, присоединялись к шествию. Гаррис сказал, что, по самым скромным подсчетам, за ним шагало человек двадцать. А одна женщина с ребенком, блуждавшая по лабиринту с раннего утра, боясь потерять Гарриса, взяла его за руку и цепко держалась за него.
      Гаррис честно поворачивал всякий раз направо, но конца пути все не было видно, и кузен сказал, что лабиринт, видимо, очень большой.
      — Один из самых обширных в Европе, — подтвердил Гаррис.
      — Должно быть так, — сказал кузен, — ведь мы уже прошли добрых две мили.
      Гаррис и сам начал подумывать, что действительно дело неладно, но продолжал путь, следуя своей методе, пока наконец шествие не наткнулось на кусок печенья, валявшийся на зерлле, и кузен Гарриса не побожился, что он уже видел его семь минут тому назад. Гаррис сказал:
      — Не может быть!
      Но женщина с ребенком воскликнула:
      — Как это: не может быть! — Она собственноручно отняла у своего младенца этот огрызок и бросила его незадолгс до того, как встретила Гарриса. Тут она присовокупила, что дорого бы дала за то, чтобы никогда с ним не ветре чаться, и выразилась в том смысле, что он гнусный самозва нец. Это обвинение возмутило Гарриса до глубины души, и он вытащил план и изложил свою теорию.
      — План, может быть, и помог бы делу, — сказал кто-то, — если бы вы хоть приблизительно представляли, в каком месте лабиринта мы находимся.
      Гаррис этого себе не представлял и предложил направиться обратно ко входу, чтобы начать все сначала.
      Предложение начать все сначала не вызвало большого энтузиазма; что же касается рекомендации вернуться кг входу в лабиринт, то она была встречена единодушным одобрением, и процессия повернула и опять потянулась велел за Гаррисом в обратном направлении. Прошло минут десять и они оказались в центре лабиринта.
      Гаррис сначала было вознамерился изобразить дело так что он к этому стремился; но у толпы был такой угрожающий вид, что он решил представить все как чистую случайность
      Теперь, по крайней мере, было ясно, с чего начать. Зная, где они находятся, они сверились еще раз с планом, убеди лись, что все затруднения гроша ломаного не стоят, и начали свой поход в третий раз.
      И через три минуты они снова оказались в центре лаби риита. Теперь они уже не могли отвязаться от этого места Куда бы они ни направлялись, дорога неуклонно приводила их обратно к центру лабиринта. Это стало повторяться с такой регулярностью, что кое-кто из компании просто стоял там и дожидался, пока остальные покрутятся и вернутся к ним
      Гаррис снова развернул план, но один вид этого документа привел массы в ярость, и Гаррису посоветовали употребить его себе на папильотки. По признанию Гарриса, он в этот момент почувствовал, что до некоторой степени утратил популярность.
      Наконец публика пришла в полное умоисступление и стала выкликать на помощь сторожа. Сторож услышал призывы, взобрался снаружи на лесенку и стал давать нужные указания. Но к этому времени все они уже до того ошалели и в головах у них был такой сумбур, что никто не мог ничего понять, в тогда сторож велел им стоять на месте и сказал, что сейчас придет к ним сам. Они сбились в кучу, а сторож спустился лесенки и вошел в лабиринт.
      На беду, сторож оказался новичком; он вошел в лабиринт, по не сумел найти заблудившихся, а через некоторое время и сам заблудился. Они могли разглядеть сквозь кусты живой изгороди, как он мелькает то тут, то там, и он тоже видел их и пытался до них добраться, и они ждали его минут пять, после чего он снова появлялся на том же самом месте и спрашивал, куда же они девались.
      Им пришлось дожидаться, пока после обеда не появился один из старых сторожей и не вывел их оттуда. (Джером К. Джером. Трое в лодке (не считая собаки). — М.: Худ. лит., 1984. — С. 44 — 46.)
      Заметим, что лабиринтные игры, как и игры вообще, несут на себе черты эпохи, в которой они создаются. В 20-х готах нашего века один английский журнал предпринял сбор средств для устройства площадки детям рабочих. Чтобы привлечь внимание читателей к этому мероприятию, журнал напечатал оригинальный лабиринт (1.26).
      У входов в лабиринт дымят заводские трубы и только в его центре — благоустроенная площадка для игр. (Рисунок символизирует то, каким длинным и сложным является путь детей бедняков от заводского поселка к месту с чистым воздухом.)
      В 30-х годах, когда трудящиеся Германии боролись с надвигающейся чумой фашизма, был популярен лабиринт, в котором спартаковцам («Спартак» — детская демократическая организация Германии, образованная в 1920 г.) нужно было пройти по запутанным коридорам лабиринта, минуя штурмовиков (1.27).
      Заслуженной популярностью среди задач занимательной математики пользуются лабиринтные задачи. Диапазон их сложности исключительно широк — от простейших, доступных дошкольникам, до сложных математических задач.
      Лабиринтные задачи отражают, как вы увидите далее, важнейшие математические закономерности, изучаемые в топологии, теории графов, теории вероятностей и других математических дисциплинах.
      Выдающийся ученый XX века, создатель ставшего классическим учения о стрессе Г. Селье писал: «Просто распознавать бесчисленные природные явления бесполезно, если мы не способны в случае необходимости мысленно воссоздать их, пройдя сквозь лабиринт всех возможных связей. ...Даже если причинность способствует пониманию связи между явлениями в той же степени, как и нить Ариадны, мы без ее помощи не смогли бы выбраться из лабиринта бесчисленных связей, также, как Тесей из своего лабиринта» (Селье Г. От мечты к открытию: Как стать ученым. — М.: Прогресс, 1987. — С. 284).
      Исследуя замысловатые лабиринтные маршруты, вы испытаете прекрасное чувство их первооткрывателя.
     
      Глава 2
     
      Предмет математики настолько серьезен, что полезно не упускать случая сделать его немного занимательным.
      Б. Паскаль
     
      ПОКА БЕЗ НИТИ АРИАДНЫ
      2.1. Для начала предлагаем пройти по коридорам этих постепенно усложняющихся лабиринтов.
      2.2. Кому первые тренировки покажутся недостаточно напряженными, могут попробовать свои силы, прокладывая маршруты от входа к центрам этих лабиринтов.
      2.3, 2.4. Каким маршрутом Винни-Пух может пройти к домику, а муравей к своему месту в муравейнике?
      2.5, 2.6. Как мышке пройти к сыру, а ежику - к яблоку?
      ВЫХОДИМ В ПРОСТРАНСТВО
      2.7. Помогите дедушке найти портфель.
      2.8. Прогуляйтесь по эстакадам геометрического города от площади 1 к площади 2.
      2.9. Пройдите в волшебном замке от нижней террасы 1 к верхней 2 так, чтобы по многочисленным лестничным переходам все время двигаться только вниз.
      2.10. Пользуясь лестницами, перейдите с крыши дома 1 на крышу дома 2.
      ВОЗЬМИТЕ НИТЬ АРИАДНЫ
      Победив Минотавра, Тесей чувствовал себя в критском лабиринте увереннее, чем мы в предыдущих лабиринтных прогулках. У него была нить Ариадны и правило пользования ею, то есть алгоритм выхода из лабиринта.
      Мы путешествовали по лабиринтам чисто интуитивно, методом проб и ошибок, и все же достигали поставленной цели. Так может быть, метод проб и ошибок — это тоже некоторый алгоритм? Да, алгоритм, и для широкого класса лабиринтов даже наилучший, поэтому мы к нему еще вернемся.
      А теперь рассмотрим еще один алгоритм поиска необходимого нам маршрута. Если имеется план лабиринта, то выход из него можно найти, зачеркивая все тупики, то есть коридоры, из которых нет выхода (2.11, 1, 2).
      Незачеркнутая часть коридоров и будет выходом из центра лабиринта или же маршрутом от входа к выходу. Проверьте эффективность рассмотренного алгоритма на других лаби ринтах рисунка 2.11.
      Пусть плана нет, но мы знаем, что лабиринт имеет один выход. Тогда полезно пользоваться алгоритмом (правилом) одной руки — идти по лабиринту, не отрывая правой (или левой) руки от стены лабиринта. Правило одной руки не универсальное, но во многих случаях оно может оказаться полезным.
      Пользуясь правилом одной руки, можно пройти по всем участкам того лабиринта, все стены которого хотя и имеют сложные повороты или изгибы, но составляют непрерывное продолжение наружной стены. Это правило не позволит нам пройти в центр лабиринта (2.11, 3), так как центральная часть этого лабиринта полностью изолирована вторым внутренним коридором от наружной стены.
      Лабиринты, не содержащие замкнутых маршрутов, называются односвязными. Лабиринты, содержащие замкнутые маршруты, то есть отдельно стоящие стенки, называются многосвязными. Только в односвязных лабиринтах, пользуясь правилом одной руки, можно достичь цели.
      2.11. Проверьте, можно ли, применив правило одной руки, пройти от входа к выходу лабиринтов 2.11, 4 и 2.11, 5.
      2.12. Какой из пяти дорог должен проследовать рыцарь, чтобы попасть к замку? Правило левой или правой руки обеспечит ему более краткий путь?
      2.13. Пользуясь правилом одной руки, пройдите к дереву в лабиринте (построен в Англии, XIII в.).
      2.14. У этого лабиринта три входа С помощью правила какой руки можно попасть в центр лабиринта через каждый из этих входов?
      2.15. Правило какой руки следует применить, чтобы пройти к центру лабиринта через вход 1; вход 2?
      2.16. Помогите туристу, застигнутому проливным дождем, обойти все водные преграды и выйти на сухой участок.
      2.17. Каким маршрутом девочка может выйти из лабиринта?
      2.18. Проложите маршрут от входа к выходу автомобилеподобного лабиринта.
      2.19. Помогите улитке найти в каменном лабиринте тропинку к мухомору.
      2.20. Проложите кратчайший маршрут от старта к пионерскому лагерю, отмеченному треугольником.
      2.21. Помогите мальчику выйти к северной окраине леса.
      2.22. 2.23. Проложите маршруты к центрам этих карнавальных масок-лабиринтов.
      2.24. Охотники расставили на тропинках ловушки для зайца. Найдите безопасную для зайца тропинку к месту, отмеченному стрелкой.
      2.25. Каков кратчайший путь рыцаря к замку?
      2.26. Контуры этого лабиринта напоминают карту Индии. Совершите в нем путешествие от Леха до Туттуккуди.
      2.27. Кто какую игрушку держит?
      2.28. Кто с какой оцецКой идет из школы?
      2.29. 2.30. Пройдите по всем аллеям каждого парка так, чтобы ни по одной аллее не проходить дважды.
      2.31. От клеточки 1 пройдите к клеточке 2, не пересекая вершин других клеточек. При этом маршрут не должен иметь точек самопересечения, то есть в каждой клеточке разрешается Побывать только один раз, не пересекая жирных линий.
      2.32, 2.33. Пройдите в каждом квадрате от клеточки 1 к клеточке 2 так, чтобы обойти все клеточки по одному разу, не попадая в черные.
      2.34, 2.35. Используя условия трех предыдущих задач, найдите такие маршруты в этих двух квадратах, чтобы каждый из них начинался и заканчивался в клеточке 1.
      2.36. В этом квадрате путешествовать надо по сторонам клеточек. Маршрут может самопересекаться, но он должен быть замкнутым и проходить через все восемь отмеченных перекрестков.
      2.37. Прославленный русский полководец А. В. Суворов проверял смекалку своих офицеров, предлагая им такую задачу:
      Комендант крепости выходит из центрального помещения крепости и проверяет, как несут службу солдаты на постах При этом он, обходя все посты, не проходит дважды ни по одному участку маршрута и на каждом посту бывает только один раз. Каков маршрут коменданта?
      2.38. Заяц вливает в лейку молоко, а белочка — томатный сок. Какой кран нужно открыть, чтобы выпить томатный сок?
      2.39. Какую кнопку следует нажать, чтобы прекратилось вытекание горючего из поврежденной трубы?
      2.40. Машинисту надо подъехать к тупику В. Каким буде маршрут, если паровоз не может дать задний ход?
      2.41. Соедините каждый корабль со своим якорем, как это сделано в левом верхнем углу. Через каждый квадратик должна проходить лишь одна линия, и никакие линии не должны пересекаться или заходить в выделенные зоны.
      2.42. Сосчитайте повороты, сделанные белкой от пенька к домику. (Повороты разрешается делать только под прямым углом, а двигаться — в направлении стрелок.)
      В ЛАБИРИНТАХ ЧИСЕЛ
      2.43. Найдите в этом лабиринте такой маршрут, чтобы сумма всех «собранных» на перекрестках чисел равнялась 40. Через каждый перекресток можно проходить только один раз.
      2.44, 2.45. Назовите последовательно все числа, записанные случайным образом в каждой из таблиц. Если вы сделаете это за 4 минуты, то вы исключительно внимательны, за 5 - -внимание удовлетворительное, а за 6 — оно несколько ослаблено, и его необходимо тренировать.
      2.46. Проложите такие три маршрута, чтобы произведение чисел записанных в проходах, было: а) наибольшим; б) наименьшим; в) равно 900.
      2.47. Проложите такие маршруты от вершины к основанию числовой пирамиды, чтобы суммы чисел, встречаемых на каждом из них, равнялись соответственно 35, 45, 55.
      2.48. 2.49. От верхнего левого квадрата проложите такой путь к нижнему правому квадрату, чтобы сумма чисел, запи санных в промежуточных квадратах, а также в стартовом и финишном, составляла для первого лабиринта 110, а для второго 70.
      (Искомый маршрут может пересекать только стороны, но не вершины промежуточных квадратов и проходить через каждый промежуточный квадрат только один раз.)
      2.50. Двенадцать чисел, осаждая замок цифроградцев, решили расположиться так, чтобы их сумма на каждой стороне шестиугольника равнялась 17. Четыре числа уже стоят на требуемых местах. Как следует расставить остальные восемь чисел?
      2.51. Поднявшимся на фрегат по веревочной лестнице будет считаться тот, кто сумеет отобрать шесть таких перекладин, сумма чисел на которых равна 100.
      2.52. Поверните четыре кольца так, чтобы суммы каждой четверки чисел, расположенных на одном радиусе, были одинаковыми. Чему они равны?
      2.53. От 1 до 9 можно двигаться только либо вправо, либо вниз. Выполняя это условие, проложите между этими числами такой маршрут, чтобы сумма пройденных чисел составляла 100.
      2.54. Между верхней и нижней пятерками проложите такой маршрут, чтобы сумма чисел, включая стартовую и финишную пятерки, равнялась 100.
      2.55. Найдите 12 таких натуральных чисел, не превосходящих 19, чтобы их сумма по всем указанным стрелками направлениям была равна 38. Числа не должны повторяться.
      2.56. Проложите между А и В такие два маршрута, чтобы в первом сумма пройденных чисел составляла 250, а во втором — 350.
      2.57. В соревнованиях по стрельбе участвовало три стрелка. Каждый из них сделал по мишени 6 выстрелов. Соревнование закончилось вничью. Определите, какие были попадания у каждого участника состязаний, если известно, что у стрелка, попавшего в центр и выбившего сразу 50 очков, все пули достигли мишени ниже средней линии.
      2.58. Проложите такие три маршрута к центру этого лабиринта, чтобы сумма чисел, записанных на проходах была: а) наибольшая; б) наименьшая; в) равная 136.
      2.59. В свободные клетки впишите данные числа — от двузначных до одиннадцатизначных — таким образом, чтобы лабиринт был заполнен ими полностью: каждое число должно занять строго отведенное ему место. На лабиринтной сетке указано место только цифры 4.
      2.60. Острова средневекового государства соединены мостами, на которых находятся таможенные барьеры. Проходящий по мосту, обязан уплатить несколько форинтов пошлины (ее размер указывают цифры, изображенные рядом с мостом). Найдите путь через острова и мосты от одного из трех входов к одному из двух выходов, чтобы сумма пошлины составила 6 форинтов.
     
      СЛОВЕСНЫЕ ЛАБИРИНТЫ
      Предлагаем небольшой набор словесных лабиринтов. Для их преодоления потребуются смекалка, настойчивость и любовь к русскому языку.
      2.61. В таблице случайным обра.юм записаны все 33 буквы алфавита. За две минуты отыщите и назовите их в алфавитном порядке.
      2.62. В 64 клеточки квадрата вписаны буквы алфавита. Начиная с буквы А в верхнем левом углу, проведите ломаную несамопересекающуюся линию, которая проходила бы ровно через §3 буквы алфавита и заканчивалась в нижнем правом углу буквой Я, но не проходила бы через вершины клеточек
      2.63. Хотите забить гол в ворота бульдога? Тогда запишите в свободных клетках три таких слова, чтобы в каждом были все буквы предыдущего и еще одна буква, взятая из слова бульдог.
      2.64. Вы забросите столько шайб, сколько раз в направ лении снизу вверх сможете прочесть слово шайба. Каждый раз при чтении надо выбирать путь, отличающийся от предыдущего одним поворотом. А теперь подсчитайте, сколько на вашем счету шайб.
      2.65. Какую букву нужно вписать в свободный кружочек, чтобы все записанные по трем диаметрам слова превратить в другие?
      2.66. Используя данные буквы, заполните свободные квадратики двух «немых» кроссвордов, в каждом из которых должно быть по 8 слов.
      2.67. Пройдите по этому словесному лабиринту от пляжа к шалашу. Допустимые траектории вашего пути приведены слева. Если маршрут ваш будет правильный, то по пути вы будете вычитывать последовательность слов: тропинка, тро пинка,...
      2.68. Соедините четыре части так, чтобы буквы, записан ные на этих частях, составили пословицу.
      2.69. Старт, финиш и некоторые этапы пути в этом cnapei ном лабиринте обозначены стрелками. Если вы правильно изберете и промежуточные этапы, то из букв на вашем пуп и составится известная русская поговорка.
      2.70. Существует, как уже упоминалось, мнрго систем тайнописи или кодирования. Сравнительно простым является древний способ «решетки». От состоит в том, что на квадрш ный набор букв накладывается решетка, отверстия которой расположены в определенном порядке. Буквы, появляющисс i в этих отверстиях, и составят закодированный текст.
      Прочтите закодированный здесь текст. Для этого изготовьте решетку с отверстиями (они закрашены). Наложите ее на тайнопись и выпишите все буквы, которые появятся в «отверстиях». Затем решетку поверните на 90° по часовой стрелке и снова выпишите буквы. После четвертого поворота тайнопись будет расшифрована. Прочтите ее.
      2.71. Сколько существует в буквенном треугольнике таких маршрутов, продвигаясь по которым от буквы к букве можно прочитать слово «треугольник»? (На рисунке показан один из таких маршрутов.)
      2.72. (Об одном из дел Шерлока Холмса.) Расследуя i ерию преступлений, лондонская полиция задержала некоего Джона Пигса. В его бумажнике нашли монету 65 шиллингов и клочок бумаги с какой-то зашифрованной записью. Расшифровать эту запись никому не удалось. Дело поручили Шерлоку Холмсу. Он решил, что монета имеет какое-то отношение к шифру. Накладывая ее на буквы, он нашел такое положение монеты, при котором из букв, расположенных на ее окружности по часовой стрелке, складываются лова, уличающие Джона Пигса в соучастии в расследуемом преступлении. Что прочел Шерлок Холмс?
      2.73. Чтобы прочесть пословицу, надо из отдельных частей сложить ключ.
      2.74. Мысленно «передвиньте» фургончики по соответствующим линиям на свои места (в квадратики внизу). Какую фразу при этом получите?
      2.75. В Стране Чудес Алиса встретила Чеширского кота, ого самого, который мог исчезнуть, оставив на месте свою
      ллыбку. Алиса захотела спросить кота: что он за животное? И Стране Чудес вопросы задавали в письменной форме, читали сверху вниз и снизу вверх. Поэтому их и записывали t удобной для такого чтения форме: чтобы читатель мог начинать и заканчивать фразу, где он пожелает.
      Сколькими способами можно было прочесть в Стране Чудес вопрос Алисы: Was it a cat I saw? Начинайте с любого Л и переходите к соседней букве, от нее к следующей и т. д., пока не доберетесь до s, а затем возвращайтесь назад к границе. (Можете двигаться вверх, вниз, влево и вправо.)
      2.76. Таинственным текстом начинается роман Жюля Черна «Жаганда». Всеми уважаемый человек Жоам Дакоста несправедливо приговорен к смертной казни. Спасти его может только расшифровка приведенного текста, содержащего доказательство его невиновности. Друзья приговоренного тщетно трудились над расшифровкой. Больше всех был увлечен судья, поверивший в невиновность Дакосты. Он пришел к заключению, что применен следующий цифровой шифр. Возьмем какое-либо число, например 423, назовем его ключом, подпишем под текстом, как показано ниже:
      УСУДЬ ИЖАРРИКЕСА 4234234 2 3 423423
      ЧУЦИЮЛК ВУФКНЙУГ ПРО Н И Ц А ТЕЛЬ НЫЙУМ 42342 34 234234234
      УТСС К ШД ФИПЮРЯ ЛЦР
      Далее каждую букву текста заменим другой, отстоящей от нее в алфавите на соответствующее цифре число букв. Если же, например, цифра 4 окажется под буквой Ю, отсчитываем я, а, б, в и ставим вместо Ю букву В.
      Судья утверждал, что смог бы расшифровать таинственный текст, если бы буквы в нем были разделены на слова. Тогда можно было бы в любом семибуквенном слове заподозрить имя Дакосты, которое в тексте наверняка упоминается, и таким образом разыскать ключ. Но при сплошном тексте расшифровка его невозможна. (Судье Жаррикесу расшифровка удалась только после получения дополнительной информации.)
      Но, может быть, судья не проявил должной настойчивости и дополнительную информацию следует считать избыточной?
      Попробуйте расшифровать этот документ, не располагая какой-либо дополнительной информацией.
     
      САМИ ДЕДАЛЫ И ТЕСЕИ
      Предлагаем читателям выступить в роли строителей лабиринтов, воспользовавшись описаниями нескольких простых лабиринтных игр-самоделок. Чаще всего они состоят в том, чтобы провести шарик (или несколько шариков) в центр лабиринта или другую заданную его точку.
      Для всякого лабиринта сначала нужно сделать коробку (из древесины, толстой фанеры, оргстекла или других материалов). закрыв ее сверху оргстеклом, вставленным в пазы, сделанные в боковых стенках. Дно лабиринта можно сделать из фанеры или пластика, перегородки — из тонких деревянных планок, полосового железа, оргстекла или фанеры. Шарики подберите из старых шарикоподшипников. (Заметим, что лишь к некоторым из представленных ниже схем указаны
      размеры. В остальных случаях предоставляем читателям возможность поиска оригинальных конструкторских решений.)
      2.77. Игра состоит в том, чтобы провести маленький шарик по коридорам лабиринта к его центру. Если шарик попадет в тупик, то его нужно выкатить обратно. Если же он попадет в центр, то его выкатывают по лабиринту или переворачивают коробочку стеклом вниз.
      2.78. На дне коробки сооружен лабиринт простой конструкции. Но задача усложнена требованием провести к центру лабиринта три шарика. (Если это задание окажется сложным, начинайте игру с двумя шариками.)
      2.79. Этот лабиринт построен в правильном пятиугольнике. Задача состоит в том, чтобы провести шарик к одному из двух углублений («глаза тигра»).
      2.80. Один лыжник уже проехал по извилистым коридорам этого лабиринта. Если сделать такой лабиринт своими руками, роль лыжника может выполнять шарик. А перегонять его от входа к выходу можно деревянной лопаткой. (Игру можно использовать много раз, если сделать съемные вставки для перемены расположения входных и выходных ворот и некоторых промежуточных звеньев лабиринта.)
      2.81. В этом лабиринте надо провести шарик по маршруту, указанному стрелкой, причем сделать это так, чтобы шарик не провалился ни в одно из отверстий. Если он попадет в отверстие, то через нижнее отверстие в боковой стенке может быть выведен наружу. (После каждой неудачи игру начинайте сначала, закладывая шарик вновь в верхнее отверстие.)
      2.82. А здесь шаг в сторону усложнения. Плоская коробочка сделана так, что открыть ее невозможно: и дно, и крышка прибиты наглухо. В углу крышки имеется небольшое отверстие, куда опускается металлический шарик. Итак, он попал в лабиринт. Задача состоит в том, чтобы провести шарик по лабиринту и выкатить наружу через боковое отверстие коробочки. Сделать это непросто, так как лабиринт находится внутри закрытой коробочки. Нагибая ее в разные стороны, попытайтесь отыскать выход из этого лабиринта-невидимки.
      2.83. Наружный извилистый бортик и внутренние стенки этого лабиринта можно сделать из картонных полосок, выгну тых соответствующим образом и приклеенных к основанию. Диаметр тринадцати отверстий должен быть несколько боль ше диаметра шарика. К боковым стенкам приклейте дистан ционные подпорки из картонных полосок или фанеры. Они обеспечат нужное расстояние от дна коробки — немного больше, чем диаметр шарика. (Стенки коробки должны немного подниматься над крышкой, чтобы шарик не выкаты вался наружу.)
      Задача состоит в том, чтобы, минуя отверстия, провести шарик по указанному стрелками маршруту. Если шарик по падет в одно из отверстий, то выкатывайте его через отверстие, проделанное в одном из углов коробки.
      2.84. Ящик для лабиринта имеет форму правильного пяти угольника. Ко дну ящика во внутренней части приклейте выпиленный из толстой фанеры лабиринт, а с противополож ной стороны — подставку сферической формы, благодаря которой ящик может раскачиваться и поворачиваться в раз ные стороны. Внутрь ящика вложите шарик. Поворачивая ящик, проведите шарик в центр лабиринта.
      2.85. Этот лабиринт — двухэтажный. В нем шарик может перемещаться по любому из этажей, но с одного этажа на другой он попадает через отверстия, соединяющие этажи Слева изображена схема первого этажа, справа — второго (зеркальное отражение). Черные линии — пути, по которым перемещается шарик, кружочки — отверстия, соединяющие этажи. Лабиринт имеет один вход и два выхода на первом этаже. Труднее всего достичь выхода, отмеченного звездочкой Найдите кратчайшие пути от входа к выходу.
      Для сооружения лабиринта потребуется лист пенопласта размером 28X37X5 см. На верхней и нижней стороне листа паяльником (или нагретым стальным стержнем) на рас стоянии 2 см друг от друга сделайте борозды (на схеме они изображены черным цветом), а в местах, отмеченны на схемах кружками, пенопласт просверливается насквозь. На двух боковых гранях делаются три отверстия. Затем верх и низ листа пенопласта заклеивается оргстеклом или целлофаном.
      2.86. Каждый этаж пятиэтажного лабиринта помечен соответствующими цифрами, цифрой 6 обозначена крыша Все планы ориентированы одинаково (направление «юг север» на них одно и то же). Черными линиями обозначены непроницаемые перегородки, белым цветом — отверстия, сквозь которые можно переходить с одного этажа на другой Игра заключается в том, чтобы, проникнув сквозь отверстие в крыше и прокатившись по переходам, шарик выкатился из отверстия в первом этаже. (Можно двигаться и в проти воположном направлении — с первого этажа на крышу.)
      Лабиринт следует сделать из листового прозрачного плек сигласа и пропустить через него шарик для настольного тенниса. В таком случае ширина коридоров и высота этажей должна составлять 40 — 45 мм. (Не забудьте учесть толщину плексигласа!) Отдельно слева показан пол третьего этажа с установленными на нем внутренними перегородками и вырезанными отверстиями. Наружные стены общие для всего лабиринта. При монтаже этажей нужно быть внимательным, чтобы не перепутать их друг с другом и не изменить ориентацию. Выходное отверстие в кровле обведите какой-нибудь краской, чтобы его не спутать с выходом в первом этаже.
      Можно изготовить сравнительно простое кибернетическое игровое устройство, которое, подобно программному блоку, способно взаимодействовать со своим противником — человеком. Рассмотрим три кибернетические лабиринтные игры.
      2.87. Коты и мыши — герои многих сказок, поговорок, мультфильмов и, конечно, игр.
      Коты должны ловить мышей, а мыши — прятаться от котов, так заведено на свете. При этом каждая сторона, не желая быть в проигрыше, идет на всяческие ухищрения.
      Рассмотрим лабиринтную игру «Кот и мышь».
      Предположим, что в какой-то момент оба участника игры попадают в лабиринт (1), каждому участку которого присвоен номер. Передвигаясь с одинаковой скоростью, они могут идти прямо и заворачивать за угол, но не должны проходить путь дважды. Если, пройдя три участка, «мышь» не встретилась с «котом» и спаслась, то она выиграла. Участники игры во время движения не знают о местонахождении и перемещении противника.
      Допустим, что они действуют по заранее составленному алгоритму. У «кота» и «мыши» имеется восемь различных стратегий движения в лабиринте (2), каждая из которых составлена из трех участков.
      И матрице позиция «кот поймал мышь» обозначается 1 «кот упустил мышь» — 0. Для «мыши» наиболее выгодны стратегии М\ и Mg. «Коту» же наиболее выгодны К4 и Kg, поскольку здесь он выигрывает семь раз из восьми. Таким образом матрица игры значительно упрощается:
      В этой стратегической игре 2x2 «кот» и «мышь» имеют равные шансы на успех. «Кот», применив стратегию Kt, с равной вероятностью может как проиграть, так и выиграть. Аналогичная ситуация и у «мыши». Стратегия Ки и Kg, так же как М\ и Mg, равноценны. Очевидно во время игры «коту» следует одинаково часто применять стратегии К4 и К5 — и это будет его оптимальная смешанная стратегия. «Мышь» должна также смешивать свои стратегии М\ и Mg. «Кот» должен делать малые петли, а «мышь» — придерживаться внутренних коридоров. При таком оптимальном поведении игроков ни один из них не будет иметь преимущества перед другим и при большом количестве сыгранных партий счет в игре будет примерно равным.
      Если игрокам эти оптимальные стратегии неизвестны, и они действуют случайным образом, то мышь будет проигрывать чаще, так как в матрице единиц больше, чем нулей.
      Анализ игры показывает, что оптимальная смешанная стратегия «кота» довольно проста, и ее можно ввести в несложное кибернетическое устройство. (Построенный играющий автомат будет придерживаться оптимальной смешанной стратегии «кота», а человек выступит в роли «мыши».)
      Кибернетическая модель «Лабиринт» (рис. 2.88) — это релейная схема, воспроизводящая свойства памяти и демонстрирующая работу сигнальной системы, которая выбирает и запоминает кратчайший путь к любой заданной точке. В этом устройстве световой луч выполняет те же действия, что и «мышь» в предыдущей игре. Модель имеет вид небольшого чемодана, на передней стенке которого размещен лабиринт с одним входом и двенадцатью тупиками, а слева от лабиринта — пульт управления. В любой из тупиков можно поместить «сало» — штепсельный штеккер (для того в каждом тупике имеется специальное гнездо). После включения тумб лера «Запрос» и нажатия кнопки «Поиск» программное устройство модели приступает к поиску «сала». Световой луч
      начинает быстро обходить все проходы и тупики лабиринта, пока не попадет туда, где находится «сало». Как только -то произойдет, дальнейший поиск прекращается и звуковой сигнал (звонок) оповещает о том, что «сало» найдено.
      Если не помещая «сало» ни в один из тупиков лабиринта, заставить модель искать его (нажатием кнопки «Поиск»), световой луч обойдет все проходы и тупики и, не найдя «сала», погаснет. На пульте управления вспыхнет табло «Лабиринт пуст».
      Продолжительность действия «памяти» модели можно регулировать, устанавливая ее в пределах от 1 до 60 секунд. На пульте управления сигнальная лампочка «Память», которая светится только в том случае, если модель «помнит» результат своих поисков.
      Подробнее с этой моделью и ее принципиальной схемой вы можете ознакомиться в книге: Простая кибернетика 1Сост. Д. М. Ко мс к и й. — М.: Мол. гвардия, 1965. — С. 121 — 130.;
      На рисунке 2.89(1) изображена схема одного из первых кибернетических устройств — автоматов для осуществления управления поведением некоторой системы, именуемой «путником». Данная схема лабиринта изображена на панели устройства. В центральную часть лабиринта помещался «путник», который мог продвигаться в поисках выхода. Движениями «путника» управлял программный блок, в котором не было информации о том, где находятся выходы из лабиринта. Перед человеком ставилась задача: не выпустить «путника» из лабиринта.
      На рисунке 2.89(2) изображена схема другого кибернетического устройства — «Тесей и Минотавр».
      Пусть Тесей находится в центре симметричного лабиринта.
      Ему необходимо выбраться из центра лабиринта к одному из выходов 1 или 15. В этой игре у Тесея не будет нити Ариадны — в каждом узле его поджидает Минотавр, который указывает верный или неверный путь. Тесей знает, что у одного из выходов Минотавр хранит несметные сокровища, и понимает, что Минотавр постарается всячески запутать его. Поэтому Тесей должен решить, когда следовать указаниям Минотавра, а когда направляться в противоположную сторону.
      Очевидно, Тесей несколько первых шагов должен сделать, бесприкословно выполняя указания противника, убеждая его в «послушании», а затем использовать это в своих интересах. Вот один из возможных вариантов развития событий.
      Предположим, что сокровища у входа 1, а Тесей находится в узле 8.
      1. Минотавр указывает на узел 9, Тесен переходит туда.
      2. Минотавр указывает на узел 11, Тесей переходит туда.
      3. Минотавр указывает на узел 12, но Тесей переходит в узел 10.
      4. Минотавр еще верит, что Тесей послушный, и, пытаясь направить его в другой конец лабиринта, указывает на узел 11, но Тесей выбирает противоположный путь — узел 8.
      5. Два «непослушания» убеждают Минотавра, что Тесей ему не повинуется. Поэтому Минотавр указывает на узел 7 в расчете, что Тесей выберет узел 9. Однако и Тесей убежден, что «переучил» Минотавра, и, выполняя его указания, переходит в узел 7.
      6. Минотавр помнит, что Тесей «слушался» его два раза подряд, поэтому назвать путь, ведущий к выходу 1, он опасается, а вдруг Тесей все-таки послушается. Итак, Минотавр указывает на узел 8. Однако Тесей учел опасения Минотавра и переходит в противоположный узел 5.
      7. Запутавшись, Минотавр предполагает, что уж теперь-то его противник должен быть непослушным, и указывает на узел 3. Однако Тесей подчиняется и переходит туда.
      8. Полагая, что Тесей не может быть два раза подряд послушным, Минотавр указывает на узел 2. Но Тесей, учитывая это, подчиняется и переходит в узел 2.
      9. В панике Минотавр указывает на узел 4, пытаясь увести Тесея от выхода из лабиринта. Однако Тесей не ошибается и выбирает противоположный узел 1. Путь к сокровищам Минотавра открыт.
      Герою потребовалось всего 9 ходов, чтобы выйти из лабиринта. Если бы он в каждом узле определял направление своего движения случайным образом, то для выхода из лабиринта ему потребовалось бы в среднем около 25 ходов.
      В автомате (2.89.3) роль Тесея играет релейноконтактное стройство, а функцию Минотавра выполняет играющий с втоматом человек. Внешний вид автомата показан на рис. Л89(3). На лицевой панели изображена схема лабиринта, .! узлах которого установлены электрические лампочки. На выходах — красные лампочки, остальные — зеленые. Во время игры загорающиеся лампочки указывают местонахождение Тесея. Здесь же на лицевой панели расположены: выключатель сети, переключатель «Выход» (для фиксации задуманного человеком выхода из лабиринта 1 или 15), переключатель программ поведения Тесея, кнопки «Ход Тесея» и «Сброс», счетчик ходов Тесея, световое табло «Лабиринт пуст» и «Конец программы» под табличкой «Вы выиграли» и световое табло «Выход найден» под табличкой «Вы проиграли».
      На специальной боковой панели автомата слева находится накрытый крышкой блок ввода программы.
      Каждый переход, соединяющий два соседних лабиринта на лицевой панели, имеет посредине ромбовидные гнезда. Они предназначены для установки штеккера, который представляет собой трехгранный стержень с укрепленной на нем стрелкой. С помощью этого штеккера-стрелки Минотавр во время игры указывает Тесею направление движения. Если вставить штеккер в гнездо, то трехгранный стержень войдет в ту половину ромба, куда указывает стрелка. Например, если стрелка указывает на переход из узла 12 в узел 11, то стержень штеккера войдет в левую половину ромбического отверстия, если же нужно указать переход из 11 узла в 12, то стержень войдет в правую его половину.
      Под лицевой панелью у каждого гнезда укреплены три группы контактов. Две группы расположены у остроугольных вершин ромба и состоят из двух пар нормально разомкнутых контактов. Третья группа, укрепленная у одной из тупоугольных вершин ромба, образует одну пару замыкающих контактов. При установке штеккера в гнездо всегда будут замыкаться контакты у тупоугольной вершины ромба и контакты, расположенные у той остроугольной вершины, куда направлена стрелка штеккера. Например, если ввести штеккер в гнездо таким образом, чтобы стрелка указывала направление от узла 11 к узлу 12, то замкнутся контакты, расположенные справа, и контакты у тупоугольной вершины ромба.
      Контакты, установленные около тупоугольных вершин всех ромбовидных гнезд, соединяются параллельно. Контакты же, расположенные около остроугольных вершин ромба, объединены в группу.
     
      ТОПОЛОГИЯ КАК НИТЬ АРИАДНЫ
      Человек, изучая явления окружающего мира, смело использовал сведения из различных отраслей знания, сближая, по образному высказыванию М. В. Ломоносова, «далековатые идеи». И не только далековатые, но и весьма далекие и даже сверхдалекие. Неоценимую помощь в этом всегда оказывала математика. Подтвердим сказанное примером создания и развития топологии, называемой геометрией XX века. Первая работа, специально посвященная этой области математики, — «Предварительные исследования по топологии» немецкого математика И. Листинга (1808 — 1882) была опубликована в 1847 г. Очень скоро топология стала весьма эффективным орудием решения многих задач как в самой математике, так и в ее приложениях, благодаря именно тому, что позволяла видеть общее в весьма различных объектах. Простейшие топологические понятия помогают также решать некоторые лабиринтные задачи.
      Топология изучает свойства фигур, сохраняющиеся при любых взаимно-однозначных и непрерывных преобразованиях. Такие преобразования называются гомеоморфными, или топологическими, а соответствующие свойства — топологическими инвариантами, или просто топологическими свойствами.
      Оказывается, что топологические свойства фигуры — это самые общие, устойчивые и глубокие ее свойства, сохраняющиеся при произвольных сжатиях, растяжениях и перекручиваниях (лишь бы не было склеиванья точек — нарушения взаимной однозначности и разрывов — нарушения непрерывности).
      Но читатели, несомненно, заметили, что при решении лабиринтных задач форма, ширина и длина лабиринтных коридоров никакой роли не играют. Существенно только наличие или отсутствие перекрестков и отдельно стоящих стенок. И в топологии также нет углов и расстояний между точками. Поэтому делаем вывод: для решения лабиринтных задач важны не метрические, а топологические свойства лабиринта.
      В этом легко убедиться, рассматривая внешне различные а для решения наших задач неразличимые лабиринты (3.1). Каждому из них можно было бы придать еще более причуд ливые формы. Но если нигде не склеивать точек и не разры вать линий, то для решения любой нашей задачи получаемые
      лабиринты как топологически эквивалентные будут неразличимы. Рассмотрим некоторые топологические свойства замкнутых плоских линий без самопересечений. Такие линии гомео-морфны окружности. Действительно, если представить модель окружности из резинового шнура, то ее без разрывов и самопересечений легко преобразовать в квадрат, треугольник, прямоугольник и т. д. Это означает, что все такие фигуры топологически эквивалентны. Линии, топологически эквивалентные окружности, называются простыми замкнутыми линиями.
      Французский математик К- Жордан (1838 — 1922) доказал, что всякая простая замкнутая линия на плоскости разбивает эту плоскость на две области — внутреннюю и внешнюю. Может показаться, что в теореме Жордана утверждается очевидный факт, который вряд ли стоило и доказывать. Однако среди неисчислимого количества простых замкнутых линий есть такие замысловатые, что утверждение Жордана далеко не очевидно.
      В частности, если простая замкнутая линия I достаточно сложная, то совсем не очевидно, в какой — внешней или внутренней области, ограниченной 1, находится данная точка А и можно ли соединить данные точки А и В непрерывной линией так, чтобы она нигде не пересекала линии 1.
      Разобраться в подобных ситуациях помогают такие теоремы:
      1. Если число точек пересечения дуги (или отрезка) АВ с простой замкнутой линией 1 нечетно, то одна из данных точек является для фигуры F, которая ограничена линией 1, внешней, а другая — внутренней (3.2).
      Чтобы установить, какая из этих точек (А или В) является внешней, а какая — внутренней относительно фигуры F, достаточно провести из А и В лучи и определить число пересечений каждого луча с линией I. Если это число нечетно, то начало луча находится во внутренней области фигуры F, а если четно — то во внешней ее области.
      2. Если число точек пересечения отрезка (или дуги) СР с простой замкнутой линией 1 четно, то точки С и Р одновременно расположены во внешней или внутренней области фигуры F.
      Диапазон действия этих теорем ограничен, но для лабиринтов, схемы которых являются простыми замкнутыми линиями, они являются подлинной Ариадниной нитью.
      3.1. Какой из известных вам алгоритмов наиболее рационально применить для прогулки к центру этих топологически эквивалентных лабиринтов?
      3.2. Постройте лабиринт и нанесите точки А, В, С, D в соответствии с моделью 3.2.
      3.3, 3.4. Путники оказались в лабиринте. Установите: а) кто из них может встретиться, не пересекая контур лабиринта; б) какой из путников может выйти из лабиринта, не пересекая его контура.
      3.5. Какие мышата могут встретиться в таком лабиринте? Какие из них имеют шансы выбраться из лабиринта?
      3.6, 3.7. Сохранились фрагменты плана лабиринта и известно, что контур его гомеоморфен окружности. Может ли путник .Д выйти из этого лабиринта, не пересекая его контура? Могут ли встретиться путники А и В?
      3.8. Есть ли выход из точки А лабиринта?
      3.9. Проложите маршрут от точки А до точки В Почему при решении этой задачи нельзя воспользоваться теоремой Жордана?
      ГРАФЫ И ДЕРЕВЬЯ
      Два с половиной столетия назад у жителей тихого Кенигсберга (теперь Калининград) пропал покой. Все они увлеченно решали такую задачу — как обойти семь мостов, переброшенных через реку Прегель, огибающую остров Кнсйпхоф, побывав на каждом из них один и только один раз (3.10).
      Эгон беспокойной головоломкой заинтересовался и выдающийся немецкий математик Л. Э й л е р (1707 — 1783). Ученый увидел в этой задаче важную математическую проблему и нашел общий метод решения подобных задач.
      Фигуры, состоящие из ряда точек, соединенных между собой прямолинейными отрезками, кривыми линиями или дугами, называются графами. Точки называются вершинами графа {узлами), а линии (прямые или кривые) — ребрами [ветвями). Линия на графе, не проходящая вдоль ребер больше одного раза, называется цепью. Граф называется связным, если любые две его вершины связаны какой-нибудь цепью.
      Решая задачу о мостах, Эйлер подсчитал число ребер, вы ходящих из каждой вершины графа. Вершины, из которых выходит нечетное число ребер, он назвал нечетными, а верши ны, из которых выходит четное число ребер, — четными. Число ребер, выходящих из вершины графа, называют степенью этой вершины. Все четыре вершины графа задачи о семи мое тах оказались нечетными. Решая эту задачу, ученый открыл следующие свойства связных графов:
      1. Число нечетных вершин связного графа всегда четно. Невозможно начертить граф с нечетным числом нечетных вершин.
      2. Если все вершины графа четные, то можно одним росчерком (то есть не отрывая карандаша от бумаги и проводя по каждому ребру ровно один раз) начертить граф, при этом движение можно начинать с любой вершины графа и закончить его в той же вершине.
      3. Граф только с двумя нечетными вершинами можно начертить одним росчерком, при этом движение нужно начать в одной из этих вершин и закончить в другой.
      4. Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком.
      Поскольку число нечётных вершин графа задачи о семи мостах равно четырем, то такой граф невозможно изобразить одним росчерком, а следовательно, невозможно пройти по всем семи мостам, побывав на каждом из них только по одному разу и не проходя при этом дважды ни одного пути между мостами.
      Эйлеровым путем (или циклом) в графе называется путь (цикл), содержащий по одному разу все ребра графа. Граф, обладающий Эйлеровым циклом, называется Эйлеровым графом. Замкнутая линия, которую можно начертить одним росчерком, называется уникурсальной. Рисунок графа, обладающего Эйлеровым циклом, является уникурсальной линией. Заметим, что уникурсальная линия не всегда имеет более простую структуру в сравнении с неуникурсальными линиями. В упоминавшейся иа с. 74 книге Листинга приведен выразительный пример простой и сложных линий (3.11). На основании свойства уникурсальности можно убедиться, что сложная линия 1\ — уникурсальная, и более простая 1г — не уникурсальная.
      Читатели, конечно, уже усмотрели связь между алгоритмами решения лабиринтных задач и некоторыми свойствами Эйлеровых графов (уникурсальных кривых). Маршруты в лабиринте могут быть представлены как ребра графа, а точки пересечения двух или более путей — как его вершины.
      Поиск маршрута в лабиринте сводится к построению алгоритма поиска маршрута в соответствующем графе от шданной точки А до заданной вершины В.
      Если единственные нечетные вершины графа, соответствующего лабиринту, — это вход в лабиринт и его центр (го есть в лабиринте нет ни одного тупика), то (по третьему свойству связных графов) такой лабиринт можно обойти упикурсально.
      Вот известный Хэмптон-Кортский лабиринт (3.12), доставивший столько неприятностей Гаррису, из повести Джерома К. Джерома «Трое в лодке (не считая собаки)». Граф этого лабиринта (3.12) не содержит изолированных вершин, а поэтому является связным. Но он не Эйлеров, то есть не представляет собой уникурсальную кривую. Тупикам лабиринта на графе соответствуют вершины, степень которых равна единице; они называются висячими. Граф рассматриваемого лабиринта связный, но сам лабиринт относится к так называемым многосвязным. На нем сразу видны два изолированных замкнутых маршрута, по которым могли кружиться заблудившиеся Гаррис и ведомые им посетители лабиринта. Эго маршруты: 4- 6- -7 и 6- -8 7. Поскольку лабиринт многосвязный, к нему неприменимо также правило одной руки.
      Неожиданным будет результат построения графа, соответствующего лабиринту (3.13). Он вообще не имеет циклов. Всякий связный граф, не имеющий циклов, называется деревом. Для каждой пары вершин дерева существует единственный соединяющий их путь. Несвязный граф, представляющий объединение нескольких деревьев, называется лесом.
      3.10. Покажите, что, если бы в задаче о семи мостах число мостов было на единицу меньше или на единицу больше, можно было бы совершить прогулку, пройдя по каждому мосту точно один раз. Нарисуйте графы соответствующих задач.
      3.11. Каки;щглиниями достаточно дополнить 1г, чтобы она стала уникурсальной?
      3.12.1Проложите кратчайший маршрут к центру Хэмптон-КортсДого лабиринта.
      3.13. Постройте граф лабиринта 3.13, отметив на нем точки 0, I, 2, 11.
      3.14. Охотник за «мертвыми душами» Павел Иванович Чичиков из повести Н. В. Гоголя побывал у своих предпола-
      земых клиентов по одному разу. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Костанжогло, полковника Кошкарева. Составлен граф взаимного расположения имений клиентов Чичикова и проселочных дорог, соединяющих их. Установите, кому принадлежат имения, изображенные на рисунке, если ни по одной дороге Чичиков не проезжал более одного раза.
      3.15. На плане склада разрывы линий обозначают двери. Внутренние и наружные двери расположены так, что из комнаты В можно пройти через каждую дверь ровно один раз (рис. 3.15, 1).
      При реконструкции склада были добавлены две наружные двери (3.15,2) и обойти все комнаты стало невозможным.
      Архитектор, чтобы исправить этот недостаток, замуровал одну из дверей, сохранив при этом две добавленные двери. Какую дверь замуровал архитектор?
      3.16. Сохранился план подземелья, в одной из комнат которого спрятаны сокровища рыцаря. В завещании рыцаря было сказано, что для отыскания сокровищ, достаточно войти в одну из крайних комнат подземелья, пройти, причем только по одному разу, через все двери. Сокровища спрятаны за той дверью, которая будет пройдена последней. Найдите эту дверь на плане подземелья.
      3.17. В небольшой роще находится заяц. Выскочив из поры и бегая по снегу от дерева к дереву, он оставил следы и, наконец, спрятался под одним из этих деревьев. Где находится сейчас заяц? Под каким деревом находится его нора?
      3.18. Горожанам, посещающим острова А, В, С, D, разрешается проходить по каждому из мостов только один раз. Изучив маршрут, определите, на каком острове горожанам придется брать лодку, чтобы не оставаться ночевать в последнем пункте маршрута? у
      3.19. 3.20. Покажите, что рисунки графор; соответствующих системам мостов, являются уникурсаЛьными линиями. Совершите прогулку по мостам каждощиз этих систем такую, чтобы по каждому мосту и каждому отрезку путей между мостами проходить только один раз.