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 vette, ami szerint a világ megteremtésekor egy 64 korongból álló tornyot kezdtek átmozgatni 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[szerkesztés]
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[szerkesztés]
Legyen a legkisebb szükséges lépésszám tn . 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 tn lépésből hajtható végre. Ezt követően tudjuk csak a legalsó (és legnagyobb) korongot a harmadik rúdra mozgatni, ez egy lépésből hajtható végre. Most járunk tn + 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 tn lépésből valósítható meg. Tehát
tn + 1 = tn + 1 + tn = 2tn + 1
tn-t kivonva az egyenlőség két oldalából a következőt kapjuk:
∆tn = tn + 1
Ebből következik, hogy
tn = c2n – 1
bizonyos konstans c-re. Tudjuk, hogy t1 = 1 (próbáljuk ki képzeletben a megoldást 3 rúddal és egy koronggal). Ezt felhasználva eljuthatunk c-hez:
1 = t1 = c21 – 1 = 2c -1
Tehát c = 1. Ezért
tn = 2n – 1.
A legenda szerinti példát alapul véve (64 korong) a megoldás:
t64 = 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.
Források[szerkesztés]
