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.
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. (Geometriai gráfnak nevezik a síkban lerajzolt gráfokat, ahol tehát a csúcsok koordinátáinak is jelentősége van.) Lehet, hogy csak nem túl szerencsésen rendeztük el a csúcsokat, ezért nem igazán látható az élek által meghatározott struktúra. Ha azonban ügyesen választjuk meg a csúcsok helyét, a gráf azt is megmutatja magából, ami korábban rejtve maradt. Egyes játékoknál – sőt, talán inkább ez a tipikus – az is előfordulhat, hogy akármilyen ügyesen is helyezzük el a csúcsokat, a gráf továbbra sem mutat többet magából.
A Hanoi tornyai feladat esetében azonban egy kivételesen szép, rekurzív minta jelenik meg, egyike a legismertebb és a legkorábban felrajzolt fraktáloknak. Remek példája annak, amikor a matematika különböző területei találkoznak. Érdekes, hogy e kapcsolat feltárására bő hetven évet kellett várni [4].
Ha csak egyetlen (zöld) korongunk van, azt bármelyik másik pálcára áttehetjük. Az 1-korongos Hanoi-gráf tehát egy háromszög. Célszerű már itt bevezetni az él színezését: az él színe a mozgatott korong (esetünkben zöld) színével egyezzen meg.
Adjunk hozzá egy második, nagyobb (lila) korongot is! Ekkor attól függően, hogy a lila korong melyik pálcán van, három darab zöld háromszöget kapunk, hiszen a zöld korong mozgását a lila továbbra sem akadályozza. A három zöld háromszög az 1. ábra szerint kapcsolódik egymáshoz lila élekkel. Sokan már sejthetik, mi történik további korong(ok) hozzáadása esetén. A 2. ábra a 4-korongos Hanoi-tornyok gráfját mutatja. Az, hogy a legnagyobb (fekete) korong melyik pálcán helyezkedik el, a gráf egyik ,,harmadát'' határozza meg. Mindegyik harmad megfelel az eggyel kisebb korongszámú Hanoi-tornyok gráfjának, ha figyelmen kívül hagyjuk a fekete korongot: bármelyik harmad \(\displaystyle \pm 120 \) fokos elforgatottja a másik kettő.
1. ábra. A 2-korongos Hanoi tornyai feladat gráfja
A gráfban három fekete él van, hiszen a legnagyobb korongot csak akkor tudjuk mozgatni, ha az összes többi korong egyetlen pálcán van – ilyen állapotból három pár van, a nekik megfelelő csúcsok között futnak a fekete élek.
2. ábra. A 4-korongos Hanoi tornyai feladat gráfja
3. ábra. Egy Hamilton-út a 4-korongos Hanoi tornyai feladat gráfjában
Tekintsük a hagyományos feladványt: kezdetben minden korong a bal oldali pálcán van, és juttassuk el az összes korongot a jobb oldali pálcára. A megoldás útvonala a 2. ábrán egy nyílegyenes, vízszintes út a nagy háromszög vízszintes oldala mentén. Aki próbálkozott már a Hanoi tornyai játékkal, bizonyára felismeri a megoldás menetét.
Még izgalmasabb, ha tetszőleges kiindulási, illetve célállapotot megengedünk, akár egyidejűleg. Legyen például a kiindulási állapot az, amelyikben a fekete korong középen, az összes többi a jobb oldalon van. A célállapotban pedig legyen a fekete korong a jobb oldalon, az összes többi pedig középen. Keressük meg a 2. ábra alapján a legrövidebb utat, azaz a legkevesebb lépést igénylő megoldást! Hányszor helyeztük át a fekete korongot? Természetesen könnyen lehet a fekete korong egyetlen áthelyezésével is megoldást találni, de az majdnem kétszer annyi lépést igényel.
Végezetül a 3. ábra a 4-korongos Hanoi tornyai feladvány gráfjában mutat egy Hamilton-utat.
[1] Kós Géza: Átkelés a folyón, KöMaL, 2024. szeptember.
[2] F. É. A. Lucas: La Tour d'Hanoï, 1883. https://www.cs.wm.edu/~pkstoc/page_1f.html, https://www.cs.wm.edu/~pkstoc/page_2f.html
[3] W. Sierpińnski: Sur une courbe dont tout point est un point de ramification, C. R. A. S. 160, (1915) 302–305.
[4] I. Stewart (1987): Another Fine Math You've Got Me Into, Oxford University Press
[5] Vígh Viktor: Gráffal modellezhető logikai játékok, KöMaL, 2024. november
Jó szórakozást!
A KöMaL levelezős versenyei azon kevesek közé tartoznak, amelyek ingyenesek – immár több mint 130 éve! Sajnos azonban a KöMaL állami támogatásának rendszere az elmúlt évben jelentősen átalakult, a következő években az előre látható bevételeink várhatóan nem tudják fedezni a költségeinket.
Ezért kérünk mindenkit, aki szereti a KöMaL-t, létezését fontosnak tartja, hogy lehetőségéhez mérten támogassa a KöMaL-t kiadó MATFUND Alapítványt. Ha teheti, rendelkezzen adója 1%-áról az Alapítvány javára. Ezen kívül pedig, ha saját vagy céges lehetőségei megengedik, támogassa a KöMaL kiadását, a KöMaL tudáskincsének gondozását!
A KöMaL kiadásának, a versenyek teljes lebonyolításának, díjazásának és a díjkiosztóval egybekötött Ifjúsági Ankétok szervezésének költségeit 2007 óta a MATFUND Középiskolai Matematikai és Fizikai Alapítvány fizeti.
Kérjük, személyi jövedelemadója 1%-ának felajánlásával álljon a több, mint 125 éve alapított Középiskolai Matematikai és Fizikai Lapok mellé!
Legutóbb szeptemberi számunkban foglalkoztunk bújócska típusú ördöglakatokkal. Elkészítésre ajánlottunk olvasóinknak egy pálcás változatot, ahol a ,,szokásos'' trükk nem működik, mivel az átbújtatás után (lásd ábra) a pálca nem fér át a hurkon a zsinór rövidsége miatt. Azonban vegyük észre, hogy ebben az átbújtatott állapotban valójában annyi a célunk, hogy a hurok a dupla zsinór másik oldalára kerüljön. Ezt úgy is elérhetjük, ha a téglatest formájú ,,alapot'' bújtatjuk át a hurkon.
Ha egy négyzetet a két átlójával felosztunk négy háromszögre, majd ezeket kiszínezzük három színnel az összes lehetséges módon, akkor megkapjuk a négyzetes színdominókat.
A színdominókat először a múlt század elején írta le Percy Alexander MacMahon, a kalandos életű matematikus. Ő rögtön megadott több nehéz feladatot is hozzájuk.
