Rejtvények, ördöglakatok: A Hanoi tornyai feladvány gráfja

Bozóki Sándor

Rovatunkban minden hónapban valamilyen szórakoztató matematikai fejtörőt mutatunk be. Ezek között fontos helyet foglalnak el a különböző kirakós játékok, topológiai feladványok, ördöglakatok és a matematikát felhasználó bűvészmutatványok.

Manapság szinte mindent meg lehet találni az interneten, de az igazi élményt az adja, ha a feladatokat magunk oldjuk meg, a bűvészmutatványok trükkjeit mi találjuk ki, és a szükséges kellékeket is mi tervezzük meg és készítjük el. Próbáljuk meg a feladatokat továbbgondolni, általánosítani, igyekezzünk új feladatokat kitalálni.

A Hanoi tornyai egy olyan feladvány, amelyben három függőleges pálcán van \(\displaystyle n\) db, különböző külső átmérőjű lyukas korong [2]. A hagyományos kiindulási állapotban a bal szélső pálcán van az összes korong, fentről lefelé növekvő méretben, a célállapot pedig ugyanez a korongpiramis, csak a jobb szélső pálcán. Két egyszerű szabályt kell betartani: minden lépésben valamelyik pálca legfelső korongját tehetjük egy másik pálca tetejére, továbbá semelyik korongot sem szabad nála kisebb korongra tenni. Igazolható, hogy a szükséges lépésszám \(\displaystyle 2^n - 1\), azaz minden egyes korong hozzáadásával lényegében megduplázódik.

A 2024. szeptemberi [1] és novemberi [5] számokban már találkoztunk gráffal modellezhető feladványokkal. A Hanoi tornyai játék is ilyen, ráadásul az egyik legszebb gráffal rendelkezik. Az állapotokat reprezentáló csúcsok alkalmas geometriai elhelyezésével a Sierpińnski-háromszög [3] egy részgráfja adódik. A Hanoi tornyai rekurzív jellegét a gráfjaik is visszatükrözik: bármelyik Hanoi-gráf részgráfja minden, nála nagyobb korongszámú Hanoi-gráfnak.

A gráffal modellezhető feladatok egy részében nem feltétlenül szembetűnő a gráf geometriája.