Hanoi tornyai lépésszámláló

A Hanoi tornyai a matematika egyik legismertebb fejtörője: három rúd, és az egyiken egymásra rakott, felfelé egyre kisebb korongok. A feladat egyszerűnek tűnik, a szükséges lépések száma azonban robbanásszerűen nő. A lépésszámláló pontosan kiszámolja a minimális lépésszámot bármennyi (legfeljebb 1000) korongra, megbecsüli, mennyi ideig tartana a megoldás a választott tempóban, és legfeljebb 8 korongig animációval meg is mutatja az optimális megoldást.

A szabályok

• Egyszerre csak egy korongot szabad áthelyezni.
• Mindig csak egy rúd legfelső korongját mozgathatjuk.
• Nagyobb korong soha nem kerülhet kisebbre.
• A cél: az összes korongot átvinni az első rúdról a harmadikra.

Hogyan használd?

1. Add meg a korongok számát (a csúszka 64-ig, a mező 1000-ig enged).
2. Állítsd be a tempót: hány lépést teszel meg másodpercenként.
3. Olvasd le a lépésszámot és az időtartamot; nagyon nagy számoknál a teljes, minden jegyet tartalmazó érték lenyitható.
4. A szemléltetésnél válassz 1–8 korongot, és indítsd el az animációt, vagy lépkedj egyenként.

Miért pontosan 2ⁿ − 1 lépés?

Gondolkodjunk visszafelé. A legnagyobb korongot csak akkor tudjuk áttenni, ha fölötte nincs semmi, és a célrúd üres – vagyis a többi n − 1 korongnak a középső rúdon kell lennie. Ehhez T(n − 1) lépés kell, utána 1 lépés a legnagyobb korong, majd újabb T(n − 1) lépés, hogy a kisebbeket ráépítsük. Így T(n) = 2 · T(n − 1) + 1, és mivel T(1) = 1, teljes indukcióval T(n) = 2ⁿ − 1. Ennél rövidebb megoldás nem létezik, mert a fenti gondolatmenet minden lépése elkerülhetetlen.

A lépésszám minden új koronggal megduplázódik (plusz egy): 3 korongnál 7, 10 korongnál 1023, 20 korongnál már 1 048 575 lépés.

A legenda és a 64 korong

A fejtörőhöz egy 19. századi legenda is tartozik: egy templomban szerzetesek 64 aranykorongot raknak át a szabályok szerint, másodpercenként egyet, és amikor végeznek, eljön a világvége. A kalkulátor szerint ehhez 18 446 744 073 709 551 615 lépés kell, ami másodpercenként egy lépéssel kb. 584,5 milliárd év – az Univerzum mai korának (kb. 13,8 milliárd év) több mint negyvenszerese. Nyugodtan alhatunk.

A számolás pontossága

A 2⁶⁴ − 1 már nem fér el pontosan a szokásos lebegőpontos számokban, ezért a kalkulátor tetszőleges pontosságú egészekkel dolgozik: 1000 korongnál is mind a 302 számjegyet pontosan megkapod. Az időtartamot évekre a 365,25 napos (Julián-) évvel számoljuk, és a magyar nagyságrendneveket használjuk (milliárd = 10⁹, billió = 10¹²).

Gyakori kérdések

Van egyszerű szabály az optimális megoldáshoz?

Igen. Ha a korongokat az A rúdról a C rúdra visszük, páratlan számú korongnál a legkisebb korong körbe jár az A → C → B → A irányban, páros számúnál az A → B → C → A irányban. Minden második lépésben a legkisebb korong lép, a köztes lépésekben pedig mindig csak egyetlen szabályos lépés van, amely nem a legkisebb korongot mozgatja.

Mire jó ez a fejtörő?

Kiváló bevezetés a rekurzív gondolkodásba és az exponenciális növekedés megértésébe, a pszichológiában pedig a tervezési és végrehajtó funkciók vizsgálatára is használják.