Лабіринти

2

Зміст

Історія виникнення лабіринту

Перші здогади «Правило правої руки»

Лабіринти і замкнені лінії

Лабіринти і графи

Лабіринти і теорія ймовірності

Використана література

Додатки

Історія виникнення лабіринту

Лабіринтами (від грецьк. лабіринтос) в давнину в Греції і Єгипті називали споруди зі складними заплутаними ходами, в які легко потрапити, і дуже важко вибратися. Уперше про один з них повідомив давньогрецький історик Геродот (бл. 484--431 або 425 рр. до н. є.). У другій книжці свого знаменитого твору «ІСТОРІЯ», він описав відвіданий ним велетенський Фаюмський лабіринт і розповів про історію його побудови. Цей найдавніший з відомих лабіринтів був заупокійним храмом, побудованим біля піраміди фараона Аменемхета III (1840--1792 р. до. н.е.).

В одному з найчарівніших давньогрецьких міфів розповідається про лабіринт крітського царя Міноса. Цю споруду вважають одним із семи чудес світу. У лабіринті Мінос переховував чудовисько, яке живилося людським м'ясом.

Син афінського царя Егея сміливий Тезей вирішив звільнити рідне місто від кривавої данини. Разом з юнаками і дівчатами, приреченими на жертву, він поплив на о. Кріт. Дочка Міноса Аріадна полюбила героя і взялася допомогти йому. Вона вручила Тезею меч і клубок ниток. Закріпивши кінець нитки біля входу, Тезей, блукаючи в лабіринті, розмотував нитку, чим позначав пройдений шлях. Герой зустрів чудовисько і в тяжкому поєдинку вбив його, а за ниткою Аріадни знайшов вихід із зачарованого палацу. Звідси й широко відомі метафори -- «лабіринт» -- безвихідне становище, заплутана ситуація, з якої немає розумного виходу і «аріаднина нитка» -- правильне розв'язання складної за дачі, щаслива ідея в заплутаній ситуації тощо.

Лабіринти -- одна із складних, ще не розв'язаних загадок історії. У різні часи ці дивні витвори у формі печер, палаців або споруд без покрівлі тощо з'являлися скрізь, де мешкала людина.

В епоху середніх віків у Європі схеми лабіринтів вимощували мозаїкою на підлогах соборів. Наприклад, такий лабіринт вимостили в XII ст. на підлозі Щартрського собору в Франції (мал. 3). Пізніше були поширеними паркові лабіринти. Найбільш відомий з них -- парковий лабіринт з кущів, влаштований у 1690 р. поблизу Лондона у володінні Вільгельма Оранського в саду Гемптон-Корта (мал. 2).

Навколо фортець у давнину споруджували системи валів у формі лабіринту, план якого знав тільки володар фортеці. Такі споруди служили для оборони і могли стати схованкою. Лабіринти використовували й для покарання. Засуджених до смерті відводили в лабіринт. Там, не знаючи його будови, приречений після марних блукань гинув від спраги й голоду.

Найбільшого поширення набули лабіринти-головоломки. Уже діти давніх греків і римлян заповнювали дозвілля такими розвагами, про що свідчить креслення, виявлене на стіні одного з будників міста Помпеї, засипаного попелом під час виверження вулкана Везувію в 79 р. Біля креслення лабіринту написано: «Лабіринт. Тут живе Мінотавр». З того часу і до наших днів ідея лабіринту стає в цікавій математиці все змістовнішою, збагачується новими мотивами задач. Урізноманітнюються самі форми лабіринтів, з'являються числові, об'ємні й інші лабіринти, де в несподіваних формах розвивається ідея, витоки якої губляться в прадавніх часах. Історії лабіринтів присвячено багато наукових досліджень і популярних видань.

Лабіринти широко застосовуються в науці і техніці. Психологи за їх допомогою вивчають поведінку людей і тварин у повторюваних або екстремальних ситуаціях. Кібернетикам лабіринти допомагають конструювати ЕОМ, зокрема роботів, які здатні до самонавчання. Такі експерименти першим провів американський математик Клод Шеннон (нар. 1916 р.): кібернетичні миші вченого за певними алгоритмами могли вибиратися із найзаплутаніших лабіринтів. За принципом лабіринту виготовляють глушителі в двигунах внутрішнього згорання, заповнюють частини деталей під високим тисом.

Перші здогади «Правило руки»

Якщо ви у лабіринті, то вихід з нього можна знайти закресливши тупікові коридори, тобто ділянки з яких немає виходу. Не закреслена частина і буде шуканим виходом з центра лабіринта, або маршрутом до його центру. (мал)

Якщо виходу з лабіринту немає, але ми знаємо, що він має бути, то задача теж може бути розв'язана. Потрібно йти, не відриваючи правої руки по коридору лабіринта.

Цей метод спрацьовує і тоді, коли потрібно пройти по всіх коридорах і вийти з лабіринту, за умови, що весь лабіринт складається з однієї, хоча і дуже розгалуженої, стіни (мал. 6). Застосувавши правило правої руки, легко потрапити до центра лабіринта Шартрського собору.

Можна просто побудувати лабіринт, застосувати до нього правило лівої або правої руки і таким чином знайти вхід і вихід, хоча потрапити до позначеного зірочкою центра (мал. 7) все ж таки не вдасться. Це стосується лабіринтів, які складаються з кількох розгалужених стін (мал. 8).

Побудовано лабіринти і складнішої форми. Лабіринт, придуманий у 1728 р. Бетті Ленглі, має три входи (мал. 9). До першого не можна застосувати правила ні правої, ні лівої руки, до другого -- правило лівої руки, до третього -- правої. До жодного з трьох входів лабіринту Версальського парку в Парижі не можна застосовувати ні правило лівої, ні правило правої руки (мал. 10).

Загальний метод розв'язання розглянутого типу лабіринтних задач запропонував у 1882 р. француз Тремо.

Увійшовши в лабіринт, додержуватимемо правила, наприклад, правої руки. Дійшовши перехрестя, йдемо в будь-якому напрямі, а якщо опинимося в тупику, повертаємося у вихідну точку. З неї йдемо в той коридор, у якому ще не були. Не можна входити в коридор, на обох стінах якого уже зроблено позначки про наше перебування. Правило Тремо можна перевірити, шукаючи шлях до позначених точками центрів квадратного і круглого лабіринтів, зображених па мал. 11 і 12.

Лабіринти і замкнені криві

Розв'язувати різні лабіринтні задачі можна, використовуючи деякі топологічні властивості замкнених ліній без самоперетинів. Далі ми говоритимемо тільки про такі замкнені лінії.

Можна довести, що коли кількість точок перетину дуги AB із замкненою кривою/непарне, то одна з точок А і В для фігури Ф зовнішня, а друга --- внутрішня (мал. 13). Щоб встановити, яка з двох точок (А або В) внутрішня для фігури Ф, достатньо провести два довільні промені з початком у точках А І В І полічити кількість точок перетину цих променів з кривою І. Якщо кількість точок перетину з кривою І непарне, то початок променя знаходиться у внутрішній області фігури Ф, якщо парне -- в зовнішній.

Справджується і така залежність: якщо кількість точок перетину відрізка (або дуги) CD із замкненою кривою / парне, то точки С ID одночасно розміщені або в зовнішній або у внутрішній області фігури Ф.

Використавши наведені властивості, можна розв'язати, наприклад, таку задачу:

Людина знаходиться в точці А (мал. 14). Чи є вихід Із цього лабіринту? Якщо є, знайдіть його.

Лабіринти і графи

До розв'язування лабіринтних задач можна застосувати елементи теорії графів. Коридори лабіринту зображатимемо ребрами, а входи, виходи, тупики, кімнати і перехрестя -- вершинами або вузлами. Тоді граф Гемптон-Кортського лабіринту (мал. 2) матиме вигляд (мал. 17). На ньому легко визначити всі можливі маршрути, і в тому числі оптимальний, до центра лабіринту. Але щоб граф міг подати вичерпну інформацію, потрібно уважно позначити всі елементи лабіринту і зобразити їх відповідними елементами графа. Для складних лабіринтів -- це досить копітка робота.

Залежно від того, парна чи непарна кількість ребер сходиться у вузлі графа, вузли називаються, відповідно, парними або непарними. Легко довести, що коли граф зовсім не має вузлів або має не більш як два непарних вузли, його можна накреслити, не відриваючи олівця від паперу і не проводячи двічі ліній по одному і тому самому ребру. Лінії, які можна так накреслити (одним розчерком) називаються унікурсальними. Звідси випливає, що далеко не всі лабіринти можна обійти-так, щоб проходити кожним коридором лише один раз. Така подорож можлива лише по лабіринту, графом якого є унікурсальна лінія. Наприклад, граф лабіринту на мал. 8 має чотири непарні вузли (мал. 18), тобто є не унінурсальною кривою. Тому здійснити прогулянку по цьому лабіринту так, щоб пройти по кожному коридору тільки один раз, не вдасться. Якщо ж зображати коридори не однією, а двома лініями, то графи всіх лабіринтів матимуть тільки парні вузли, тобто стануть унікурсальними лініями. Отже, будь-який лабіринт можна обійти, проходячи двічі кожним його коридором, тобто з кожного лабіринту є вихід. І це має підбадьорити читачів у пошуках ще двох цікавих лабіринтів. Перший з них (мал. 19) накреслив англійський математик і письменник Чпрлз Лютвідж Доджсон (1832--1898), який прославився в усьому світі під псевдонімом Льюїс Керролл як автор казок «Аліса в Країні Чудес» і «Аліса в Задзеркаллі». Цей лабіринт юний Доджсон, накреслив для розваги своїх домашніх. З нього зовсім нелегко вибратися. У другому лабіринті (мал. 20) знайдіть шлях від лівої стрілки (входу) до правої (виходу). Якщо ви зробите це за 8--10 хв. -- у вас добре розвинена увага.

Лабіринти і теорія ймовірностей

Щоб скарби з пірамід стали менш доступними для грабіжників, будівельники створювали там лабіринти, рухаючись по яких наймання, викрадачі часто гинули в ямах -- пастках. Картина, звичайно, сумна, та ми розглядаємо тільки математичний бік таких подій.

Людина рухається по лабіринту навмання, тобто зустрівши перехрестя вибирає той чи інший шлях з рівною імовірністю (якщо сходяться два шляхи -- то з імовірністю ¹/₂, якщо три -- ¹/₃).

Чому дорівнює ймовірність того, що шукач знайде скарб (мал. 21) і ймовірність того, що шукач загине?

Чому дорівнюють ці ймовірності для іншого лабіринту (мал. 22), якщо шукач скарбів може випадково блукати як завгодно довго і робити петлі?

Вивчаючи властивості лабіринтів і розв'язуючи різні лабіринтні задачі, ми ніде не розглядали і не використовували метричні властивості лабіринтів і їх графів. Це не випадково. Теорії лабіринтів і графів належать до топології-- математичної дисципліни, яка вивчає властивості фігур, інваріантні відносно всіх неперервних і взаємно однозначних перетворень. Такі властивості називаються топологічними і є найбільш глибокими, тривкими, оскільки зберігаються і в таких загальних перетвореннях.

Найпростіші лабіринтні задачі розв'язувати теж нелегко. У значно складнішому становищі опинялися ті, кому довелося прогулятися в справжньому лабіринті, навіть, якщо він був тільки розважальним атракціоном. Про це гарно написав відомий англійський письменник-гуморист Джером К. Джером у повісті «Троє в одному човні як не рахувати собаки».

Використана література

1. Бобров СП. Архимедово лето. М., 1959, кн. 1. 328 с.

2. Конфорович А. Г. Без поради Аріадни.-- Знання та праця, 1980, № 12. с. 12--17.

3. Куратов А. Каменные лабиринты Северной Европы.-- Наука и жизнь, 1971, Мі З. с. 37--46.

4. Саркисян А. А., Колягин Ю. М. Познакомьтесь с топологией. М., 1976. 292 с.

5. Толочко П. П. Таємниці київських підземель. К-, 1968.168 с.

6. Трахтенброт Б. А. Алгоритмы и машинное решение .задач. М., 1966. 292 с.

Додатки