Ханойська вежа

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

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

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

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

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

Походження

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

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

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

Розв'язання

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

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

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

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

Примітки
  1. Spitznagel, Edward L. (1971). Selected topics in mathematics. Holt, Rinehart and Winston. с. 137. ISBN 0-03-084693-5.
  2. Ivan Moscovich, 1000 playthinks: puzzles, paradoxes, illusions & games, Workman Pub., 2001 ISBN 0-7611-1826-8.
  3. Petković, Miodrag (2009). Famous Puzzles of Great Mathematicians. AMS Bookstore. с. 197. ISBN 0-8218-4814-3.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.