Gál Péter
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.
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. Két színezést akkor tekintünk egyformának, ha síkbeli forgatással egymásba vihetők. Tehát a tükörképek (pl. az 1. ábra alsó sorának 4. és 5. eleme) különbözőek.
1. ábra
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. Például: rakjunk ki az összes elemből egy téglalapot úgy, hogy oldalak mentén csak azonos színek érintkezzenek. A 2. ábra mutat egy lehetséges megoldást.
2. ábra
Érdemes elkészíteni az 1. ábrán látható MacMahon-féle készlet elemeit. A fenti \(\displaystyle 4\times6\)-os téglalapon kívül még a szóba jöhető \(\displaystyle 2\times12\)-es és \(\displaystyle 3\times8\)-as is kirakható belőlük, igaz, hogy csak úgy, ha nem kívánjuk meg, hogy a téglalap kerületére csupa azonos szín kerüljön. Próbáljuk meg megoldani ezeket a feladatokat!
Ha néhány elemet elhagyunk, kisebb téglalapokat is ki tudunk rakni. Minden olyan téglalap kirakható, ami 24 vagy annál kevesebb négyzetből áll, és mindkét oldala egész. Érdekes megvizsgálni, hogy közülük vajon melyikek rakhatók úgy ki, hogy a keretük egyféle színű legyen. (Lásd a cikk végén kitűzött feladatokat.)
Mindazonáltal 24 elem elég sok egy jó játékhoz. Más összerakó játékoknál tapasztalhatjuk, hogy 7, 10 vagy 12 elemből is meglepően nehéz feladványok készíthetők. Felmerülhet az ötlet, hogy ne 3 színt használjunk, illetve ne engedjük meg a színek ismétlődését egy elemen belül – ezekkel kapcsolatban szintén lásd a cikk végén kitűzött feladatokat. Természetes gondolat az is, ha más alakzatokból álló játékot keresünk.
A szabályos sokszögek közül a négyzeten kívül az egyenlő oldalú háromszög és a hatszög alkalmas arra, hogy a síkot csempézze (más szóhasználattal parkettázza), vagyis hézagmentesen, átfedés nélkül lefedje. Ezekből is érdekes, játékra alkalmas színdominók készíthetők.
Ha a szabályos háromszög középpontját kötjük össze a csúcsaival, akkor három egybevágó háromszögre bontjuk. Ezeket kiszínezve kaphatjuk a háromszög színdominóit (3. ábra). Talán meglepő, hogy négy színnel éppúgy 24-féle színdominót készíthetünk, mint három színnel négyzetet.
Ezekből az elemekből pl. paralelogrammákat lehet kirakni és egészen hasonló kérdések vethetők fel, mint a négyzetes kirakónál.
Játszhatóság szempontjából lényegesen más a helyzet a hatszögekkel. Ha három színt használunk a színezéshez, amelyek ismétlődhetnek is, akkor 100-nál több elemet kapunk. Szintén száz feletti az elemek száma hat szín ismétlődés nélküli használata esetén. Két szín használata viszont érdekes készlethez és kérdésekhez vezet. Ebben az esetben 14 különböző elemet kapunk (4. ábra).
Ez az elemkészlet még kevéssé vizsgált, de az már kiderült róla, hogy jó nehéz feladványok létrehozására alkalmas! Részletesebb elemzése majd egy másik cikk témája lesz. Próbáljunk hozzá mi magunk érdekes feladványokat kitalálni!
3. ábra
4. ábra
A 2. ábrán látható téglalap kerete egyszínű. Ha sok készletünk lenne MacMahon négyzeteiből, akkor a fenti kirakást minden irányban megismételhetnénk, hiszen csupa kék mezőből áll a körvonala, ezért egy másik ugyanilyen téglalap mellé helyezhető. Ha ezt a kirakást periodikusan ismételgetjük, a teljes síkot ki tudjuk színdominóinkkal csempézni. A periodikus csempézés könnyen érthető fogalom: létezik olyan (nem nulla vektorral történő) eltolás a síkon, ami a csempézést önmagába viszi. (Csempénként értelmezve: egy csempézés periodikus, ha van olyan eltolás, amelyre minden csempe eltolt képe vele azonosan színezett csempe.) A periodikus csempézésnek bizonyos értelemben az ellentéte az aperiodikus csempézés. Ez tehát azt jelenti, hogy az egész síkot csempézzük színdominókkal, de nincs olyan (nem nulla vektorral történő) eltolás a síkon, amit erre a fedésre alkalmazva a színezés nem változik meg. (Lásd 5. feladat.)
Sokáig azt gondolták, hogy ugyanúgy viselkednek a különböző módokon színezett négyzetes színdominók: ha egy készlettel ki lehet csempézni a síkot, akkor periodikusan is ki lehet csempézni. Ha megengedjük a dominók elforgatását, ez nem túl érdekes kérdés, hiszen egy tetszőleges színdominó és 180 fokos forgatottja segítségével a sík periodikusan csempézhető. (Hogyan?) Ezért a továbbiakhoz feltesszük, hogy a színdominók állása rögzített, azokat nem forgathatjuk el.
De hogyan lehet eldönteni, hogy egy színdominó elemkészlet jó-e, azaz ki lehet-e vele csempézni a síkot? Van-e erre valami jó módszer, létezik-e rá algoritmus, amivel esetleg egy – kellően gyors – számítógép segítségével mindig válaszolhatunk a kérdésre? Ezt a kérdést nevezték el ,,csempézési problémának''.
1961-ben Hao Wang amerikai matematikus azt sejtette, hogy minden jó készlet periodikus, azaz ha egy készlet csempézi a síkot, akkor periodikusan is tudja ezt. Wang megadott egy algoritmust, ami egy input dominókészletről eldönti, hogy jó-e vagy sem. Továbbá azt is észrevette, hogy ez az algoritmus akkor és csak akkor áll le biztosan, ha sejtése igaz, azaz minden jó dominókészlettel periodikusan is le lehet fedni a síkot [1]. Ezen eredmény tiszteletére a színezett négyzetekből álló készleteket Wang dominóknak vagy Wang csempéknek nevezzük.
Aztán 1966-ban Wang tanítványa, Robert Berger megcáfolta mestere sejtését, talált egy dominókészletet, amivel ugyan ki lehet csempézni a síkot, de csak aperiodikusan, s azt is belátta, hogy a dominó csempézési probléma algoritmikusan nem megoldható. (Hasonlóan a Turing-gép megállási problémájához, csak ez sokkal könnyebben érthető, sokkal játékosabb feladvány.)
Berger dominókészlete több mint 20 ezer elemből állt, ami a tényleges megvalósítást szinte lehetetlenné tette. Azóta számos matematikus próbálkozott minél kevesebb darabszámú és színű készlet megalkotásával, amivel a sík csak aperoidikusan csempézhető. 2019-ben Emmanuel Jeandel és Michaël Rao [2] francia matematikusok, számítástudományi szakemberek megalkottak egy 11 elemből álló készletet, amihez mindössze 4 színre volt szükségük. Készletük elemei az 5. ábrán láthatóak. (Az ő definíciójuk szerint a csempézéshez nem forgathatók el a négyzetek, tehát csak olyan állásban használhatók, ahogy az ábrán lerajzoltuk.) Azt is bebizonyították, hogy ez lehető legkevesebb elemből és színből álló készlet.
5. ábra
Ez annyira kevés elem, hogy akár már játszani is alkalmas. A 6. ábrán egy \(\displaystyle {20\times20}\)-as téglalap látható Jeandel és Rao csempéiből kirakva. Lehet próbálkozni még nagyobb területek létrehozásával!
A cikket néhány kapcsolódó feladvánnyal zárjuk. (A feladatokban szereplő alakzatokat nem tekintjük különbözőknek, ha azok egymásba forgathatók.)
1. Ha csak 2 színt használhatunk, hányféle négyzetes elem készíthető?
2. Hány különböző négyzetes elem készíthető 4 színnel, ha minden négyzeten minden színnek szerepelni kell?
6. ábra
3. Hány különböző négyzetes elem készíthető 5 színnel, ha a színek egy elemen belül nem ismétlődhetnek?
4. Keressünk példát olyan, a MacMahon-féle készletből elkészíthető, 24-nél kisebb területű téglalapra, amely kirakható úgy, hogy a kerete egyszínű, és olyanra is, ami nem rakható ki ilyen módon!
5. Adjuk meg a sík egy aperiodikus csempézését a MacMahon négyzetekkel! (Nem feltétlenül szükséges az összes elemet felhasználni.)
6. Mutassuk meg, hogy a 4. ábrán látható hatszögekkel kirakható olyan alakzat, amit sokszor egymás mellé helyezve a sík egy periodikus parkettázását kapjuk!
[1] Hao Wang. Proving theorems by Pattern Recognition II. Bell Systems Technical Journal, 40:1–41, 1961.
[2] Emmanuel Jeandel and Michaël Rao. 2021. ``An Aperiodic Set of 11 Wang Tiles.'' Advances in Combinatorics, January. https://doi.org/10.19086/aic.18614.
Jó szórakozást!
A cikk szövegét a publikálás után, 2026. január 26.-án pontosítottuk.
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.
Nem kell túl sokáig keresgélnünk az interneten a fejtörő feladatok között ahhoz, hogy sík vagy tér kitöltésére vonatkozó feladványra bukkanjunk. Ezek egyik fajtája az, amikor néhány síkidom vagy test valamilyen keretben van elhelyezve úgy, hogy látszólag teljesen kitöltik azt, de van még külön egy további eleme a játéknak.
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.
