Algojáték 1. gyakorlat megoldókulcs

A bal oldali játékban a tanult algoritmus szerint keresünk egy topologikus sorrendet a játék gráfjában (ebben a tárgyban megelégszünk a ránézéses módszerrel) például: $$v_0, a,e,b,f,c,d,g.$$ Eszerint visszafele haladva címkézzük a csúcsokat.

• A nyelők esetében a szabály a következő:
  • Az $N_W$-beliek $\II$-es típusúak, hiszen a belépő játékos nyerni fog, viszont a ''kilépő'' játékost hívjuk $\I$-esnek.
  • Az $N_L$-beliek pedig pont fordítva, tehát $\I$-es típusúak.
• A többi csúcs esetében a szabály a következő:
• Ha lát $\II$-es csúcsot, akkor nyerő stratégia oda lépni, tehát $\I$-es a típusa.
• Ha nem lát $\II$-es csúcsot, akkor nincs nyerő stratégiája a most következő játékosnak, tehát $\II$-es a típusa.

A jobb oldali játékban a megoldás hasonló. Egy jó topologikus sorrend például a $$v_0, a,d,g, b,e,h, c,f,i.$$ A döntetlenes eseteket a következőképpen kezeljük:

• Az $N_T$-beli nyelők értelemszerűen $*$ típusúak.
• Nem nyelők esetében a szabály a következő:
• Ha van $\II$-es szomszéd, akkor nyerő stratégia oda lépni, tehát $\I$-es a csúcs típusa.
• Ha nincs $\II$-es szomszéd, akkor nincs nyerő stratégia, de ha van $*$-os, akkor nemvesztő stratégia oda lépni, tehát $*$-os a csúcs típusa.
• Ha csak $\I$-es szomszéd van, akkor muszáj egy ilyenbe lépni, ilyenkor ha az ellenfél ügyesen játszik, veszteni fogunk, tehát a mi csúcsunk $\II$-es típusú.

Szemfüles hallgatók megfigyelhetik, hogy míg az éles játékok esetében a $\II$-es típusú csúcsok alkotják a magot, a döntetlen nyelők jelenléte elrontja ezt a tulajdonságot. Ha valaki szeretne olyan címkézési szabályt, ahol a mag a címkék alapján ránézésre látszik, érdemes a $*$ típusú címkét két altípusra bontani aszerint, hogy melyik játékos fog a döntetlen nyelőbe ténylegesen belépni. Izgalmas feladat annak a bizonyítása, hogy ilyen címkézés mellett kik alkotják a magot.

A választott topologikus sorrend szerint visszafelé haladva határozzuk meg a csúcsok Grundy-számozását. Minden csúcs az általa látott értékek $mex$-ét kapja, vagyis a legkisebb olyan nemnegatív egész számot, amit ő nem lát. Nyelők esetében ez az érték $0$.

A bal oldali gráfra ez: $$\begin{array}{c|c|c|c|c|c|c|c} v_0 & a & e & b & f & c & d & g \\ \hline 2 & 1 & 1 & 2 & 2 & 0 & 1 & 0 \end{array}$$

A jobb oldalira pedig: $$ \begin{array}{c|c|c|c|c|c|c|c} v_0 & a & e & b & f & c & d & g \\ \hline 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \end{array} $$

Felrajzoljuk az összegjáték gráfját: ennek a csúcshalmaza $V(G_1) \times V(G_2)$, és egy $(u_1, u_2)$ csúcsból pontosan akkor vezet irányított él egy $(v_1, v_2)$ csúcsba, ha vagy $u_1 v_1 \in E(G_1)$ és $u_2 = v_2$ vagy $u_2 v_2 \in E(G_2)$ és $u_1 = v_1$.

A felrajzolást áttekinthetőbbé tehetjük, ha táblázatot készítünk: az egyik gráf csúcsait az első sorba, a másikét az első oszlopba írjuk. Így minden cella az adott sor- és oszlopcsúcs párjához tartozik.

Célszerű a két kiinduló gráfot topologikus sorrendben elhelyezni, mert ekkor az összegjáték gráfjának topologikus sorrendje egyszerűen megkapható például a táblázat sorfolytonos, azaz fentről lefelé, azon belül balról jobbra történő kiolvasásával. Egy ilyen ábrázolást látunk lent. Ezután az órán tanult algoritmussal meghatározzuk a gráf Grundy-számozását (az ábrán ezt piros számokkal tüntettük fel).

Megjegyzés: Következő előadáson fog elhangzani a Sprague-Grundy tétel. Ez alapján az összegjáték gráfjának Grundy-számozása a kis gráfok Grundy-számainak nim-összegéből kapható. Figyeljük meg, hogy ez itt is teljesül, ehhez a kis gráfok Grundy-számait is feltüntettük.

1. megoldás. Ha már megvan az összegjáték Grundy-számozása, akkor az összegjáték pontosan akkor lesz $\II$-es típusú, ha a kezdőállás Grundy-száma 0, azaz az $(a,z)$, $(b,y)$, $(c,y)$, $(d,z)$ kezdőállások esetén.

2. megoldás. Elég külön-külön a két játék Grundy-számozását ismerni, ugyanis az összegjáték pontosan akkor lesz $\II$-es típusú, ha a kezdőállás Grundy-száma 0, ami pontosan az azonos Grundy-számú állásokból képzett párok esetén fordul elő, vagyis az $(a,z)$, $(b,y)$, $(c,y)$, $(d,z)$ kezdőállások esetén.

Belátjuk, hogy a magban épp azok a kupacpárok lesznek, amelyekben legalább az egyik kupac páros méretű. Ekkor a soron következő játékos tud úgy lépni, hogy egy páros kupacot két páratlanra oszt fel, a másik kupacot pedig eldobja. Két páratlan kupacból pedig csak úgy tud lépni a soron következő, hogy egy páros kupac is fog keletkezni. Mivel az $(1,1)$ állásba lépő játékos nyer, ezért a kezdőjátékosnak valóban pontosan akkor van nyerő stratégiája, ha $n$ és $m$ közül legalább az egyik páros.

Némi számolgatás útján megsejtjük, hogy a magban a $0$, az $1$, és a $4$-nél nagyobb, 3-mal osztható számok vannak. Ezt kézzel igazoljuk $n=10$-ig:

• $n \in \{0,1\}$ valóban a magban van ($\II$-es típusú), hiszen ekkor nem tudunk kavicsot elvenni.
• $n \in \{2,3\}$, illetve $n \in \{4,5\}$ nincs a magban ($\I$-es típusú), hiszen belőlük $2$, illetve $4$ kavics elvételével nyerni tudunk.
• $n=6$ a magban van ($\II$-es típusú), hiszen csak $2$ vagy $4$ kavicsot lehet belőle elvenni és mindkét esetben $\I$-es típusúba lépnénk.
• $n \in \{7,8\}$ nincs a magban ($\I$-es típusú), hiszen $7$ kavics elvételével nyerni tudunk belőle.
• $n=9$ a magban van ($\II$-es típusú), hiszen belőle az $n' \in \{7,5,2\}$ látszik, ezek egyike sincs a magban.
• $n=10$ nincs a magban ($\I$-es típusú), hiszen belőle $4$ kavics elvételével az $n'=6$-ba lépünk, ami $\II$-es típusú.

$11 \leq n$ már elég nagy, hiszen belőle az $n'=4$-ig látunk vissza, ahol már szabályosan viselkedik a sorozat. Elég nagy $n$-re pedig indukcióval a következőképpen lehet érvelni. Tegyük fel, hogy $n$-nél kisebb (és $4$, vagy annál nagyobb) kupacméretekre már igaz az állítás.

• Ha $n=3k$ alakú, akkor az $S=\{2,4,7\}$ lépések mindegyike $3$-mal nem osztható kisebb számot csinál belőle, amikről tudjuk, hogy $\I$-es típusúak, tehát $n=3k$ valóban $\II$-es típusú lesz.
• Ha $n=3k+1$ alakú, akkor $7$ kavics elvételével $3$-mal osztható méretű kisebb kupacra tudunk lépni, amiről már tudjuk, hogy $\II$-es típusú, ezért $n=3k+1$ $\I$-es típusú.
• Ha $n=3k+2$ alakú, akkor $2$ kavics elvételével $3$-mal osztható méretű kisebb kupacra tudunk lépni, amiről már tudjuk, hogy $\II$-es típusú, ezért $n=3k+1$ $\I$-es típusú.

Tetszőleges $S$ esetén egy $k$-méretű kupac típusára tekinthetünk úgy, mint az őt közvetlenül megelőző $\max S$ darab csúcs típusának a függvényére. Nevezzük ezt a $\max S$ hosszúságú típussorozatot a csúcs mintájának. A ($\max S$)-hosszú intervallumok véges sok (konkrétan $2^{\max S}$) félék lehetnek, és amint találunk két azonos, ($\max S$)-hosszú intervallumot a sorozatban, akkor onnantól kezdve a rákövetkező csúcsok típusa is azonos kell hogy legyen és így tovább.

Az első lépésben válassza ki a kezdőjátékos a 2. sor 2. kiskockáját (azaz a mérgezett kockától átlósan jobbra felfelé lévő kockát). Utána akár a függőleges oszlopból, akár a vízszintes sorból harap a második játékos, a kezdőjátékos tegye ugyanezt a másik sávban, és így nyerni fog.

A nyerő stratégia követése során a győztesnek sosincs választása, ugyanis ha bárhol eltérünk a nyerő stratégiától, akkor az ellenfél tud nyerni. Ezért a győztes játékos nyerő stratégiája a módosított játékra megegyezik az eredetivel. A vesztes játékos ezzel szemben tud úgy lépni, hogy a győztesnek minden lépésben pontosan 1 kavicsot kelljen elvennie (konkrétan a vesztes mindig 10 kavicsot vesz el).

A $G_1$ gráf DAG, tehát van benne mag. A topologikus sorrend szerint visszafelé haladva mohón építünk egy független ponthalmazt, ez lesz a(z egyértelmű) mag: $d, f$.

A $G_2$ gráfban nyilván nincs mag, hiszen a függetlenség miatt ez csak egy csúcsból állhatna (ugyanis az üreshalmaz semmilyen legalább egycsúcsú gráfban nem mag), aminek akkor egy olyan csúcsnak kellene lennie, amibe minden más csúcsból fut él, de ilyen csúcs nincsen.

A $G_3$ gráfban az $a,d$ csúcsok egy magot alkotnak.

A $G_4$ gráfban nincs mag. Indirekt tegyük fel, hogy van. Akkor abban a $d$ csúcs nem lehet benne, ellenkező esetben a függetlenség miatt nem lehetne a magban az $a, b, f$ csúcsok egyike sem, és így $a$ nem látná a magot. Ekkor ahhoz, hogy a $d$ csúcs láthassa a magot, az $a$ csúcsnak muszáj a magban lennie. A függetlenség miatt ekkor a $b$ és az $f$ csúcs sem lehet a magban. Ahhoz, hogy az $f$ csúcs láthassa a magot, az $e$ csúcsnak a magban kell lennie. De ekkor a függetlenség miatt nem lehetne a magban az $b, c, h$ csúcsok egyike sem, és így $c$ nem látná a magot.

Indirekt tegyük fel, hogy mégis van neki. Mivel minden mag egy független ponthalmazt alkot, ezért lesz olyan csúcs hogy sem ő, sem pedig az ő egyetlen ki-szomszédja nem szerepel ebben a független ponthalmaznak, ami ellentmond a mag definíciójának.

Egy tetszőleges tovább már nem bővíthető független halmazrendszer mag, és ilyet mohó kiválasztással tudunk találni.

A címkézés topologikus sorrendben visszafele történik. A nyelőknek a megadott érték lesz a címkéje. A többiek pedig az általuk látott csúcsok maximumának $-1$-szeresét írják a címkére, hiszen az onnan kilépő játékos a maximális szomszédba akar majd lépni, ha optimálisan játszik, a mi kifizetésünk pedig az ellenfél kifizetésének a $-1$-szerese lesz.