Ханойська вежа також Вежа Брахми або Вежа Люка іноді в множині Ханойські вежі математична гра або головоломка Утворена т

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

Приклад ханойської вежі із вісьмома дисками

Анімоване розв'язування задачі **Ханойська вежа** для *T(4,3)*.

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

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

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

Походження

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

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

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

Розв'язання

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

Ітеративний розв'язок

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

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

Примітки

Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. с. 137. ISBN .
Ivan Moscovich, 1000 playthinks: puzzles, paradoxes, illusions & games, Workman Pub., 2001 .
Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. с. 197. ISBN .

Посилання

Вікісховище має мультимедійні дані за темою: Ханойська вежа

Weisstein, Eric W. Tower of Hanoi(англ.) на сайті Wolfram MathWorld.
Ханойська вежа, каталог посилань Open Directory Project

[1] Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. с. 137. ISBN .

[2] Ivan Moscovich, 1000 playthinks: puzzles, paradoxes, illusions & games, Workman Pub., 2001 .

[3] Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. с. 197. ISBN .