Ханойська вежа (також Вежа Брахми або Вежа Люка, іноді в множині Ханойські вежі) — математична гра або головоломка. Утворена трьома стрижнями і кількома дисками різних розмірів, які можна насунути на будь-який стрижень. Початковий стан головоломки має два порожніх стрижні і всі диски на третьому в монотонно спадному порядку з низу до гори, так утворюється побудова, що нагадує вежу.

Метою головоломки є перенести весь стос дисків на інший стрижень, дотримуючись таких правил:

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

З трьома дисками, головоломку можна розв'язати за сім кроків.

Походження

На Заході задачку вперше оприлюднив французький математик Едуард Люка у 1863. Існує легенда про храм в Індії, який містив велику кімнату з трьома стовпами і 64 золотими дисками на них. Протягом усього часу, жрець брахман, наслідуючи давньому пророцтву, переставляв ці диски згідно з правилами головоломки. Звідси друга назва головоломки — головоломка веж Брахми. Згідно з легендою, після завершального руху настане кінець світу. Неясно, чи Люка вигадав цю легенду або надихнувся нею.

Якщо легенда правдива і якщо жрець може пересувати диски зі швидкістю один раз в секунду, найменша кількість необхідних для вирішення задачі переміщень займе в нього 264−1 секунд, або близько 585 мільярдів роківIvan Moscovich, 1000 playthinks: puzzles, paradoxes, illusions & games, Workman Pub., 2001 ISBN 0-7611-1826-8. — це 18,446,744,073,709,551,615 секунд (або переміщень).

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

Розв'язання Головоломку можна розв'язати для будь-якої кількості дисків, більшість іграшкових версій мають близько семи-дев'яти. Багатьом новачкам гра видається нерозв'язною, хоча існує простий алгоритм розв'язання. Кількість рухів необхідна для розв'язання становить 2n -1, де n — найменша кількість дисків.

Ітеративний розв'язок Наступний розв'язок є простим розв'язком для іграшкової головоломки.

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

Примітки

Посилання