Közel 3500 éve Ganésa, a tudomány és bölcsesség istene megparancsolta papjainak, hogy egy titkos templomban helyezzenek el három hatalmas, égnek meredő gyémánt pálcát és a szélsőre rakjanak 64 egyre csökkenő méretű arany korongot. Minden nap hajnalán a főpap áthelyezhet egyetlenegy korongot egy másik pálcára, de soha nem lehet nagyobb korong kisebben. Amennyiben vétenek a szabályok ellen vagy kimarad egy nap, Jama, a halál istene azonnyomban pusztulást hoz a földre. Ameddig viszont szabályosan tart az átrakodást, békében és boldogságban élhetnek az emberek, ha tudnak.

Se gyémánt pálcáim, se arany korongjaim nincsenek, bráhman pap sem vagyok, de fából én is megvalósítottam Ganésa óhaját. Igaz, hogy csak 6 koronggal, de így is érdekes játékot kaptam:

A játék célja tehát az összes korong átjuttatása a középső pálcára úgy, hogy egyszerre csak egy korongot mozdíthatunk és soha nem lehet kisebb korongon nagyobb.

Azt hiszem, a történelemben nem volt még egy ennyire optimista világvége-jóslat. Később majd látni fogjuk, hogy 64 korong áthelyezéséhez 2⁶⁴-1 = 18446744073709551616 lépésre van szükség. Ha minden nap egyet szabad áthelyezni, akkor az egész torony átpakolása több mint 50 ezer billió évig fog tartani. Na, jó, ebből már letelt 3500 év, de azért még nem kell nagyon izgulnunk. Különösen annak fényében, hogy ma a csillagászok még 5-10 milliárd évre becsülik a Nap várható élettartamát. A torony átrakása ennél több mint 10 milliószor több időt igényel.

De hogyan lehet egyáltalán átrakni az egész tornyot? Nem kevés ehhez a 3 pálca?

Gondolkozzunk visszafelé! Ahhoz, hogy az utolsó, legnagyobb korongot megmozdíthassuk, a nála kisebbeket át kell rakni a jobbszélső pálcára. Vagyis ilyen állást kell létrehoznunk:

Mondhatjuk, hogy először az 5 korongos játékot kell megoldani, 5 korongot kell átvinni jobbra.

Ezután átrakhatjuk a legnagyobb korongot:

Majd ismét egy 5 korongos tornyot, a jobb szélsőt kell átraknunk középre, hogy elérjük a célt:

De hogy tudjuk létrehozni a 2. képen látható állapotot? Ehhez az utolsó előtti korongot rá kell tenni az üres jobbszélső pálcára, előtte pedig a többit a középsőre. Így:

Ezután csak a középső pálcán lévő 4 korongos tornyot kell jobbra helyeznünk.

Láthatjuk, hogy X korong áthelyezéséhez először át kell rakni X-1-et az "átmeneti" pálcára, aztán az X-dik áttehető a célhelyre, majd az "átmeneti" pálcáról megint X-1 korongot kell átrakni a célba.

Így X korong átrakásához kétszer annyi lépést kell megtenni, mint X-1-hez és ráadásul mégegyet. Ha H(X)-szel jelöljük az X emeletes torony megoldásához szükséges lépésszámot, akkor:

H(X) = 2*H(X-1)+1

Egy korongot 1 lépéssel át tudunk helyezni. Így nem kell a fenti X-eket a végtelenségig csökkentgetni, 1-nél meg lehet állni.

Ebből könnyen belátható, hogy H(X) = 2^X-1. Vagyis az én 6 korongos változatomat a legjobb esetben is 2⁶-1=63 lépésben lehet megoldani. (Ha matekot tanítanék, biztos ezzel a játékkal vezetném be a teljes indukciót :))

A bevezetőben leírt meséből természetesen semmi sem igaz. A játékot Édouard Lucas francia matematikus találta ki, lehet, hogy az indiai legendát is ő költötte hozzá. Egy másik eredet történet szerint a templom Hanoiban, Vietnámban állt, ez az elnevezés terjedt el jobban.

A "Hanoi tornyok" rendkívül sok helyen felbukkannak. Az oktatásban felhasználható matematika órán a kettő hatványok vagy az indukció oktatására. Nagyon egyszerű rekurzív algoritmus készíthető a megoldás megkeresésére, így a programozással ismerkedőknek is jó feladat. De nem túl nehéz kapcsolatot találni a tornyok és a fraktálok között sem.

Hogy ki lehessen próbálni a játékot, nincs szükség pálcákra, lyukas korongokra. Megfelelnek egymásra helyezett, különböző méretű pénzérmék vagy a kár tányérok is. Javaslom az olvasónak, hogy próbálja ki a játékot, kellemes perceket fog okozni! Az is jó benne, hogy a korongok számának csökkentésével egész kis gyerekek is sikeresen játszhatnak vele. 3 koronggal még kisóvodások is megbirkóznak, 5-6 korong azonban még a játékkal most ismerkedő felnőtteket is meg tudja tréfálni.