Ханойська вежа
Ханойська вежа (також Вежа Брахми або Вежа Люка, іноді в множині Ханойські вежі) — математична гра або головоломка. Утворена трьома стрижнями і кількома дисками різних розмірів, які можна насунути на будь-який стрижень. Початковий стан головоломки має два порожніх стрижні і всі диски на третьому в монотонно спадному порядку з низу до гори, так утворюється побудова, що нагадує вежу.
Метою головоломки є перенести весь стос дисків на інший стрижень, дотримуючись таких правил:
- За раз можна рухати лише один диск.
- Кожен крок полягає в перенесенні верхнього диска з одного зі стрижнів на інший, на якому вже можуть знаходитися інші диски.
- Диск не можна класти поверх меншого за розміром диска.
З трьома дисками, головоломку можна розв'язати за сім кроків.
На Заході задачку вперше оприлюднив французький математик Едуард Люка у 1863. Існує легенда про храм в Індії, який містив велику кімнату з трьома стовпами і 64 золотими дисками на них. Протягом усього часу, жрець брахман, наслідуючи давньому пророцтву, переставляв ці диски згідно з правилами головоломки. Звідси друга назва головоломки — головоломка веж Брахми. Згідно з легендою, після завершального руху настане кінець світу.[1] Неясно, чи Люка вигадав цю легенду або надихнувся нею.
Якщо легенда правдива і якщо жрець може пересувати диски зі швидкістю один раз в секунду, найменша кількість необхідних для вирішення задачі переміщень займе в нього 264−1 секунд, або близько 585 мільярдів років[2] — це 18,446,744,073,709,551,615 секунд (або переміщень).
Існують й інші версії легенди, що різняться між собою у деталях. Так, наприклад, замість жреця може згадуватись монах, а замість храму — монастир, що може належати до будь-якої релігії і знаходитися в різних частинах світу — включно з Ханоєм, В'єтнам. В деяких варіаціях згадується, що вежі створили на початку світу, або що жрець чи монах може пересувати лише один диск на день.
Головоломку можна розв'язати для будь-якої кількості дисків, більшість іграшкових версій мають близько семи-дев'яти. Багатьом новачкам гра видається нерозв'язною, хоча існує простий алгоритм розв'язання. Кількість рухів необхідна для розв'язання становить 2n -1, де n — найменша кількість дисків.[3]
Наступний розв'язок є простим розв'язком для іграшкової головоломки.
Чергуйте рухи між найменшим і не найменшим дисками. Коли рухаєте найменший диск, завжди рухайте його до наступної позиції в одному напрямку (праворуч, якщо початкова кількість дисків парна і ліворуч, якщо непарна). Якщо в обраному напрямку немає вежі, пересувайте найменший диск до протилежного краю, тоді продовжуйте в обраному напрямку. Наприклад, якщо ви почали з трьома дисками, вам треба рухати найменший диск на протилежний край, тоді продовжити в напрямку ліворуч. Тоді черга не найменшого диску, тут ми маємо лише один варіант. Так ми завершимо головоломку, використавши найменшу кількість рухів для цього.
- ↑ Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. с. 137. ISBN 0-03-084693-5.
- ↑ Ivan Moscovich, 1000 playthinks: puzzles, paradoxes, illusions & games, Workman Pub., 2001 ISBN 0-7611-1826-8.
- ↑ Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. с. 197. ISBN 0-8218-4814-3.
- Weisstein, Eric W. Tower of Hanoi(англ.) на сайті Wolfram MathWorld.
- Ханойська вежа, каталог посилань Open Directory Project