Információk

Főmenü

 Aktuális szám: 35. szám 2025. március 

Fraktálok és káosz egy egyszerű kombinatorikus játékban

Fraktálok és káosz egy egyszerű kombinatorikus játékban

 

 

Ebben a cikkben egy egyszerű kombinatorikus játékot mutatunk be, amely középiskolás szinten is megérthető, ugyanakkor gazdag és érdekes matematikai tulajdonságokkal rendelkezik, számos nyitott kérdéssel. A kivonós játékot két játékos játssza a következő szabályokkal. Adott egy pozitív egész szám, $n$, és pozitív egész számok véges halmaza, $A$. Elhelyezünk $n$ db kavicsot egy asztalra, és a két játékos felváltva vesz el a kavicsokból. Minden lépésben az elvett kavicsok száma meg kell, hogy egyezzen az $A$ halmaz valamely elemével, de ezen felül semmi további kikötés nincsen, az $A$ halmaz bármelyik eleme akármelyik játékos által akármikor, akárhányszor választható a játék során. Ha az asztalon levő kavicsok száma kevesebb, mint az $A$ halmaz minimuma, akkor az aktuálisan lépő játékos elveszítette a játékot, és a másik játékos nyert. Az alapkérdés az, hogy adott $n$ és $A$ halmaz esetén melyik játékosnak van nyerő stratégiája, azaz melyik játékos az, aki mindenképpen meg tudja nyerni a játékot, bárhogyan is játszik a másik játékos. Az olvasókat buzdítjuk arra, hogy próbálják maguk bizonyítani a következő állítást, mielőtt elolvasnák a bizonyítást.

1. Állítás. Legyen $A=\{1,2,3,4\}$ és $n=20$. Ekkor a második (azaz nem a kezdő) játékosnak van nyerő stratégiája.

Bizonyítás. A nyerő stratégia az, hogy minden fordulóban, ha az első játékos $k$ kavicsot vesz el, a második játékos $5-k$ kavicsot vesz el. Ez mindig lehetséges, hiszen az $A$ halmaz minden lehetséges $k$ elemére igaz az, hogy az $A$ halmaz az $5-k$ elemet is tartalmazza. Így az első forduló után 15 kavics marad, a második forduló után 10, a harmadik forduló után 5, a negyedik forduló után pedig 0 kavics marad, akárhogyan is játszik az első játékos. Ezután az első játékos nem tud lépni, így a második játékos nyert. $\qedsymbol$

Mi a helyzet, ha továbbra is $A=\{1,2,3,4\}$, de $n=23$? Könnyen belátható, hogy ebben az esetben a kezdő játékosnak van nyerő stratégiája. Valóban, az első játékos az első lépésben 3 kavicsot vesz el. Ekkor 20 kavics marad, tehát a helyzet most megegyezik az előbbi játékkal, de most a második játékos lép először, és el fogja veszíteni a játékot, amennyiben az első játékos az előző bizonyításban leírt stratégiát követi.

Általánosan is igaz, hogy ha egy adott állásban az aktuálisan lépő játékosnak van olyan lépése, amely olyan álláshoz vezet, amelyben a második játékosnak van nyerő stratégiája, akkor az aktuális játékos meg tudja nyerni a játékot. Azonban ha minden lehetséges lépés olyan álláshoz vezet, amelyben a kezdő játékosnak van nyerő stratégiája, akkor az aktuális játékos elveszíti a játékot. Definiáljuk az $f_A(n)$ függvényt a következőképpen. Legyen $f_A(n)=1$, ha n kaviccsal kezdve az első játékosnak van nyerő stratégiája abban a játékban, amelyben az elvehető kavicsok számát az $A$ halmaz adja meg, és legyen $f_A(n)=0$, ha a második játékosnak van nyerő stratégiája. Ekkor teljesül a

$\displaystyle f_A(n)=1-\min\limits_{x\in A} \{f_A(n-x)\} $

egyenlőség. Valóban, $f_A(n)$ 1 lesz, amennyiben $\min\limits_{x\in A} \{f_A(n-x)\}=0$, azaz van olyan $x\in A$, hogy $f_A(n-x)=0$, azaz az első játékos el tudja navigálni a játékot egy olyan állásba, ahonnan kezdve a második játékosnak van nyerő stratégiája. Ha azonban $\min\limits_{x\in A} \{f_A(n-x)\}=1$, akkor $f_A(n)$ 0 lesz, mert az első játékos bármelyik lépésére az ellenfelének lesz nyerő stratégiája.

Az olvasókat megint biztatjuk, hogy a következő állítást próbálják meg bizonyítani mielőtt elolvasnák a bizonyítást.

2. Állítás. Bármely véges $A$ halmazra az $f_A(n)$ függvény időben periodikussá válik, azaz létezik olyan $n_0$ és $p$, hogy minden $n\ge n_0$-ra $f_A(n)=f_A(n+p)$.

Bizonyítás. Legyen $F_A$ egy, a $\max\{A\}$ hosszúságú 0-1 vektorokat $\max\{A\}$ hosszúságú 0-1 vektorokba képező függvény a következő hozzárendelési szabállyal. Ha $Z=(z_0,z_1,\dots ,z_{\max\{A\}-1})$, akkor

$\displaystyle F_A(Z)=\Bigl(z_1,z_2,\dots z_{\max\{A\}-1},1-\min\limits_{x\in A} \{z_{\max\{A\}-x}\}\Bigr) $

Vegyük észre a következőt. Ha $Z_0:=(f_A(0),f_A(1),\dots ,f_A(\max\{A\}-1))$, akkor $Z_1:=F_A(Z_0)=(f_A(1),f_A(2),\dots ,f_A(\max\{A\}))$, és rekurzívan minden n-re $Z_n:=F_A(Z_{n-1})=(f_A(n),f_A(n+1),\dots ,f_A(\max\{A\}+n-1))$. Mivel $F_A$ egy véges halmazból ugyanabba a véges halmazba képező függvény, skatulya elv alapján lesznek olyan $p_1<$ $p_2$ számok, hogy $Z_{p_1}=Z_{p_2}$. De ekkor $Z_{p_{1+1}}=Z_{p_{2+1}}$, stb. azaz a $Z_n$ vektorok $p_2-p_1$ periódussal ismétlődnek. Így az $f_A(n)$ értékek is. $\qedsymbol$

Mivel a lehetséges $\max\{A\}$ hosszúságú 0-1 vektorok száma $2^{\max\{A\}}$, ez egy felső határ a periódushosszára. Nyitott kérdés, hogy létezik-e ($\max\{A\}$ függvényében) exponenciális periódushossz. A játék egy kissé módosított változatában sikerült nemrégiben szuperpolinomiális periódushosszakat bizonyítani [4]. A tipikus periódushossz azonban általában lineáris vagy még rövidebb hosszúságú $\max\{A\}$ függvényében. Pl. belátható, hogy ha $A=\{a_1,a_2\}$, akkor a periódushossz $2a_1$ ha $a_2$ páratlan többszöröse $a_1$-nek és minden más esetben $a_1+a_2$ [1]. A nyerő pozíciók periódushosszai csak a kételemű $A$ halmazok esetén ismertek teljes egészében.

Háromelemű halmazok esetében, pl. ha $a_1=s$, $a_2=2s+1$ és $a_3=3s+1$, akkor a periódushossz $4s^2+3s$ [1]. Nem ismert négyzetesnél hosszabb periódushossz, és a legtöbb esetben a periódushossz vagy $a_1+a_2$ vagy $a_1+a_3$ vagy $a_2+a_3$, vagy ennek a három számnak az osztója [2]. Itt a következő érdekes jelenséget figyelhetjük meg. Ha egy fix nagy $a_3$ értékre ábrázoljuk minden lehetséges $A=\{a_1,a_2,a_3\}$-ra, hogy az $f_A$ függvény periódushossza a fenti három összeg közül melyiknek az osztója (esetleg több összegnek vagy egyikének sem), akkor az 1. ábrán látható fraktálstruktúrát kapjuk. Ennek a fraktálnak a struktúrája lényegében nem függ $a_3$-tól. Az 1. ábrán $a_3=293$-ra és $a_3=300$-re mutatjuk, hogy melyek azon ${(a}_1,a_2)$ párok, amelyekre az $f_A$ függvény periódusa $a_1+a_2$ osztója vagy $a_1+a_3$ osztója vagy $a_2+a_3$ osztója. Míg 293 prím, 300 összetett szám. Ennek ellenére a két esetben kapott ábra nagyon hasonlít egymásra. Egyelőre nem ismert ennek a jelenségnek a magyarázata.

1. ábra. Az $f_A(n)$ függvény periodikussága, amikor $A=\{a_1,a_2,a_3\}$. A bal oldali ábrán $a_3=293$, a jobb oldali ábrán $a_3=300$. A színkódok: piros: $f_A(n)$ periódusa osztója $a_1+a_2$-nek, zöld: $f_A(n)$ periódusa osztója $a_1+a_3$-nak, kék: $f_A(n)$ periódusa osztója $a_2+a_3$-nak, fekete: a periódus valami más, más szín: a periódus osztója az $a_1+a_2$, $a_1+a_3$ és $a_2+a_3$ számok közül többnek is. Az ábrákon az $a_1=1$, $a_2=1$ eset a bal fölső sarokban van, $a_1$ értékei az $x$ tengelyen nőnek, $a_2$ értékei az $y$ tengelyen nőnek.

Még érdekesebb jelenségeket figyelhetünk meg, ha a játékot úgy játsszuk, hogy nem 1, hanem 2 kupac kavicsunk van, és az $A$ halmaz véges, kétdimenziós nemnegatív egész vektorokat tartalmaz (legalább az egyik vektor koordináta pozitív). A két játékos ismét felváltva játszik, és minden lépésben az $A$ halmazból választanak egy vektort, amely megmondja, hogy melyik kupacból hány kavicsot kell elvenni. Amennyiben a maradék kavicsok száma annyi, hogy egyetlen $A$-beli vektor sem választható (mert legalább az egyik kupacban levő kavicsok száma kevesebb, mint a vektor megfelelő koordinátája), az aktuális játékos elveszíti a játékot, és a másik nyert. Ekkor definiálhatjuk az $f_A(n_1,n_2)$ függvényt a következőképpen. $f_A(n_1,n_2)=1$, ha $n_1$ és $n_2$ kaviccsal kezdve a kezdő játékosnak van nyerő stratégiája, és $f_A(n_1,n_2)=0$, ha a második játékosnak van nyerő stratégiája. Fennáll a

$\displaystyle f_A(n_1,n_2)=1-\min\limits_{(x_1,x_2)\in A} \{f_A(n_1-x_1,n_2-x_2)\} $

egyenlőség, amelynek segítségével könnyen ki tudjuk számolni az $f_A(n_1,n_2)$ értékeket.

Míg egydimenziós esetben skatulyaelvvel könnyen lehetett bizonyítani a periodikusságot, addig két dimenzióban nem ismert ilyen bizonyítás, sőt, úgy néz ki, hogy bizonyos esetekben az $f_A$$(n_1,n_2)$ függvény kaotikus viselkedést mutathat. Kaotikus viselkedést gyakran figyelhetünk meg olyan $A$ halmazoknál, amelyek tartalmaznak egy olyan $x_{\max}$ vektort, amelyre minden $x\in A$, $x\neq x_{\max}$-ra $x_{\max}-x\in A$ [3]. Ezek közül most az $A=\{(3,0),(0,3),(2,5),(5,2),(5,5)\}$ esetet mutatjuk be. Ekkor az átló körüli, azaz $n_1\approx n_2$ tartományban teljes káoszt mutat az $f_A(n_1,n_2)$ függvény (ld. 2. ábra), míg az átló alatt függőleges, az átló fölött vízszintes irányban periodikusságat mutat $f_A(n_1,n_2)$, de a másik irányban kaotikus viselkedést mutat (ld. 3. ábra). Ide kattintva erre a játékra $f_A(n_1,n_2)$ első 16000-szer 16000 értékeit mutatjuk be. További két $A$ halmazra ugyanennyi értéket mutatunk be, itt az $A=\{(1,9),(8,3),(9,1),(2,7),(10,10)\}$, itt pedig az $A=\{(2,9),(8,3),(8,1),(2,7),(10,10)\}$ halmazhoz tartozó $f_A(n_1,n_2)$ függvény értékeit. A $(0,0)$ a bal felső sarokban van. A fekete szín jelöli az $f_A(n_1,n_2)=1$ értéket, a fehér szín pedig a $f_A(n_1,n_2)=0$ értéket.

2. ábra. Az $f_A(n_1,n_2)$ függvény egy részlete $n_1\approx n_2\approx 10000$ környékén, $A=\{(3,0),(0,3),(2,5),(5,2),(5,5)\}$. A fekete szín jelenti az $f_A(n_1,n_2)=1$ értékeket, míg a fehér az $f_A(n_1,n_2)=0$ értékeket.

3. ábra. Az $f_A(n_1,n_2)$ függvény egy részlete $n_1\ll n_2\approx 10000$ környékén, $A=\{(3,0),(0,3),(2,5),(5,2),(5,5)\}$. A fekete szín jelenti az $f_A(n_1,n_2)=1$ értékeket, míg a fehér az $f_A(n_1,n_2)=0$ értékeket.

 

Miklós István
HUN-REN Rényi Intézet

 

Hivatkozások

[1] I. Althöfer, and J. Bültermann. Superlinear period lengths in some subtraction games. Theoretical Computer Science, 148 (1995) No 1, 111–119, 1995.

[2] U. Larsson, I. Saha, A brief conversation about subtraction games, https://arxiv. org/abs/2405.20054. (2024)

[3] U. Larsson, I. Saha, M. Yokoo, Subtraction games in more than one dimension, https://arxiv.org/abs/2307.12458. (2024)

[4] I. Miklós, L. Post, Superpolynomial period lengths of the winning positions in the subtraction game. International Journal of Game Theory, 53(2024), 1275-1313.