Algojáték 2. gyakorlat megoldókulcs

Javaslat

A megoldásokat ne nézd meg rögtön, előbb szánj egy kis időt az önálló gondolkodásra és az ötletelésre! A problémamegoldás képessége olyan mint egy izom: mindenkiben fejleszthető. Ezek a feladatok pontosan ebben segítenek. Ha teljesen elakadnál, ott a hint.

1. feladat

Osztójáték: Adott egy $n \in \mathbb{N}_+$ szám. A soron következő játékos kiválasztja $n$ egy osztóját oly módon, hogy a választott szám egyik osztója sem szerepelt korábban. Az veszít, aki az 1-et mondja. Bizonyítsuk be, hogy $n>1$ esetében a kezdőjátékosnak van nyerő stratégiája.

Hint

Stratégialopás.

Megoldás

A játék nyilván nem végződhet döntetlennel. Indirekt tegyük fel, hogy a második játékosnak van nyerő stratégiája. Ekkor a második játékos úgy is tud nyerni, ha a kezdőjátékos először az $n$-et mondaná. De akkor a kezdőjátékos tehet úgy, mintha a másik kezdte volna a játékot az $n$ szám kiválasztásával, és a második játékos nyerő stratégiáját követve innen folytatja a játékot. Ekkor a kezdőjátékos nyerne, ami ellentmondás.

2. feladat

Mutassunk meg, hogy minden $(a \times b)$-s mérgezett csoki játékhoz létezik olyan $n$, amelyre az $n$-es Osztójáték izomorf vele.

Hint

$n$ prímtényezős felbontása számít.

Megoldás

Ha $a$ és $b$ is legalább $2$: Legyen $n = p^{\,a-1} q^{\,b-1}$, ahol $p$ és $q$ különböző prímszámok. Ekkor $n$ osztói éppen a $p^i q^j$ alakú számok, ahol $0 \leq i < a$ és $0 \leq j < b$. Ezeket megfeleltethetjük egy $(a \times b)$-s mérgezett csoki kockáinak: a $p^i q^j$ osztót az $(i,j)$ indexű kockához rendeljük. A mérgezett kocka ekkor a $(0,0)$ indexű.

Ha kimondjuk a $p^i q^j$ osztót, az pontosan az $(i,j)$ csokikocka kiválasztásának felel meg, hiszen ezzel egyúttal kizárjuk az összes olyan osztót, amelyben mindkét kitevő legalább ekkora, ez pedig éppen annak a téglalapnak felel meg a csokitáblán, aminek a bal alsó sarka az $(i,j)$, a jobb felső sarka pedig az $(a-1, b-1)$.

Speciális esetben: ha $a=1$ és $b=1$, akkor legyen $n=1$. Ha $a=1$ és $1 \lt b$ (vagy fordítva), akkor legyen $n=p^{b-1}$, ahol $p$ egy prím.

3. feladat

Bizonyítsuk be, hogy a $J_1$ és $J_2$ éles kombinatorikus játékok pontosan akkor ekvivalensek, ha tetszőleges $H$ éles kombinatorikus játék esetén $J_1 + H$ és $J_2 + H$ azonos típusúak.

Hint

Többféleképpen is igazolható. Egy lehetséges bizonyításhoz a következő állítások használata elegendő:

$J_1$ és a $J_2$ pontosan akkor ekvivalensek, ha $J_1 + J_2$ egy $\II$-es típusú játék.
$\I + \II = \I$, azaz egy $\I$-es és egy $\II$-es típusú játék összege $\I$-es típusú.
$\II + \II = \II$, azaz két, akár különböző, de $\II$-es típusú játék összege $\II$-es típusú.
$J + J = \II$, ugyanabból a játékból két példányt véve, az összegük $\II$-es típusú lesz.

A két irány amit be kell látni:

Ha $J_1$ és $J_2$ ekvivalensek, akkor bármely $H$-ra $J_1 + H$ és $J_2 + H$ azonos típusúak.
Ha tetszőleges $H$ választásra $J_1 + H$ és $J_2 + H$ azonos típusúak, akkor $J_1$ és $J_2$ ekvivalensek.

Megoldás

Ha $J_1$ és $J_2$ ekvivalensek, akkor bármely $H$-ra $J_1 + H$ és $J_2 + H$ azonos típusúak:

Nézzük meg tetszőleges $H$ játékra, hogy mi a helyzet a $(J_1 + H) + (J_2 + H)$ összegjátékban!
A játékok összege értelemszerűen kommutatív és asszociatív, azaz ez $(J_1+J_2)+(H+H)$ alakra hozható.
Ebből $H+H$ típusáról tudjuk, hogy $\II$-es, hiszen két példány ugyanabból a játékból.
A feltételből pedig $J_1$ és $J_2$ ekvivalensek, vagyis $J_1 + J_2$ egy $\II$-es típusú játék.
$\II + \II = \II$, tehát a $(J_1+J_2)+(H+H) = (J_1 + H) + (J_2 + H)$ játék típusa $\II$-es.
Indirekt tegyük fel, hogy $J_1+H$ és $J_2+H$ típusa nem azonos.
Tehát $J_1+H$ és $J_2+H$ közül az egyik $\I$-es, a másik pedig $\II$-es típusú.
Ekkor viszont $\I + \II = \I$ miatt $(J_1 + H) + (J_2 + H)$ típusának $\I$-nek kell lennie, ami ellentmondás.

Ha tetszőleges $H$ választásra $J_1 + H$ és $J_2 + H$ azonos típusúak, akkor $J_1$ és $J_2$ ekvivalensek:

Ha tudjuk, hogy ez tetszőleges $H$ választásra teljesül, akkor válasszuk például a $H=J_2$-t.
Ekkor $J_1+J_2$ típusa azonos $J_2+J_2$ típusával.
$J_2+J_2$ $\II$-es típusú, hiszen ugyanazon játék két példányáról van szó.

Megjegyzés: a második irány bizonyításánál sokszor merül fel kérdésként, hogy miért szabad nekem egy konkrét $H$-t kiválasztani. Azért, mert itt most a feltétel azt állítja, hogy minden $H$-ra teljesül valami, nekünk ennél egy sokkal gyengébb feltétel is elég az indokláshoz, ami egy konkrét $H$-t használ csak.

4. feladat

Tegyük fel, hogy van három éles kombinatorikus játékunk: $J_1, J_2, J_3$. Tudjuk, hogy $J_1+J_2$ és $J_2+J_3$ egyaránt $\II$-es típusú. Adott két program, amelyek rendre a $J_1+J_2$, illetve a $J_2+J_3$ játékban valósítják meg a második játékos nyerő stratégiáját interaktív módon: a bemenetükön várják az első játékos következő lépését, ha ezt megkapják, akkor rövid időn belül kiírják a második játékos válaszát. Ezen programok felhasználásával készíts egy hasonló interaktív programot, ami a $J_1+J_3$ játékban tud második játékosként nyerni.

(Ez idén nem volt pöttyös feladat, de túl nehéznek bizonyult, ezért jövőre az lesz.)

5. feladat

Mutassuk meg, hogy az éles kombinatorikus játékok ekvivalenciája valóban egy ekvivalenciareláció, azaz reflexív, szimmetrikus és tranzitív.

Hint

Mit jelentenek az egyes tulajdonságok:

Reflexivitás = játék saját magával ekvivalens.
Szimmetria = ha $J_1$ ekvivalens $J_2$-vel, akkor $J_2$ is ekvivalens $J_1$-el.
Tranzitivitás = ha $J_1$ ekvivalens $J_2$-vel és $J_2$ ekvivalens $J_3$-mal, akkor $J_1$ is ekvivalens $J_3$-al.

Emlékezzünk az ekvivalencia alternatív definícióira.

Megoldás

Előadáson tanultuk, hogy $J_1$ és $J_2$ játék ekvivalensek pontosan akkor, ha a kezdőcsúcsaik Grundy-számai egyenlőek, az egyenlőség pedig ekvivalenciareláció.

6. feladat

(a) Mutassuk meg, hogy tetszőleges $k \in \mathbb{N}_+$ esetén ha $k$-nimben hozzáveszünk a meglévő kupacokhoz két további, egyforma méretű kupacot, akkor a játék lényegében nem változik, azaz ugyanannak a játékosnak lesz nyerő stratégiája, mint korábban.

(b) Adott $n \in \mathbb{N}_+$ pénzérme egymás mellett egy sorban, mindegyik vagy fejjel, vagy írással felfelé. A soron következő játékos átfordít egy tetszőleges fejet írásra, valamint egy ettől jobbra lévő tetszőleges érmét átfordíthat az ellenkezőjére (ha akar). Az veszít, aki nem tud lépni (vagyis amikor mindegyik érme írással van felfelé). Kinek van nyerő stratégiája?

Hint

Az (a) feladat a Sprague-Grundy tételből következik és a (b) feladat megoldásában szeretne segíteni. A (b) feladatban azt kell észrevenni, hogy a játék egy megfelelő $k$-nimmel ekvivalens.

Megoldás

Az (a) feladatrészben a játék Grundy-száma nem változik meg két azonos méretű kupac hozzávételével.

Megmutatjuk, hogy a pénzforgató játék ekvivalens egy $k$-nim játékkal, ahol $k$ a fejek száma.
Tetszőleges $i \in \{ 1, \ldots, n \}$ esetén, ha a sor végétől számítva az $i$-edik pénzérme fej, akkor ahhoz vegyünk fel egy $i$-méretű kupacot.
Amikor a pénzforgató játékban a fej átfordítására az $i$-edik érmét választjuk ki, akkor az azt fogja jelenteni, hogy az $i$-méretű kupacból elveszünk valamennyi kavicsot.

Ha a pénzforgató játékban nem fordítunk át egy második érmét, akkor az azt fogja jelenteni, hogy az összes kavicsot elvettük az $i$-méretű kupacból.
Ha a $j$-edik érmét fordítjuk át az ellenkezőjére, akkor az azt fogja jelenteni, hogy $i-j$ darab kavicsot vettünk el az $i$-méretű kupacból:

Ha a $j$-edik érme írás volt, akkor most lett ezzel egy $j$-méretű kupacunk.
Ha viszont fej volt, akkor keletkezett volna egy második $j$-méretű kupacunk is, de az (a) feladatrész értelmében ez ekvivalens azzal a játékkal ahol egyetlen $j$-méretű kupacunk sincs. Ez pedig éppen annak felel meg, hogy a $j$. fejet is írásra fordítottuk.

7. feladat

Adott $n \in \mathbb{N}_+$ pénzérme egymás mellett egy sorban, mindegyik vagy fejjel, vagy írással felfelé. A soron következő játékos választ egy fejet, és azt, illetve az összes tőle jobbra lévő érmét átfordítja az ellenkezőjére. Az veszít, aki nem tud lépni (vagyis amikor mindegyik érme írással van felfelé). Kinek van nyerő stratégiája?

Hint

Játsszunk végig egy ilyen játékot. Nézzük meg, hogy viselkedik a sorban utolsó érme a játék során.

Megoldás

Mivel minden lépésben megváltozik, hogy az utolsó érme melyik oldalával van felfelé, ezért a kezdőjátékosnak pontosan akkor van nyerő stratégiája (sőt, bármit csinál, győzni fog), ha kezdetben az utolsó érme fej.

8. feladat

Két játékos, $A$ és $B$ játszik $n \times n$-es táblán hexet, ahol $n$ tetszőleges pozitív egész szám. $A$ a kezdő játékos, $B$ pedig a második. $B$-nek kizárólag a legelső körében lehetősége van a hagyományos hex lépés tevése helyett úgy dönteni, hogy átveszi a kezdőjátékos szerepét. Ekkor egyrészt kicserélik $A$ és $B$ között, hogy kinek melyik szemközti oldalpárt kell összekötnie, másrészt $B$ megkapja $A$ kezdőlépését is, átszínezve azt a $B$ színére. Ezután pedig $A$ lép, immáron második játékosként. Melyik játékosnak van nyerő stratégiája ebben a módosított hex játékban?

Hint

$B$-nek lesz nyerő stratégiája.

Megoldás

Hasonlóan az eredeti hex játékhoz, döntetlen ebben a játékban sem lehet. Tehát két eset van:

Ha $A$ jót lépett, azaz egy $\II$-es típusú csúcsba lépett, akkor $B$ átveszi a szerepét és innen nyerni tud.
Ha $A$ nem jót lépett, azaz egy $\I$-es típusú csúcsba lépett, akkor onnan $B$-nek van nyerő stratégiája, e szerint lép.

Tehát $B$-nek van nyerő stratégiája.

9. feladat

(a) Mutassuk meg, hogy egy hexhez hasonló, de ($n \times n$)-es négyzetrácson játszott játékban $n \ge 2$ esetében mindkét játékosnak van nemvesztő stratégiája.

(b) Adjuk meg a második játékos egy lehetséges nemvesztő stratégiáját.

(Pöttyös feladat.)

10. feladat

Tekintsük a "fordított hex" játékot, ahol az a játékos veszít, aki megépít egy olyan utat, amivel a hexben nyert volna.

Mutassuk meg, hogy ha $n$ páros, akkor a kezdőjátékosnak van nyerő stratégiája.
Mutassuk meg, hogy ha $n$ páratlan, akkor a második játékosnak van nyerő stratégiája.

(Pöttyös feladat.)

11. feladat

Pontosan mely $n \in \mathbb{N}_+$ számok esetén lesz az Osztójáték izomorf egy mérgezett csoki játékkal?

(Pöttyös feladat.)