Hanoi tornyai

A Wikipédiából, a szabad enciklopédiából
Hanoi tornyai modellje (8 koronggal)
A feladat animált megoldása

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[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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óbb (é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

Az elsőrendű lineáris inhomogén egyenletek megoldásánál tanultak alapján a ∆tn = tn + 1 egyenletbő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 580 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[szerkesztés | forrásszöveg szerkesztése]

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