Hanoi tornyai

A Hanoi tornyai matematikai játék, amihez a hasonnevű matematikai feladvány kapcsolódik. Ez úgy is ismert, mint Brahma tornyai, vagy világvége feladvány. A játék szabályai szerint az első rúdról az utolsóra kell átrakni a korongokat úgy, hogy minden lépésben egy korongot lehet áttenni, nagyobb korong nem tehető kisebb korongra, és ehhez összesen három rúd áll rendelkezésre.

A játékot 1883-ban Édouard Lucas francia matematikus találta fel. Az ötletet egy legendából kapta, ami szerint a világ megteremtésekor egy 64 korongból álló hanoi torony feladványt kezdtek el „játszani” Brahma szerzetesei. A szabályok azonosak voltak a ma ismert hanoi torony szabályaival. A legenda szerint, amikor a szerzetesek végeznek majd a korongok átjuttatásával a harmadik rúdra, a kolostor összeomlik, és a világunk megszűnik létezni.

A feladvány

A feladvány így szól a hanoi torony játékokban: Mennyi a legkevesebb szükséges lépés, amivel az első rúdról a harmadik rúdra lehet juttatni a korongokat, úgy, hogy nagyobb korongot kisebb korongra tilos mozgatni?

A feladvány megoldása

Legyen a legkisebb szükséges lépésszám t_n . A feladat megoldásához kell találni egy rekurzív relációt erre a számsorozatra. Vegyük észre, hogy ha n+1 korongunk van, nem tudjuk a legalsó korongot mozgatni, amíg az összes fölötte lévő korongot nem mozgatjuk át a középső rúdra. Mozgassuk hát át az összes a legnagyobb korong felett lévő korongot a középső rúdra, ez pontosan t_n lépésből hajtható végre. Ezt követően tudjuk csak a legalsóbb (és legnagyobb) korongot a harmadik rúdra mozgatni, ez egy lépésből hajtható végre. Most járunk t_n + 1 lépésnél. Most a második rúdon található n számú korongot mozgatjuk át a harmadik rúdra, ez további t_n lépésből valósítható meg. Tehát

t_{n + 1} = t_n + 1 + t_n = 2t_n + 1

t_n-t kivonva az egyenlőség két oldalából a következőt kapjuk:

∆t_n = t_n + 1

Az elsőrendű lineáris inhomogén egyenletek megoldásánál tanultak alapján a ∆t_n = t_n + 1 egyenletből következik, hogy

t_n = c2ⁿ – 1

bizonyos konstans c-re. Tudjuk, hogy t₁ = 1 (próbáljuk ki képzeletben a megoldást 3 rúddal és egy koronggal). Ezt felhasználva eljuthatunk c-hez:

1 = t₁ = c2¹ – 1 = 2c -1

Tehát c = 1. Ezért

t_n = 2ⁿ – 1.

A legenda szerinti példát alapul véve (64 korong) a megoldás:

t₆₄ = 18 446 744 073 709 551 615

lépés szükséges a feladat megoldásához. Ez hatalmas szám! Ha egy szerzetes éjjel-nappal dolgozna a feladaton másodpercenként egy lépést végrehajtva, akkor kicsit több mint 1000 milliárd év alatt tudná megoldani a feladatot. Emlékeztetőül, jelen pillanatban elfogadott nézetek szerint Földünk „még csak” 4,5 milliárd éves! Ha a feladat megoldását nem szerzetesekre, hanem szuperszámítógépekre bíznánk, az akkor is több millió évbe telne.

Források

Hanoi tornyai

A Wikimédia Commons tartalmaz Hanoi tornyai témájú médiaállományokat.