PROFILPELAJAR.COM

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

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

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

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

Походження

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

Якщо легенда правдива і якщо жрець може пересувати диски зі швидкістю один раз в секунду, найменша кількість необхідних для вирішення задачі переміщень займе в нього 2⁶⁴−1 секунд, або близько 585 мільярдів років^[2] — це 18,446,744,073,709,551,615 секунд (або переміщень).

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

Розв'язання

Головоломку можна розв'язати для будь-якої кількості дисків, більшість іграшкових версій мають близько семи-дев'яти. Багатьом новачкам гра видається нерозв'язною, хоча існує простий алгоритм розв'язання. Кількість рухів необхідна для розв'язання становить 2ⁿ -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.