Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?
Csirmaz László: Játékok és Grundy-számaik

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 X1, X2, ..., Xk pozíciók, hogy X1-ből X2-be, X2-ből X3-ba, ..., Xk-1-ből Xk-ba, és Xk-ból X1-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 x1, x2, ..., xk nemnegatív egész számok legkisebb kizártján azt a legkisebb nemnegatív egészet értjük, amely nem fordul elő az x1, x2, ..., xk számok között. Ezt a számot a legkisebb közös többszörös mintájára lkkz(x1, x2, ..., xk) 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 H0=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 H1=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 H2=lkkz(0, 1)=2.

Általában az n elemű halomból kiindulva a Grundy-szám Hn=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 Rn-nel. Itt is az első két Grundy-szám R0=0 (mivel a 0 elemű halomból nem lehet elvenni), illetve R1=lkkz(R0)=1. Ha két elemű halomból indulunk ki, az egyetlen lehetséges lépés az egy elem elvétele. Így R2 nem más, mint lkkz(R1)=lkkz(1)=0.

Három elemű halom esetén akár 1, akár 2 elemet is elvehetünk, így R3= lkkz(R1, R2)= lkkz(1, 2)=0. Öt elem esetén maradhat 1, 2, 3, vagy 4 is, innen R5=lkkz(R1, R2, R3, R4)=3.

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

n01234 567891011 121314151617 181920
Rn0102 0304020 5060207 080

Könnyen igazolható, hogy páros n-re Rn=0, ha n páratlan, és n-nek a legkisebb prímosztója éppen a k-adik prímszám, akkor Rn=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 L0=H0=0, L1=1, L2=2, L3=3. Ha viszont négy elemből indulunk ki, akkor a lépés eredménye nem lehet a 0 elemű halom, tehát L4=lkkz(L3, L2, L1)=lkkz(3, 2, 1)=0. Ötelemű halom esetén 4, 3 vagy 2 elemű halmot kaphatunk, így L5=lkkz(L4, L3, L2)=lkkz(0, 3, 2)=1. Általában az Ln az Ln-1, Ln-2, Ln-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ő 2nx2n méretű részének minden sorában és minden oszlopában a 0-tól (2n-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<2n. Ekkor (i+2n)j=i(j+2n)=(ij)+2n, valamint (i+2n)(j+2n)=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 1002 és az 50=110 0102 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 1102=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 X1 pozíció, amelyhez nem került szám. Ez csak amiatt lehetséges, hogy már X1-nek valamely X2 rákövetkezőjéhez sem írhattunk számot. Különben, ha X1-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 X2-nek is van olyan X3 rákövetkezője, melyhez nem tartozik Grundy-szám, X3-nak is van ilyen X4 rákövetkezője, és így tovább. Ily módon kapjuk az X1, X2, X3, ... pozíciókat úgy, hogy mindegyik Xi+1 pozíció az Xi 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 Xk=Xl, ahol 1k<l. Ám ekkor Xk-ból Xk+1-be, Xk+1-ből Xk+2-be, ..., Xl-1-ből Xl=Xk-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 J1 és J2 játékok összegének nevezzük, és (J1+J2)-vel jelöljük azt a játékot, melyben a soros játékos a J1 vagy a J2 játékok közül pontosan az egyikben lép egyet. hasonlóan definiáljuk a J1+J2+J3 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 J1 játék Grundy-száma j1, a J2 játéké j2. Ekkor J1+J2 Grundy-száma j1j2, vagyis j1 és j2 NIM-összege.

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

Feltevésünk szerint J1, J2 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ó J1-beli Grundy-számot g, az X1, ..., Xn pozíciókhoz tartozókat g1, ..., gn, a J2 játék Y pozíciójához tartozó J2-beli Grundy-számot h, az Y1, ..., Ym pozíciókhoz tartozókat h1, ..., hm. Tételünk azt állítja, hogy a J1+J2 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 J1+J2 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 J1+J2-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 (Xi, Y) pozíció Grundy-száma gih, az (X, Yj) pozíció Grundy-száma ghj (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(g1, ..., gn), illetve h=lkkz (h1, ..., hm),q másrészt (X, Y) Grundy-száma

lkkz(g1 h, ..., gn h, gh1, ..., ghm).

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=gih volna, akkor ennek mindkét oldalához h-t NIM-adva

g0=g(hh)= (gh)h=(gih)h=gi(hh)=gi0,

azaz g=gi volna, ami (1) miatt lehetetlen. Hasonlóan gh=ghj sem állhat fenn hhj 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 g1, ..., gn legkisebb kizártja g, így a g1, ..., gn 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

Több HALOM játék összege az ismert NIM játék:

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 n0, n1, ..., hosszúságú sorok közül az n0 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 < n0 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:

elemszám01234 567891011 121314151617 181920
Grundy-szám01213 1214121 3121512 13
Általában, ha az elemszám 2k-nal osztható, de 2k+1-nel már nem, akkor a hozzá tartozó Grundy-szám k+1.

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 R10=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

KUGLI. Ezt a játékot H. E. Dudeney (1847-1930) híres angol rejtvényszerző írta le először. A játék alapja egy 14. századbeli népszerű francia labdajáték - a quilles -, mely kétségtelenül a mai kugli (és teke) őse. A játékhoz több kuglibábut állítunk fel egy sorba, egymás mellé (21. ábra). A játékosok olyan ügyesek, hogy a kugligolyóval akaratuk szerint bármelyik bábut vagy bármely két szomszédos bábut le tudják dönteni. Egymástól távolabb levő bábukat viszont lehetetlen egyszerre ledönteni. A játékot az nyeri, aki az utolsó bábut dönti le.

21. ábra

Jelöljük általában dn-nel azt a pozíciót, melyet n egymás mellett álló bábu alkot, és legyen Dn 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 d4+d1+d3+d2, és értéke D4D1D3D2. Egy lépés után a dn pozícióból mindazokba, és csak azokba a da+db összeggel jelzett pozíciókba kerülhetünk, ahol a+b vagy (n-1)-gyel, vagy (n-2)-vel egyenlő. Ennek alapján a Dn értéket sorban meghatározhatjuk. Nyilvánvalóan D0=0 és D1=1. A d2 pozíció lehetséges rákövetkezői d0 és d1, így D2=lkkz (D0, D1)=2. Hasonlóan D3 rákövetkezői d1, d2, valamint d1+d1, 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 D3=lkkz (D0, D1, D1+D1)=lkkz (1, 2, 0)=3. Hasonlóan továbbmenve

D4=lkkz (D2, D1D1, D3, D2D1)=lkkz (2, 0, 3, 20)=1,

D5=lkkz (D3, D2D1, D4, D3D1, D2D2)=lkkz (3, 21, 1, 31, 22)=4.

A Dn sorozat elemeit egyre nagyobb n-ekre különösebb nehézség nélkül kiszámíthatjuk. Ezt többen meg is tették, és azt a meglepő tényt fedezték fel, hogy a Dn sorozat periódikus n72-re 12 hosszúságú periódussal. A következő táblázatban a Dn értéket 12 hosszúságú sorokba tördelve mutatjuk be, az utolsó sor ismétlődik, az adja a periódust.
n0123 456789 1011
001231 432142 6
124127 143214 67
244128 547218 67
364123 147218 27
484128 147214 27
6041281 472186 7
724128 147218 27
844128 147218 27

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 En. Az En számokat az előzőekben leírtakhoz hasonlóan számíthatjuk ki. Például E0=0, E1=0 (mivel egy pont esetén is Kezdő veszít), E2=1, E3=1, E4=2 és például

E6=lkkz (E4, E3E1, E2E2)=lkkz (2, 10, 11)=3.

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

n 0 5 10 15 20 25 30
0 00112 03110 33224 05223 30113 02110 4527
34 40112 03110 33224 45523 30113 02110 4537
68 48112 03110 33224 45593 30113 02110 4537
102 48112 03110 33224 45593 30113 02110 4537

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 .A1A2A3... sorozathoz tartozó oktális játék a következő. Ha az Ak0 "számjegy" kettes számrendszerbeli alakja éppen 2a+2b+..., 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=21+20, 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=22+21+20, í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=20); 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=22+20); 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=22+21). 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 2k darab (k1) hetes szaerepel, a Grundy-számok 36.2k-tól kezdve 6.2k 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

Három játékot Java applet formájában beprogramoztunk. Ezeket a kedves Olvasó a számítógép ellen játszhatja. A játékok közül csak az első kettő szerepel a cikkben, de a harmadik játék nyerő stratégiáját is meg lehet találni a Grundy-számozás segítségével.

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.