Csirmaz László:

Játékok és Grundy-számaik

(A cikk eredeti változata a KöMaL 1980. decemberi számában jelent meg.)

Olyan játékokat vizsgálunk, melyekben két személy játszik egymás ellen. Ezeket kétszemélyes, nulla összegű játékoknak nevezik; bennük az egyik fél győzelme a másik vereségét jelenti. A játék során a lépések nem függnek semmiféle véletlen eseménytől, a játékosok szabadon dönthetik el, hogy a megengedett lépések közül melyiket választják. Így vizsgálódásunk köréből kizártuk a szerencsejátékokat. Feltesszük azt is, hogy a játékosok felváltva lépnek, és a játék addigi menetéről mindent tudnak - matematikai szakkifejezést használva a játék teljes információjú. Kimaradnak tehát az alkalmazások szempontjából fontos mátrix-játékok, köztük a jól ismert kő-olló-papír játék is. Ezekről bővebben [1]-ben és [2]-ben olvashatunk. A legtöbb táblás játék [3], köztük a sakk is, eleget tesz megszorításainknak.

A vizsgált játékok matematikai elmélete meglehetősen egyszerű. A gyakorlatban azonban - ha megpróbáljuk ezt az elméletet közvelenül alkalmazni - még az egyszerű játlékok elemzése is végrehajthatatlanul sok számolást igényel. Így ezekben az analízisekben sok egyedi, egyetlen játékra alkalmazható - idegen kifejezéssel élve "ad hoc" - ötletet találunk. Gondoljunk például a sakkra, használhatók-e más játékok elemzésénél a sokféle megnyitást, végjátékot ismertető vaskos kötetek?

Célunk egy ilyen ad hoc módszernek, a Grundy-számozásnak a bemutatása. Ennek segítségével több olyan játék analízise végezhető el, amelyek egyébként nem, vagy csak igen nagy nehézség árán lennének elemezhetők.

E cikk hét részből áll. Az elsőben pontosan leírjuk a vizsgált játékok struktúráját. A második rész példái a bevezetett fogalmakat illusztrálják. A 3. részben definiáljuk a játékok Grundy-számait, az ezt követő részben pedig azt mutatjuk be, hogyan használhatók a Grundy-számok annak eldöntésére, hogy a játékban melyik játékos tud nyerni, és ehhez hogyan kell játszania. Végül az utolsó részben egy mindmáig megoldatlan problémát említünk meg.

Természetesen nem volt és nem is állt szándékunkban a játékelméletnek - még az általunk választott szűk területén sem - teljes ismertetése. Sok fontos eredményt csak megemlítünk, sokról pedig szó sem esik. A tételek más módon is kimondhatók lennének. A tételek bizonyítása is több helyütt hiányos vagy egészen hiányzik, ám ezeket a hiányokat az érdeklődő Olvasó könnyűszerrel pótolhatja. A cikkben szereplő játékok is a Grundy-számozás alkalmazásait kívánják bemutatni. Így eleve kihagytuk azokat, amelyekre a módszer nem alkalmazható. Kimaradtak azok a játékok is, melyek elemzésénél a Grundy-számozás csak minimális segítséget nyújt, vagy nem kapcsolódik közvetlenül a játék struktúrájához. A megmaradt játékok közül igyekeztünk kiválasztani az érdekesebbeket, és ezek közül is azokat, melyek nem túlságosan bonyolultak.

A cikk megírásához felhasznált legfontosabb forrásmuka J. H. Conway könyve volt. [4]

1. Milyen játékokról lesz szó?

Játékaink kétszemélyesek. Úgy képzeljük, hogy valamilyen táblán valamiféle szabály szerint két játékos, akiket Kezdőnek, illetve Másodiknak nevezünk, felváltva lép. A játék folyamán a táblán különféle pozíciók (helyzetek) alakulnak ki, melyek lépésről lépésre változnak, és a játék állását ezek egyértelműen meghatározák. Játékaink tehát bizonyos pozíciókból állnak, és létezik valamiféle szabály, amely minden pozícióhoz megmondja, hogy a soron következő lépéssel milyen más pozíciók érhetők el, a játékosok mely pozíciókba tudnak lépni. A játékot a Kezdő játékos kezdi, úgy, hogy az egyértelműen meghatározott kezdő pozíció valamelyik (lehetséges) rákövetkezőjét kiválasztja, azaz abba lép. Ezután a Második játékoson a sor: ő választ egyet a Kezdő által választott pozíció rákövetkezői közül, majd ismét a Kezdő következik, és így tovább. A vesztes az, akinek lépnie kell, de nem tud; más szavakkal: az nyer, aki az utolsót lépi.

Minden játéknak egyetlen kezdő pozíciója van. De tekinthetjük a játék tetszőleges pozícióját is egy rövidebb játék kezdő pozíciójának.

A vizsgált játékok struktúráját ezek szerint a következőképpen írhatjuk le. Minden egyes pozíciónak megfeleltetünk egy pontot (például a síkban), és ha az X pozícióból az Y pozícióba lehet (közvetlenül) lépni, vagy más szavakkal: ha Y az X rákövetkezője, akkor az X-nek megfeleltetett pontból egy nyilat irányítunk az Y-nak megfeleltetett pontba. Az így kapott struktúrát irányított gráfnak nevezzük, a pozícióknak megfeleltetett pontokat csúcsoknak vagy csúcspontoknak, a nyilakat pedig éleknek.

Csak olyan játékokkal foglalkozunk, amelyekben véges sok lehetséges pozíció van. Ezek között fontos szerepet játszanak az ún. véges játékok. Egy játék véges, ha akármelyik pozícióból indulnak és akárhogyan is játszanak a játékosok, a játék előbb-utóbb véget ér. Ez azt jelenti, hogy nem találhatók olyan X₁, X₂, ..., X_k pozíciók, hogy X₁-ből X₂-be, X₂-ből X₃-ba, ..., X_k-1-ből X_k-ba, és X_k-ból X₁-be lehetne lépni. Speciálisan nem lehet olyan pozíció sem, amely saját magának (egyik) rákövetkezője. A játékoknak megfeleltett irányított gráfok nyelvén ez a kikötés azt jelenti, hogy a gráf nem tartalmazhatja az 1. ábrán látható gráfok, az úgynevezett irányított körök egyikét sem. Az ilyen gráfot körmentes gráfnak szokás nevezni.

1. ábra

2. Néhány egyszerű játék

HALOM. Van egy halom valamilyen tárgyunk (babszem, gyufa, érme stb.) A soron következő játékos annyi elemet vesz el a halomból, amennyit akar (akár az összeset is), de legalább egy elemet el kell vennie.

Ez így önmagában egy érdektelen játék, de több összetett játéknak eleme, ezért érdemes vele foglalkoznunk. Kezdő akkor tudja megnyerni ezt a játékot - úgy mondjuk: akkor van nyerő stratégiája -, ha a halomban legalább 1 tárgy van. Ha egy tárgy sincs a halomban, akkor Második nyert, mert Kezdőnek lépnie kellene, de nem tud. Legyen a halomban kezdetben 5 tárgy. Ekkor a játéknak összesen 6 lehetséges pozíciója van, attól függően, hogy a halomban 5, 4, 3, 2, 1 vagy 0 elem van-e. A játékhoz tartozó irányított gráfot a 2. ábra mutatja.

2. ábra

RELATÍV PRÍM. Ismét van egy halom tárgyunk. De most n elemből akkor vehetünk el k elemet, ha n és k relatív prímek, vagyis az n és k számoknak nincs 1- nél nagyobb közös osztójuk.

Mindig legalább 1 elemet el kell venni (hiszen 0 semmihez sem relatív prím), pontosan 1 elemet pedig mindig el lehet venni (mert 1 minden számhoz relatív prím). Végül nem lehet egy lépéssel kiüríteni a halmot, kivéve ha csak 1 tárgy van benne, mert n > 1 esetén az n az n-hez nem relatív prím. Az 5 elemből álló játék grafikája a 3. ábrán látható.

Lássa be az Olvasó, hogy Kezdőnek akkor és csak akkor van nyerő stratégiája, ha kezdetben páratlan sok elem van a halomban!

3. ábra

LÉTRA. Van egy halom tárgyunk. A soron következő játékos a halomból legalább 1, de legfeljebb t tárgyat vehet el, ahol t előre rögzített természetes szám.

Ezt a játékot valószínűleg mindenki játszotta. Másodiknak pontosan akkor van nyerő stratégiája, ha a halom elemeinek száma osztható (t+1)-gyel. Csak arra kell ügyelnie, hogy minden lépése után is ez a helyzet álljon elő, különben Kezdő nyer.

A következő négy játékot (mondjuk 8x8-as) sakktáblán lehet játszani. Kezdetben a tábla jobb alsó sarkában (a h1 mezőn) áll egy bábu, és ezt a játékosok a megadott szabályok szerint felváltva mozgatják. A lépések olyanok, hogy a bábu minden lépésben közelebb kerül a bal felső sarokhoz, s a cél az, hogy oda eljusson. Most is az veszít, aki nem tud lépni.

KIRÁLY. A bábuval vagy egy mezővel balra, vagy egy mezővel fölfelé, vagy egy mezővel átlósan balra fölfelé lehet lépni (4. ábra). A nyertes az, aki a bábut a bal felső sarokba tolja, hiszen csak onnan nem lehet tovább lépni.

4. ábra

A játékot Kezdő nyeri. Először átlósan kell lépnie, majd a Második lépéseit utánozva Ő jut be a célba.

KIRÁLYNŐ. Léphetünk balra, fölfelé, vagy a bal felső csúcsba befutó átló tetszőleges mezőjére (5. ábra).

A játékot így természetesen Kezdő nyeri, hiszen első (és egyetlen) lépésével a bábut a bal felső sarokba tolja. Ha azonban a bábu a h4 mezőről indul, akkor Másodiknak van nyerő stratégiája.

5. ábra

BÁSTYA. A bábu az előző játékban leírt módon léphet, csak most az átlós irányú lépés nincs megengedve. A játékban Másodiknak van nyerő stratégiája.

Vegyük észre, hogy a BÁSTYA játék ekvivalens a következővel. Veszünk két, 7-7 elemű halmot. A soron következő játékos az egyik halmot kiválasztja, és abban a HALOM szabálya szerint lép egyet. Ha a bábu a BÁSTYÁ-ban a balról számított i-edik oszlopban és a felülről számított j-edik sorban van (1i,j8), ez megfelel annak az esetnek, mikor az egyik halomban i-1, a másikban j-1 elem van. A vízszintes lépések az első halom csökkentésének, a függőleges lépések a másik halom csökkentésének felelnek meg.

HUSZÁR. A bábu egy mezőről a 6. ábrán látható négy mező valamelyikére léphet, feltéve, hogy az még a táblán van. Ezt a játékot is Második tudja megnyerni.

6. ábra

Az eddigiek véges játékok voltak, most lássunk egy nem véges játékot.

DUGÓ (közlekedési). A 7. ábra egy állam térképét mutatja, a városok nevei Abádszalöktől Putnokig futnak. A városokat a térkép szerint egyirányú utak kötik össze. Egy autó indul Muraszemenyéről, a játékosok egy-egy lépésben valamelyik kivezető úton egy szomszédos városba mehetnek. Az győz, aki Cibakházára beviszi az autót, hiszen (csak) onnan nincs kivezető út.

7. ábra

A játék nem véges, mert a játékosok körben járhatnak Muraszemenye-Ipafa-Nagyatád útvonalon. Ennek ellenére Második meg tudja nyerni a játékot. (Hogyan?)

3. Grundy-számok

Az x₁, x₂, ..., x_k nemnegatív egész számok legkisebb kizártján azt a legkisebb nemnegatív egészet értjük, amely nem fordul elő az x₁, x₂, ..., x_k számok között. Ezt a számot a legkisebb közös többszörös mintájára lkkz(x₁, x₂, ..., x_k) jelöli.

Példák: lkkz(0)=1, lkkz(1)=0, lkkz(0,1,3)=lkkz(0,1)=lkkz(7,9,8,3,1,12,0)=2.

Tekintsünk most egy véges játékot. A játék pozícióihoz nemnegatív egész számokat, úgynevezett Grundy-számokat rendelünk a következő szabály szerint:

Azokhoz a pozíciókhoz, melyeknek nincs rákövetkezőjük (azaz amelyekből indulva, a soron következő játékos veszít), 0-t írunk. Ha egy X pozíciónak már minden rákövetkezőjéhez írtunk számot, akkor az X pozícióhoz ezek legkisebb kizártja kerüljön.

Egy játék Grundy-száma definíció szerint a játék kezdő pozíciójának Grundy-száma legyen.

Nézzük meg, hogy az előző játékok pozícióihoz milyen Grundy-számok tartoznak. Ezek után igazolni fogjuk, hogy minden véges játéknak van Grundy-száma.

HALOM. Egyetlen olyan pozíció van, melynek nincs rákövetkező állapota, azaz amellyel a kitöltést elkezdhetjük: amikor a halomban 0 elem van. Az ehhez a pozícióhoz tartozó Grundy-szám a fenti definíció szerint H₀=0.

Másodikként az 1 elemet tartalmazó halom Grundy-számát lehet meghatározni. Ennek ugyanis egy rákövetkező pozíciója van, az, amikor a halomban egyetlen elem sincs. A rákövetkezőnek már tudjuk a Grundy-számát, ami 0, így az egy elemű halom Grundy-száma H₁=lkkz(0)=1.

Két elemű halom esetén a két lehetséges rákövetkező állapot az 1, illetve a 0 elemű halom. Ezek már kaptak számokat, 1-et, illetve 0-t, ezért a 2 elemű halom Grundy-száma H₂=lkkz(0, 1)=2.

Általában az n elemű halomból kiindulva a Grundy-szám H_n=n. Ez azt jelenti, hogy a HALOM játék Grundy-száma - nem más, mint a halom elemeinek száma. Speciálisan a 2. ábrán látható játék Grundy-száma 5.

RELATÍV PRÍM. Jelöljük az n elemből induló játék Grundy-számát R_n-nel. Itt is az első két Grundy-szám R₀=0 (mivel a 0 elemű halomból nem lehet elvenni), illetve R₁=lkkz(R₀)=1. Ha két elemű halomból indulunk ki, az egyetlen lehetséges lépés az egy elem elvétele. Így R₂ nem más, mint lkkz(R₁)=lkkz(1)=0.

Három elemű halom esetén akár 1, akár 2 elemet is elvehetünk, így R₃= lkkz(R₁, R₂)= lkkz(1, 2)=0. Öt elem esetén maradhat 1, 2, 3, vagy 4 is, innen R₅=lkkz(R₁, R₂, R₃, R₄)=3.

Az alábbi táblázat R_n értékét mutatja n=20-ig.

Könnyen igazolható, hogy páros n-re R_n=0, ha n páratlan, és n-nek a legkisebb prímosztója éppen a k-adik prímszám, akkor R_n=k. (Az első prím a 2, a második a 3.)

LÉTRA. Az egyszerűség kedvéért a t=3 esettel foglalkozunk, a többi eset hasonlóan intézhatő el. Amíg a halomban legfeljebb 3 (=t) elem van, addig a LÉTRA és a HALOM játék ugyanaz, tehát az első négy Grundy-szám L₀=H₀=0, L₁=1, L₂=2, L₃=3. Ha viszont négy elemből indulunk ki, akkor a lépés eredménye nem lehet a 0 elemű halom, tehát L₄=lkkz(L₃, L₂, L₁)=lkkz(3, 2, 1)=0. Ötelemű halom esetén 4, 3 vagy 2 elemű halmot kaphatunk, így L₅=lkkz(L₄, L₃, L₂)=lkkz(0, 3, 2)=1. Általában az L_n az L_n-1, L_n-2, L_n-3 számok legkisebb kizártja, ami éppen n-nek 4-gyel - általában (t+1)-gyel - való osztásakor kapott maradék.

KIRÁLY. A játék pozícióit a sakktábla mezőivel azonosítjuk, a pozíciókhoz tartozó Grundy-számokat a mezőkbe írjuk. A bal felső sarokba 0 kerül, hiszen innen nem tudunk tovább lépni. A felső sor következő mezőjének Grundy-száma lkkz(0)=1, mert ebből a mezőből csak a 0 Grundy-számú sarokmezőbe tudunk lépni. A sor második (c8) mezőjéből csak az előzőbe kerülhetünk, így a beírandó szám lkkz(1)=0. A felső sorban tehát felváltva 0 és 1 áll, ugyanez igaz a bal szélső oszlopra is (8. ábra). Ezek kitöltés után egyetlen mező van, amelynek mindhárom rákövetkezőjét kitöltöttük: a b7 mező. Ebbe a rákövetkezők legkisebb kizártja, lkkz(0, 1, 1)=2 kerül. A c7 mező száma lkkz(0, 1, 2)=3, ezt folytatva a második sort - és evvel együtt a második oszlopot is - kitölthetjük. Ha ezekkel végeztünk, rátérhetünk a harmadik sorra stb.

8. ábra

A kitöltést természetesen nemcsak a 8x8-as sakktáblán, hanem akármekkora sakktáblán is elvégezhetjük. A 8. ábrán a vastagon kihúzott kis keretek segítenek a szabályszerűség felismerésében. Ennek alapján tetszőleges méretű sakktábla tetszőleges mezőjének Grundy-számát megmondhatjuk a teljes tábla kitöltése nélkül.

KIRÁLYNŐ. Nem részletezzük a tábla kitöltését, annak kezdő része a 9. ábrán látható. Sajnos nem valószínű, hogy valamilyen egyszerű formula megadná az egyes mezőbe irandó számokat.

9. ábra

BÁSTYA. Az ehhez a játékhoz tartozó Grundy-számok táblázata a későbbiekben fontos szerepet fog játszani (10. ábra). A felső sorban a számok 0-tól kezdve egyesével növekszenek, hiszen a felső sor egy mezőjéről a tőle balra levő mezők bármelyikére (és csak azokra) lehet lépni - ez lényegében azonos a HALOM játékkal. Ugyanez áll a bal szélső oszlopra is. Egy mezőbe akkor lehet a Grundy-számot beírni, ha az összes felette álló, illetve az öszes tőle balra levő mezőt már kitöltöttük. A mezőhöz tartozó Grundy-szám éppen az ezekben álló számok legkisebb kizártja, azaz a legkisebb olyan szám, amely sem az oszlopban, sem a sorában korábban még nem szerepelt.

10. ábra

A táblázat vastag vonalakkal határolt négyzetei a következő tétel érvényeségét mutatják n=1, 2, 3-ra:

1. tétel. A táblázat bal felső 2ⁿx2ⁿ méretű részének minden sorában és minden oszlopában a 0-tól (2ⁿ-1)-ig terjedő számok mindegyike pontosan egyszer fordul elő.

Legyenek i és j nemnegatív egész számok, és jelöljük ij-vel a balról számított (i+1)-edik oszlop és felülről számított (j+1)-edik sor metszéspontjában álló számot. Például a táblázat szerint 32=1, valamint 78=15. A táblázat szimetrikus a jobbra lejtő átlóra, ezért ij=ji minden (i,j) párra. A felső sorban a számok egyesével növekszenek, tehát 0i=i0=i; az átlóban pedig (legalábbis ameddig a 10. ábra mutatja) csupa 0 áll, így ii=0.

A következő két tétel is a BÁSTYA játék táblázatáról szól.

2. tétel. Legyen 0i,j<2ⁿ. Ekkor (i+2ⁿ)j=i(j+2ⁿ)=(ij)+2ⁿ, valamint (i+2ⁿ)(j+2ⁿ)=ij (11. ábra).

11. ábra

Bár mind az első, mind a második tételt önmagában nehéz volna igazolni, a két tételnek egyszerre, n-re vonatkozó indukcióval történő bizonyítása már nem nehéz. Ezt Olvasóinkra hagyjuk, csak úgy, mint annak meggondolását, hogyan következik a 2. tételből a

3. tétel. Írjuk fel i-t, j-t és ij-t is a kettes számrendszerben. Ekkor minden helyi értékre az ott álló három számjegy között páros sok (azaz 2 vagy 0) 1-es található.

A 3. tétel alapján tetszőleges i, j számra viszonylag gyorsan ki lehet számítani az ij számot, és ezt az i és i NIM-összegének nevezzük. Így például ha a 100=1 100 100₂ és az 50=110 010₂ számok NIM-összegét keressük, annak utolsó (kettes számrendszerbeli) helyi értékén 0, az utolsó előttin 1, az azt megelőzőn is 1 stb. áll aszerint, hogy egyezik-e a megfelelő két jegy vagy sem. Így 10050=1 010 110₂=86.

Világosabb a NIM-összeadás technikája, ha a számok kettes számrendszerbeli alakját szokásosan egymás alá írjuk (12. ábra).

 
1 100 100
 
  110 010
 

1 010 110

12. ábra

A 3. tételből az is következik, hogy tetszőleges i,j,k nemnegatív egészekre (ij)k=i(jk), azaz a NIM-összeadás asszociatív. Továbbá - mint már sejtettük -, ii=0 minden i-re. Ez a korábban megállapított ij=ji és i0=i összefüggésekkel együtt azt jelenti, hogy a nemnegatív egészek erre a műveletre nézve csoportot, mégpedig kommutatív, más néven Abel-csoportot alkotnak. A művelet egy érdekessége, hogy inverz művelete saját maga: i-hez ji-t kell NIM-adnunk ahhoz, hogy j-t kapjunk:

i(ji)=i(ij)= (ii)j=0j=j.

HUSZÁR. A Grundy-számok táblázatán (13. ábra) jól megfigyelhető ismétlődés a 8x8-as táblán még nem tudna kibontakozni. (Kérdés: miért nem fordul elő 4-nél nagyobb szám a táblázatban?)

13. ábra

Példáinkat befejezve rátérünk egy, már korábban kimondott tétel bizonyítására.

4. tétel. Egy véges játék minden pozíciójának van Grundy-száma.

Tegyük fel az állítással ellentétben, hogy a hozzárendelés szabálya szerint a játék egyetlen további pozíciójához sem lehet számot rendelni, és mégis van egy X₁ pozíció, amelyhez nem került szám. Ez csak amiatt lehetséges, hogy már X₁-nek valamely X₂ rákövetkezőjéhez sem írhattunk számot. Különben, ha X₁-nek nem volna rákövetkezője, akkor 0-t, egyébként pedig a rákövetkezőihez írt számok legkisebb kizártját írtuk volna. Ekkor X₂-nek is van olyan X₃ rákövetkezője, melyhez nem tartozik Grundy-szám, X₃-nak is van ilyen X₄ rákövetkezője, és így tovább. Ily módon kapjuk az X₁, X₂, X₃, ... pozíciókat úgy, hogy mindegyik X_i+1 pozíció az X_i rákövetkezője. Játékunkban azonban csak véges sok pozíció van, tehát ebben a sorozatban valamelyik pozíció ismét előfordul, például X_k=X_l, ahol 1k<l. Ám ekkor X_k-ból X_k+1-be, X_k+1-ből X_k+2-be, ..., X_l-1-ből X_l=X_k-ba lehet lépni, így gráfunkban létezik kör, azaz a játék nem véges, ellentétben kiinduló feltevésünkkel. Az ellentmondás éppen a tétel állítását bizonyítja.

4. Hogyan lehet egy játékot megnyerni?

Egy (véges) játék pozícióihoz rendelt Grundy-számoknak a következő három fontos tulajdonságuk van:

a) vesztő pozíció Grundy-száma 0;
b) ha egy pozíció Grundy-száma n0, akkor egyetlen rákövetkező pozíció Grundy-száma sem n;
c) ha egy pozíció Grundy-száma n>0, akkor a rákövetkező pozíciók között van n-1, n-2, ..., 1, 0 Grundy-számú pozíció is.

Ezekből a tulajdonságokból azonnal adódik az:

5. tétel. Egy véges játékban Kezdőnek akkor és csak akkor van nyerő stratégiája, ha a kezdő pozíció Grundy-száma 0-tól különbözik.

Ha ugyanis a kezdő pozíció Grundy-száma nem nulla, akkor a c) tulajdonság miatt van (esetleg több) 0 Grundy-számú rákövetkezője. Válassza Kezdő ezek valamelyikét. Most Második következik, és 0 Grundy-számú pozícióból indul. Második vagy azonnal veszít - ez az a) eset -, vagy pedig kénytelen olyan pozícióba lépni, amelynek Grundy-száma pozitív - b) eset. Következésképp Kezdő ismét pozitív Grundy-számú pozícióból léphet.

Összefoglalva, ha Kezdő eszerint a stratégia szerint játszik, akkor mindig pozitív Grundy-számú pozícióból léphet, aminek a c) tulajdonság miatt feltétlenül van 0 Grundy-számú rákövetkezője. Így Kezdő nem veszthet. S mivel a játék véges, így előbb-utóbb véget ér, Második a vesztes.

Megfordítva, ha a kezdő pozíció Grundy-száma 0, akkor Második érheti el, hogy valahányszor őrá kerül a sor, pozitív Grundy-számú pozícióból léphessen. Így ebben az esetben Másodiknak van nyerő stratégiája.

Ennek a tételnek a segítségével korábbi játékaink mindegyik pozíciójára meg tudjuk mondani, hogy onnan indulva Kezdő vagy Második tudja-e megnyerni a játékot, sőt magát a stratégiát is tudjuk: aki nyerni akar, annak mindig 0 Grundy-számú pozícióba kell lépnie. Ha csak egyszer is téved, ellenfele kezébe adja a nyerés lehetőségét.

Az 5. tétel bizonyítása a Grundy-számoknak az a), b) és c) tulajdonságán, valamint azon a tényen múlott, hogy a játék előbb-utóbb véget ér. A Grundy-számozást és ezzel együtt az 5. tételt nem véges játékokra is lehet általánosítani a következő módon.

A Grundy-számok hozzárendelésére a 3. pontban adott eljárást módosítsuk így:

Ahhoz a pozícióhoz, melynek nincs rákövetkezője, 0-t írunk.

Egy még Grundy-szám nélküli, X pozícióhoz az n0 számot a következő esetben rendeljük:

1. ha n a legkisebb kizártja azoknak a számoknak, amelyek X megszámozott rákövetkezőihez tartoznak;
2. ha X minden szám nélküli rákövetkezőjének van olyan megszámozott rákövetkezője, melynek Grundy-száma éppen n.

Nézzük, hogyan alkalmazható ez az eljárás a DUGÓ játékra (14.ábra). A C csúcs az egyetlen, amelyből nem indul ki út, így a C csúcs Grundy-száma 0. Ezután a D-hez írhatunk 0-t, mert D rákövetkezői B és E még számozatlanok, de mindkettőnek van 0 számú rákövetkezője (a C csúcs). Ezek után G száma 1, hiszen egyetlen rákövetkezőjének, D-nek Grundy-száma 0, és ugyanígy K száma 0.

14. ábra

Most az egyetlen csúcs, amit megszámozhatunk, E, melynek Grundy-száma 1. Valóban, E-nek egyetlen rákövetkezője C, míg másik, még számozatlan rákövetkezőjéből H-ból eljuthatunk az 1 Grundy-számú G-be. Mivel evvel B mindkét rákövetkezőjét kitöltöttük, B-be lkkz(0,1)=2 kerül, és ezért A-ba lkkz (0,2)=1.

Innen kezdve könnyen meghatározhatjuk az F, J, I, H, L, M, N, P csúcsok Grundy-számait: mire egy csúcsra sor kerül, addigra már összes rákövetkezője kapott már számot.

Maradhatnak olyan pozíciók is, melyek még a módosítás alapján sem kapnak számot. Ilyen játék gráfját mutatja a 15. ábra, az üres, illetve teli négyzetek mutatják a "számozhatatlan" csúcsokat. A módosított eljárással kapott Grundy-számok is rendelkeznek a korábban kimondott a), b), c) tulajdonságokkal, és igaz az 5. tételnek a következő általánosítása:

15. ábra

6. tétel. Egy játékan a Kezdő játékosnak pontosan akkor van nyerő stratégiája, ha kezdő pozíció valamely rákövetkezője nulla Grundy-számú.

A második játékosnak pontosan akkor van nyerő stratégiája, ha a kezdő pozíció nulla Grundy-számú.

Minden más esetben mindkét játékos elérheti, hogy ne kapjon ki, azaz ha mindketten "okosan" játszanak, a játék sohasem ér véget.

A 6. tétel bizonyítása hasonló az 5. tétel bizonyításához, csak annál kissé bonyolultabb, szintén az Olvasóra hagyjuk. A 6. tétel alapján a 15. ábra játékát Kezdő nyeri, ha a kezdő pozíció az 1-gyel, a 2-vel vagy a három teli négyzettel jelölt pozíciók valamelyike; Második nyeri, ha a két nullás pozíció valamelyikéből indulnak; végül a játék döntetlen, ha az üres négyzetek bármelyike a kezdő pozíció.

A DUGÓ játéknál a kezdő pozíció az M csúcs, aminek Grundy-száma 0, tehát Másodiknak van nyerő stratégiája. Az a dolga, hogy Kezdő minden lélpése után valamelyik 0 Grundy-számú csúcsba irányítsa az autót.

5. Játékok összege

Egy játékot játszani nem mindig nehéz, sőt, néha annyira egyszerű, hogy nem is tekintjük igazán játéknak. Mondjuk azt mindjárt a HALOM-nál. Ám rögtön érdekessé, sőt nehézzé válik, ha több HALOM játékot kell egyszerre áttekinteni, a játékok között valamiféle "egyensúlyt" fenntartani azzal a feltétellel, hogy a soros játékos a rendelkezésre álló több játék közül csak az egyikben léphet. De hogy melyikben, és hogyan, azt már ő dönti el. A vesztes most is az, aki nem tud lépni, azaz aki az utolsónak maradó játékot veszti el.

Hogy könnyebben tudjunk ezekről az összetett játékokról beszélni, egy jelölést vezetünk be. A J₁ és J₂ játékok összegének nevezzük, és (J₁+J₂)-vel jelöljük azt a játékot, melyben a soros játékos a J₁ vagy a J₂ játékok közül pontosan az egyikben lép egyet. hasonlóan definiáljuk a J₁+J₂+J₃ stb. összegeket is. Egy összegjáték valamelyik összeadandója lehet maga is egy összeg, ilyenkor azonban a rész-összeadandókat anélkül, hogy előbb külön összeadnánk őket, közvetlen tagoknak is tekinthetjük.

Elsőként nézzük meg, mi történik, ha ugyanazt a játékot vesszük két példányban, vagyis vizsgáljuk a J+J összeget. Ebben kezdőnek nem lehet nyerő stratégiája. Játszon ugyanis Második a következőképpen: akármit is lép Kezdő, lépje ő ugyanazt a másik játékban. Így Másodiknak minden lépése után mindkét játék ugyanabba a pozícióba kerül, tehát, ha Kezdő tud lépni, tud lépni Második is. Ha J játék véges, akkor persze J+J is az, és ekkor J+J-ben Másodiknak van nyerő stratégiája.

Valamivel bonyolultabb a helyzet a J+J+J játéknál. Ha Másodiknak van nyerő stratégiája J-ben, akkor a J+J+J összeget is megnyeri: Kezdő bármelyik játékot is választja, lépje Második ugyanabban a játékban a J-beli nyerő stratégiája szerinti válaszlépést. Így Második a J mindhárom példányát megnyeri, tehát az összeget is.

Ha viszont Kezdőnek van nyerő stratégiája J-ben, és J véges, akkor Kezdő J+J+J-t is meg tudja nyerni. A három J közül az elsőt mintegy szívügyének tekinti, és abban a (J-beli) nyerő stratégiája szerint játszik. Például első lépését is ott teszi meg, és valahányszor Második ebben lép egyet, Kezdő is itt válaszol. A másik két játék csak ráadás: Ha Második az egyikben lép valamit, Kezdő lépje ugyanazt a másikban. E szerint játszva Kezdő nem veszthet, s mivel J, és ezzel együtt J+J+J is véges, végül is nyer.

Az a feltétel, hogy J véges, nem hagyható el. Található ugyanis olyan nem véges J játék, amelyben Kezdőnek nyerő stratégiája van, s ugyanakkor J+J+J-t Második akkármeddig elhúzhatja.

Az 5. tétel alapján egy véges játékban Másodiknak akkor és csak akkor van nyerő stratégiája, ha a játék Grundy-száma 0. Mivel J-vel együtt J+J, J+J+J, ... is véges, az előbbieket egy kissé általánosítva a következő tételt kapjuk:

7. tétel. Ha a J véges játék Grundy-száma 0, akkor a J+J, J+J+J, ... játékok Grundy-száma is 0. Ha a J véges játék Grundy-száma pozitív, akkor a J+J+J, J+J+J+J+J, ... játékok Grundy-száma is pozitív, ugyanakkor J+J, J+J+J+J, ... Grundy-száma 0.

Ez a tétel egyszerű következménye a következő, első látásra meglepő tételnek, mely azt mondja ki, hogy játékok összegének Grundy-száma kiszámítható a játékok Grundy-számából, s nem függ az összeadandők struktúrájától.

8. tétel. Legyen a J₁ játék Grundy-száma j₁, a J₂ játéké j₂. Ekkor J₁+J₂ Grundy-száma j₁j₂, vagyis j₁ és j₂ NIM-összege.

Bizonyításul csak azt az esetet vizsgáljuk, ha J₁ és J₂ végesek; az általános eset hasonlóan kezelhető, csak bonyolultabb. A J₁+J₂ pozícióit olyan párokkal ábrázolhatjuk, melyek első tagja a J₁ játéknak, második tagja pedig a J₂ játéknak egy-egy pozíciója. Ha a J₁-beli X pozíció (J₁-beli) rákövetkezői X₁, X₂, ... X_n; a J₂-beli Y pozíció rákövetkezői Y₁, Y₂, ... Y_m, akkor J₁+J₂ játék (X, Y) pozíciójának összesen n+m rákövetkezője van, és ezek (X₁, Y); (X₂, Y); ...; (X_n, Y), valamint (X, Y₁); (X, Y₂); ...;(X, Y_m). Az első n pár annak felel meg, mikor a soros játékos J₁-ben lép, a második m pedig annak, amikor J₂-ben.

Feltevésünk szerint J₁, J₂ végesek, tehát mindkét játék minden pozíciójához tartozik Grundy-szám. Jelölje az X pozícióhoz tartozó J₁-beli Grundy-számot g, az X₁, ..., X_n pozíciókhoz tartozókat g₁, ..., g_n, a J₂ játék Y pozíciójához tartozó J₂-beli Grundy-számot h, az Y₁, ..., Y_m pozíciókhoz tartozókat h₁, ..., h_m. Tételünk azt állítja, hogy a J₁+J₂ játék (X, Y) pozíciójához tartozó Grundy-szám gh. Ezt a Grundy-számok előállítására vonatkozó szabály alapján indukcióval igazoljuk, ebből a tétel állítása azonnal adódik.

Egy pozícióhoz (véges játék esetén) két állapotban írhatunk Grundy-számot: vagy ha a pozíciónak nincs rákövetkezője, vagy ha a pozíció minden rákövetkezőjének már van Grundy-száma. Tekintsük a J₁+J₂ játék (X, Y) pozícióját. Ennek pontosan akkor nincs rákövetkezője, ha sem X-nek, sem Y-nak nincs rákövetkezője. Ekkor X-nek, Y-nak és (X, Y)-nak is 0 a Grundy-száma, és 00 = 0.Erre az esetre tehát igaz az állítás.

Most tegyük fel, hogy a J₁+J₂-beli (X, Y) pozíció minden rákövetkezőjének már van Grundy-száma, továbbá indukciós hipotézisként tegyük fel azt is, hogy az (X_i, Y) pozíció Grundy-száma g_ih, az (X, Y_j) pozíció Grundy-száma gh_j (itt in; jm, és n=0 vagy m=0 is lehetséges). Mivel X és Y Grundy-száma a rákövetkezőihez tartozó számok legkisebb kizártja, azaz

g=lkkz(g₁, ..., g_n), illetve h=lkkz (h₁, ..., h_m),q másrészt (X, Y) Grundy-száma

lkkz(g₁ h, ..., g_n h, gh₁, ..., gh_m).

Ahhoz, hogy tételünket bizonyítsuk, elegendő megmutatnunk, hogy a (2)-ben szereplő érték éppen gh. Ez két dolgot jelent. Egyrészt azt, hogy gh nem fordul elő a zárójelben felsoroltak között, másrészt azt, hogy minden (g h)-nál kisebb érték szerepel. Kezdjük az elsővel. Ha gh=g_ih volna, akkor ennek mindkét oldalához h-t NIM-adva

g0=g(hh)= (gh)h=(g_ih)h=g_i(hh)=g_i0,

azaz g=g_i volna, ami (1) miatt lehetetlen. Hasonlóan gh=gh_j sem állhat fenn hh_j miatt. Így g h valóban nem fordul elő (2)-ben a zárójelen belül.

A gh NIM-összeg definíció szerint a (g-1)h, ..., 1h, 0h és a g(h-1), ..., g1, g0 számok legkisebb kizártja (10. ábra). Az (1) feltétel szerint a g₁, ..., g_n legkisebb kizártja g, így a g₁, ..., g_n között a g-1, ..., 1, 0 számok mind megtalálhatók. Következésképpen (2)-ben a g-1h, ..., 0h mindegyike, s ugyanezért a gh-1, ..., g0 mindegyike is szerepel. Így (2) értéke legalább gh, mivel több szám kizártja nem lehet kisebb, mint egy részhalmazuké. De gh nem szerepel közöttük, azért (2) értéke valóban gh. Ezzel igazoltuk a 8. tételt.

Mindjárt alkalmazzuk is a tételt: a Második játékosnak a J+J játékban nemcsak akkor van nyerő stratégiája, ha J véges, hanem akkor is, ha J kezdő pozíciójának , azaz J-nek van Grundy-száma, mondjuk j. Valóban J+J Grundy-száma az előző tétel alapján jj=0, ami a 6. tétel alapján Második nyerő stratégiájának létezését tanúsítja. Másodiknak úgy kell lépnie, hogy a két játékban mindig egyforma Grundy-számú pozíciót állítson elő. Ilyen lépésből természetesen több is lehet, de nem feltétlenül vezet ezek mindegyike közelebb a győzelemhez. Például, ha két DUGÓ játékot játszanak egyszerre - vagy ami ugyanaz, kezdeben két autó indul ugyanabból a városból (mindegy, hogy melyikből), és egy lépésben az egyik autót vihetik tovább -, akkor Második biztosan nyer.

Minden összeget két tagú tagok összegére bonthatunk fel, a 8. tétel tehát nemcsak két, hanem akárhány játék összegére is alkalmazhatjuk. Ezt tesszük a következő játék elemzésénél.

TRIDUGÓ. A játékot a DUGÓ játék tábláján játssza a két játékos (7. és 14. ábra). Kezdetben egy-egy autó indul az A, a K és a P városból. A soron következő játékos az egyik autót jelenlegi helyéről egy szomszédos városba irányítja. Egy városban egyszerre akár mind a három autó is tartózkodhat. A nyertes az, aki az utolsó autót C-be irányítja (vagyis veszít az, aki nem tud lépni).

A figyelmes Olvasó azonnal észreveszi, hogy ez három DUGÓ játék összege. Az egyikben az autó A-ból, a másikban K-ból, a harmadikban pedig P-ből indul. Az egyes játékok Grundy-számai a 14. ábra jobb oldala alapján rendre 1, 0, illetve 2, az összjáték Grundy-száma tehát 102=3. Így Kezdőnek van nyerő stratégiája. Egyrészt arra kell ügyelnie, hogy minden lépése után a három autó alatt álló szám NIM-összege 0 legyen - ez könnyű -, másrészt arra, hogy a játék befejeződjön, ez már nehezebb. Ez utóbbi cél elérése érdekében célszerű, ha mindig olyan lépést választ, amelyben a mozgatott autó kisebb Grundy-számú pozícióba lép, de persze ez nem elég. Kezdőnek két olyan indulása is van, mellyel az összjáték Grundy-száma nullává válik: az egyikben az A-beli autót B-be, a másikban a P-beli autót N-be kell irányítania. Ha gyors győzelmet akar elérni, célszerű a második lehetőséget választania, ebben az autó egy 2 Grundy-számú pozícióról egy 1, azaz kisebb számú pozícióba lép. Az AB lépés viszont több kombinációra ad lehetőséget, talán az ellenfél nagyobb kedvvel veti bele magát a reménytelen küzdelembe.

6. további játékok: a NIM és családja

NIM. Van néhány halom tárgyunk. Egy lépésben valamelyik halomból valahány elemet kell elvenni, akár az egész halmot is. A játék nyertese az, aki az utolsó elemet elveszi.

Természetesen a játék Grundy-száma a halmokban található elemek számának NIM-összege, s aki nyerni akar, annak úgy kell játszania, hogy minden lépése után ez az összeg 0 legyen.

A NIM játéknak ezt a formáját és a hozzá tartozó stratégiát Olvasóink bizonyára jól ismerik. Azonban a játéknak több érdekes és kevésbé ismert változata is van. Ezek közül az elsőként bemutatandó változat D. G. Northcott nevéhez fűződik.

GYALOGOS. A játékot a (8 X 8-as) sakktáblán a nyolc fehér és a nyolc fekete gyaloggal (paraszttal) játsszák, olyanféle kiinduló állásból, amilyet a 16. ábra mutat. Minden sorban pontosan egy fekete és egy fehér gyalog áll. Kezdő a fehér gyalogokat, Második a feketéket mozgatja úgy, hogy ugyanabban a sorban akárhány mezőt előre vagy hátra léphet, de az ellenfél figuráját nem ugorhatja át, és nem állhat rá az ellenfél mezőjére sem. A vesztes az, aki nem tud lépni, azaz akinek az összes figurája "beszorult" (a sor valamelyik végén).

16. ábra

Annak ellenére, hogy a játék nem véges, lényegében egy "bújtatott" NIM-ről van szó. Benne a halmok elemszámát a szemben álló gyalogok közti üres mezők száma adja meg. Így a bemutatott pozíció Grundy-száma 40031135=1. Kezdő tehát nyer, első lépésével a negyediktől a nyolcadik sorig bármelyikben kell egy mezővel kell közelednie ellenfeléhez. Ha Második hátrál, Kezdő ugyanannyival utánnamegy, hogy a figurák közti távolság ne változzék. Ha pedig Második támad, azaz egyik gyalogját közelebb húzza Kezdő megfelelő gyalogjához, akkor a sornak megfeleltetett halmot csökkenti, és Kezdő a NIM játék stratégiája szerint válaszolhat, ami - szükség szerint - ugyanabban vagy egy másik sorban történik meg.

Így Kezdő mindig közeledik ellenfeléhez, egy idő múlva az már nem tud hátrálni, tehát veszít.

BUBORÉK. Egy fölfelé haladó kanyargós "csőben", amely a 17. ábra szerint mezőkre van osztva, a játékosok elhelyeznek néhány "buborékot", ezeket a sötét körök jelzik. Egy lépésben valamelyik buborékot kell valahány mezővel feljebb tolni. Egy mezőben legfeljebb egy buborék tartózkodhat, és a buborékok nem előzhetik meg egymást. Az ábrán a nyíl egy szabályos lépést mutat. A játék akkor ér véget, amikor az összes buborék a cső tetején gyűlik össze, s a vesztes az, aki már nem tud lépni.

17. ábra

Ebben a játékban is megtaláljuk a NIM-et. Induljunk el a legalsó buboréktól és minden páratlan sorszámú buboréktól számoljuk meg az üres mezőket a következőig (illetve páratlan sok buborék esetében utoljára a cső tetejéig). Ezek a számok adják ki a NIM halmok elemszámait, esetünkben ez 7, 4 és 4. Mindkét játékos bármelyik "halmot" bármennyivel csökkentheti, s ha egy játékos egy "halom" felső végét megtolja, ellenfele ezt lépését semlegesítheti az alsó határoló buborék alkalmas megtolásával. Így aki a NIM játékot a fent leírt halmokkal megnyeri, az nyeri meg a buborék játékot is. A bemutatott helyzetben Kezdőnek van nyerő stratégiája, s első lépésként például a legfelső buborékot tolhatja eggyel feljebb. Ezután a lépés után előálló halmok mérete ugyanis 3, 4, 7, melyek NIM-öszege 0. Jó kezdő lépés az is, ha a legalsó buborékot csatlakoztatja a megelőzőhöz, azaz a 7 elemű halmot teljes egészében elveszi.

FAVÁGÓ. Egy erdőben a fák egy négyzetrács pontjaiban helyezkednek el, bár innen-onnan már hiányzik egy-egy fa (18. ábra). A játékosok felváltva vágják ki (=áthúzzák) a fákat: a soron következő játékos egy vízszintes sorból egyet vagy többet, de csak szomszédosokat vághat ki. A vesztes az, akinek nem marad kivágni való fája.

18. ábra

Így akár Kezdő a felső sorból akár az első négy, akár az utolsó négy fát kivághatja, de nem vehet el mind a két részből, hiszen azok már nem volnának szomszédosak. Maga a játék természetesen nem más, mint az egyes összefüggő fasorokon játszott játékok összege, esetünkben 8 játék összege. Egy összefüggő fasoron a játék lényegében a HALOM játék, azzal a különbséggel, hogy egy vagy több fa kivágásán (elvételén) kívül a megmaradt részt még két különálló részre lehet osztani. Ez azonban nem befolyásolja a játék kimenetelét. Annak a játékosnak ugyanis, ekinek a NIM játékban nyerő stratégiája van, nem érdeke, hogy növelje a különálló halmok számát. Ellenfele pedig ha az n₀, n₁, ..., hosszúságú sorok közül az n₀ méretűt néhány közbülső kivágásával egy k és egy l hosszúságúra bontja szét, akkor ezzel egy klk+l < n₀ miatt nem lehet nulla, tehát hiába növelte a hálmok számát.

A 18. ábra játékának Grundy-száma ezek szerint 44627135=4, vagyis Kezdőnek van nyerő stratégiája. Jó kezdő lépés például az, ha a legfelső sorból az első négy fát kivágja.

Ismeretes, hogy a NIM-ben két egyező elemszámú halmot a játékosok bármely lépésük után egyszerűen figyelmen kívül hagyhatnak, hiszen azok együtt a játék kimenetelét nem befolyásolják. Játszhatnának tehát úgy is, hogy külön-külön helyet tartanak fenn az egy elemű, a két elemű stb. halmoknak, és mindegyik helyen legfeljebb egy, annyi elemszámú halom állhat. Amikor lépnek, akkor a változtatandó halmot kiveszik helyéről, elveszik belőle a megfelelő számú elemet, mjd visszateszik az új helyére, ha azon a helyen még nem állna halom; illetve ha már áll, akkor az előállított halmot és az ott álló, vele egyező elemszámú halmot is félreteszik - azok igazában már nem vesznek részt a játékban. Vegyük észre, hogy nincs is szükség tárgyakra, halmokra, mindössze azt kell jelölnünk, hogy van-e 1, 2 stb. elemszámú halmunkvagy nincs. Ezt az absztrakciós lépést meg is tesszük a következő játékban.

FORDÍTÓ. Van 10 korongunk, mindegyiknek az egyik lapja piros, a másiknak kék. A korongokat a játék elindításához egy sorba rakjuk, néhányat a piros, másokat a kék oldalával felfelé (19. ábra). A soron következő játékos két eljárásból választhat: vagy egy korongot a piros oldaláról a kékre fordít, vagy két korongot fordít meg, de ezek közül a jobb oldali (nagyobb sorszámú) korongot a piros oldaláról a kékre kell fordítania. a vesztes az, aki már nem tud lépni, vagyis az nyer, akinek lépése után minden korongnak a kék oldala látszik.

19. ábra

A játékban éppen a fent leírt módon bújtattuk el a NIM-et. Az i-edik korong piros fele éppen ezt mutatja, hogy van i elemű halmunk, kék fele pedig azt, hogy nincs. Így a FORDÍTÓ játék egy pozíciójának Grundy-számát úgy kaphatjuk meg, ha a piros korongok sorszámait NIM-adjuk össze. A 19. ábra Grundy-száma tehát 23710=12. Ebből 0 Grundy-számú pozíciót csak a 10 elemű halomnak 6 eleműre való csökkentésével lehet elérni, tehát az egyetlen nyerő lépés az, ha a 10. és a 6. korongot megfordítjuk.

A NIM-hez hasonló, csak kevésbé ismert játék a RIM. Van néhány halom tárgyunk. Egy lépésben valamelyik halomból valahány elemet kell elvennünk, de csak annyit szabad, hogy az elvett elelmek száma és az elvétel elötti elemek száma relatív prím legyen egymáshoz.

A játék természetesen több RELATÍV PRÍM játék összege, így elegendő a RELATÍV PRÍM Grundy-számait ismernünk ahhoz, hogy nyerhessünk.

Hasonló játék a

DIM. Az előzőtől abban különbözik, hogy az elvett elemek száma osztója kell hogy legyen a halomban eredetileg található elemek számának. (Így például bármely halomból akár az összes elemét is elvehetjük.)

Itt is egyetlen játék több példányáról van szó, egyetlen halom esetén a Grundy-számok a következők:

Az előző játékok keveréke a

RIDINIM. Van három halom tárgyunk. Egy lépésben csak az egyik halomból lehet elvenni, mégpedig a következő szabályok szerint. Az első halomból csak annyit, hogy az elvett elemek száma relatív prím legyen a halom elvétel előti elemszámához (RI), a másikból annyit, hogy az elvett elemek száma osztója legyen a halom elemszámának (DI), a harmadik halomból pedig akármennyit el lehet venni (NIM).

Induljunk ki három 10 elemű halomból. Az első halom Grundy-száma R₁₀=0, a másodiké 2, a harmadiké 10. Tehát Kezdőnek van nyerő stratégiája, s az egyetlen jó kezdő lépése az, ha a harmadik halomból 8 elemet elvesz.

Nemcsak a HALOM hanem például a LÉTRÁ-t is lehet NIM-szerűen játszani, például a következőképpen.

HEGYMÁSZÓ. Három hegymászó egy 5000 méter magas hegyet akar megmászni. A hegyen 1000 méterenként egy-egy menedékház van, a hegymászók ott megpihenhetnek, akár mindhárman egy házban (20. ábra). A három hegymászó közül az egyik még gyakorlatlan, egy alkalommal csak az 1000 méterrel feljebb levő manadékházig képes menni. A második akár 1000, akár 2000 métert tud haladni, míg a legügyesebb a harmadik menedékházhoz is fel tud érni.

20. ábra

A játékosok felváltva egy-egy hegymászót visznek a mondott megszorításokkal valamelyik magasabban fekvő menedékházba. Az nyer, aki az utolsó hegymászót is a csúcsra viszi.

A játék elemzését az Olvasóra hagyjuk.

7. Oktális játékok, egy megoldatlan probléma

21. ábra

Jelöljük általában d_n-nel azt a pozíciót, melyet n egymás mellett álló bábu alkot, és legyen D_n az ehhez a pozícióhoz tartozó Grundy-szám. Például a 21. ábrán látható pozíció nem más, mint d₄+d₁+d₃+d₂, és értéke D₄D₁D₃D₂. Egy lépés után a d_n pozícióból mindazokba, és csak azokba a d_a+d_b összeggel jelzett pozíciókba kerülhetünk, ahol a+b vagy (n-1)-gyel, vagy (n-2)-vel egyenlő. Ennek alapján a D_n értéket sorban meghatározhatjuk. Nyilvánvalóan D₀=0 és D₁=1. A d₂ pozíció lehetséges rákövetkezői d₀ és d₁, így D₂=lkkz (D₀, D₁)=2. Hasonlóan D₃ rákövetkezői d₁, d₂, valamint d₁+d₁, ez utóbbi azt az esetet jelöli, amikor a három szomszédos bábu közül a középsőt döntjük le. Így D₃=lkkz (D₀, D₁, D₁+D₁)=lkkz (1, 2, 0)=3. Hasonlóan továbbmenve

D₄=lkkz (D₂, D₁D₁, D₃, D₂D₁)=lkkz (2, 0, 3, 20)=1,

D₅=lkkz (D₃, D₂D₁, D₄, D₃D₁, D₂D₂)=lkkz (3, 21, 1, 31, 22)=4.

Módosítsuk egy cseppet a játékot: mondjuk ki, hogy nem szabad egyetlen bábut ledönteni, mindig két szomszédosat kell eltalálniuk. Természetesen papíron is játszhatunk: egy sorba pontokat rajzolunk.

A soron következő játékos két szomszédos, még szabad pontot összeköthet. A vesztes természetesen az, aki nem tud lépni.

Legyen ennél a módosított játéknál az n szomszédos ponthoz tartozó Grundy-szám E_n. Az E_n számokat az előzőekben leírtakhoz hasonlóan számíthatjuk ki. Például E₀=0, E₁=0 (mivel egy pont esetén is Kezdő veszít), E₂=1, E₃=1, E₄=2 és például

E₆=lkkz (E₄, E₃E₁, E₂E₂)=lkkz (2, 10, 11)=3.

Az E_n sorozat is periódikus n68-ra, 34 hosszúságú periódussal:

Mindkét játék az úgynevezett oktális játékok családjába tartozik, az első a ^.77, a második a ^.07 számhoz tartozó játék. Általában az ^.A₁A₂A₃... sorozathoz tartozó oktális játék a következő. Ha az A_k0 "számjegy" kettes számrendszerbeli alakja éppen 2^a+2^b+..., ahol a,b stb. egymástól különböző nemnegatív egészek, akkor egy szabályos lépésben bármely rendelkezésre álló halmot k elemmel lehet csökkenteni, majd a vagy b stb. nem üres részre kell szétbontani.

Így, mivel 3=2¹+2⁰, a ^.333... játékban bármely halmot akárhány elemmel lehet csökkenteni, és a megmaradó elemekből 1 vagy 0 részt lehet készíteni (azaz az egész halmot is el lehet venni). Ez a játék éppen a NIM.

A ^.77 esetén 7=2²+2¹+2⁰, így bármely halomból 1 vagy 2 elemet lehet elvenni, és a megmaradt elemeket 0, 1 vagy 2 részre lehet osztani. Ha arra gondolunk, hogy az elemek egy sorban állnak, akkor ez éppen azt jelenti, hogy a sorból tetszőleges helyről 1 vagy 2 szomszédos elemet elvehetünk, vagyis éppen Dudeney KUGLI játékát kapjuk.

Általánosabb játékként tekintsük a ^.156 játékot. Ebben egyetlen elemet akkor vehetünk el, ha az egyedül alkot egy halmot (mivel 1=2⁰); két elemet akkor vehetünk el, ha ezzel vagy az egész halmot elvesszük, vagy a maradékból két további nem-üres halmot csinálunk (mert 5=2²+2⁰); végül 3 elemet csak 3-nál több elemű halomból vehetünk el, a maradékot viszont (ha akarjuk) két részre oszthatjuk (hiszen 6=2²+2¹). Ezt a játékot azért mutatjuk be, mert J. C. Kenyon felfedezte, hogy Grundy-számai 3479-től kezdve 349 hosszúságú periódust alkotnak.

A többi oktális játék Grundy-számai hasonlóan viselkednek, Közülük jónéhányat megvizsgáltak és legtöbbjükben a Grundy-számok valahonnan kezdve periodikus sorozatot alkotnak. A véges sok jeggyel leírható oktális játékok közül még egynek a Grundy-számairól sem sikerült megmutatni, hogy nem periodikus sorozatot alkotnak, bár azt sem sikerült igazolni, hogy ezek a sorozatok mindig periodikusak volnának. R. Guy végtelen sok oktális játékról megmutatta, hogy Grundy-számai periodikusak: a ^.77...777 számú játékban, ha 2^k darab (k1) hetes szaerepel, a Grundy-számok 36^.2^k-tól kezdve 6^.2^k hosszúságú periódust alkotnak.

Az oktális játékok közül az egyik legegyszerűbb, ami tulajdonképpen nem is tekinthető igazán oktális játéknak, P. M. Grundy eredeti játéka. Ebben egy lépésben egy halmot két nem-üres részre kell szétosztani. A játék Grundy-számait több mint negyedmillióig megvizsgálták, és noha sok "majdnem-periódust" találtak, a sorozat nem mutatott periodicitást. Hogy ez a sorozat periodikus-e vagy sem, mindmáig nyitott kérdés.

Irodalom

[1] J. D. Williams: Játékelmélet, Műszaki Könyvkiadó, Budapest, 1972.

[2] Neumann János: Válogatott előadások és tanulmányok, Közgazdasági és Jogi Könyvkiadó, 1965.

[3] Ilyen játékokat írt le Vargha Balázs: Játékkoktél, Minerva Kiadó, 1967, könyvének 128-294. oldalain

[4] J. H. Conway: On numbers and games, Academic Press, 1976

Számítógépes programok

Gyalogos Ez a játék a 6. fejezetben látott GYALOGOS játék egy módosítása. A cél az ellenfél bábuinak beszorítása.

Kugli Ez a játék a 7. fejezetben látott KUGLI játék. Minden lépésben egy vagy két közvetlenül egymás mellett álló bábut lehet levenni. Az győz, aki az utolsó bábut leveszi.

Favágó Ez a játék nem azonos a 7. fejezetben látott játékkal. A két játékos felváltva vág le egy-egy ágat a fáról. Az ággal együtt leesnek a belőle kinövő további ágak is. Végül csak a fa gyökere marad meg. Az nyer, aki az utolsó ágat levágja.