SÖVÉNYVÁGÓ JÁTÉKOK Radnai Ágnes
Témavezet®: Király Tamás Operációkutatás Tanszék
Eötvös Loránd Tudományegyetem
Szeretnék köszönetet mondani témavezet®mnek,
Király Tamásnak,
aki készségesen
mesélt mindenr®l a témaválasztásnál, utat mutatott a legnehezebb bizonyításoknál, és a legnagyobb oda gyeléssel javította a pontatlanságokat, hogy a játékokhoz ill® könnyed fogalmazás ne menjen a precizitás kárára. Köszönöm szépen!
1
Tartalomjegyzék
1. Bevezetés
4
1.1.
A kombinatorikus játékokról általában
. . . . . . . . . . . . . . . . . .
4
1.2.
Gráf-reprezentáció
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3.
A végességr®l
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.4.
Grundy számok és NIM
. . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.4.1.
NIM
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.4.2.
Grundy-számok . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
2. Zöld sövényvágás
12
2.1.
A zöld sövényvágás szabályai . . . . . . . . . . . . . . . . . . . . . . . .
13
2.2.
A zöld bambuszliget
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.3.
Az illesztési szabály . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.4.
Zöld erd®ben...
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.5.
Paritás szabály
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.6.
Zöld sövényvágás a kezdetek . . . . . . . . . . . . . . . . . . . . . . .
17
2.7.
Összehúzható! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.8.
Bambuszok a hídon . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.9.
A-A-B-B-A-B-B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.10. Felezünk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
2.11. Készen vagyunk!
30
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3. Partizán játékok és a piros-kék sövényvágás 3.1.
A partizán játékokról általában
3.2.
Mi lesz a Grundy-számokkal?
3.3.
Piros-kék sövényvágás
31
. . . . . . . . . . . . . . . . . . . . . .
31
. . . . . . . . . . . . . . . . . . . . . . .
32
. . . . . . . . . . . . . . . . . . . . . . . . . . .
35
3.4.
Kategorizáljunk! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.5.
Zéró? Több? Kevesebb?
. . . . . . . . . . . . . . . . . . . . . . . . . .
37
Mennyit ér a játék? . . . . . . . . . . . . . . . . . . . . . . . . .
37
3.5.1.
2
3.5.2.
Már a bambuszok sem egyszer¶ek!
. . . . . . . . . . . . . . . .
4. Piros-kék-zöld sövényvágás
38
39
4.1.
Nagyrészt zöld játékok
. . . . . . . . . . . . . . . . . . . . . . . . . . .
39
4.2.
A számegyenes-módszer megbukik . . . . . . . . . . . . . . . . . . . . .
40
3
1. Bevezetés Az elkövetkez® fejezetekben kombinatorikus játékokról lesz szó. A sakk, a go, a malom és több világhír¶ játék is idetartozik, bár ezeknél sokkal egyszer¶bb példákat fogunk tárgyalni. Szemben a stratégiai játékelmélettel, melyet ma közgazdaságtanban, biológiában, pszichológiában és egyéb területeken is alkalmaznak, a kombinatorikus játékokat inkább csak mint a matematika üde színfoltját lehet emlegetni. A játékok legjobb tulajdonságai: játékkal töltjük.
érdekesek, izgalmasak.
Gyerekkorunk nagy részét
Így mikor ugyanez matematikai köntösben el®kerül, egy-egy játék
kapcsán egészen egyértelm¶, mit szeretnénk: nyerni, majd pár játszma után egy jó stratégiát, s®t, egy biztos stratégiát a nyeréshez. Matematikai kérdéseket teszünk fel magunknak, még akkor is, ha amúgy a matematika nem része az életünknek, és ezeket minél jobban szeretnénk az adott pillanatban megválaszolni. Ha van olyan ötletünk, amivel mindenképp nyerünk, akkor tulajdonképpen megfejtettük a játékot. Onnantól valami bonyolultabbal ütjük el az id®t. A továbbiakban olyan játékokról lesz szó, melyeket egy általános iskolás gyermek is élvezettel játszhat, de mi betekintünk a játékok mögé, és állítások kimondásával, ezek részletes, gazdagon illusztrált indoklásaival haladunk el®re.
A lényegi gondolatokat, témákat, ötleteket, állításokat és bizonyításokat innen vettem:
Elwyn R. Berlekamp, John H. Conway, Richard K. Guy: Winning ways for your mathematical plays Ez egy olyan könyv a játékokról, mely nagyszer¶en olvastatja magát, kreatív, és a bonyolultabb gondolatoknál f®ként az olvasó intuíciójára támaszkodik. Legf®bb feladatom az volt, hogy ezeket a gondolatokat, indoklásukkal együtt egyszer¶en követhet® lépésekre lebontsam úgy, hogy közben a fogalmazás módja átadjon valamennyit a könyv könnyed, vicces stílusából.
1.1. A kombinatorikus játékokról általában A kétszemélyes kombinatorikus játékok menete a következ®: két játékos van, A és B, mindketten tökéletesen értik a játékszabályokat. A gondolkozik, majd lép. B gondol-
4
kozik, majd B lép. A játék szempontjából lényegtelen, két lépés között mennyi id® telt el, tehát egy játszma lefolyását mint lépnek azaz
lépések
diszkrét játékot játszanak.
sorozatát írhatjuk le.
Állásból
állásba
Amennyiben a játékban a véletlenszer¶ségnek nincs szerepe, tehát A és B szabad akaratából dönt minden lépésnél,
determinisztikus játékról beszélünk.
Teljes információs a játék, ha a játékosok pontosan tudják, mi a játék állása.
A kár-
tyajátékoknál nem tudjuk biztosan, mi az állás, hiszen az függ a kézben lév® lapoktól.
Végállásnak nevezünk egy állást, ha ott a játéknak vége van, azaz a soron következ® játékos nem tud lépni.
A játék kimenetele háromféle lehet ekkor:
A nyer, B nyer,
vagy döntetlen a játszma. Ily módon egy végállás háromféle lehet. Az olyan játékot, melyben nincs döntetlen végállás, A játék
véges,
éles játéknak nevezzük.
ha tetsz®leges kezd®állásból véges sok lépésen belül véget ér, akármit
lépnek a játékosok.
Végesfokúnak pedig akkor hívjuk, ha minden állásból véges sok
állásba lehet lépni. Ha bármely állásból bármely állásba A pontosan ugyanazokat a lépéseket teheti meg,
szimmetrikusnak nevezzük. Ellenkez® esetben aszimmetrikus, vagy más néven partizán játékról beszélünk. A név azt sugallja, hogy a játék egyenl®tlen: mint B, a játékot
amit megtehet az egyik, azt a másik nem. A sakk, go, malom esetében mégsincs ez az érzetünk, pedig ezek is ilyen játékok! A partizán játékokat az utolsó fejezetben fogjuk vizsgálni. A fenti de níciókkal már pontosabb meghatározást, címet adhatunk a következ® fejezeteknek: teljes információs, diszkrét, kétszemélyes, éles, véges, végesfokú játékokkal fogunk foglalkozni, el®bb szót ejtünk a szimmetrikusakról: a NIM-r®l és az ún.
sö-
vényvágó játékról, majd a partizán játékokról, azon belül a partizán sövényvágásról is.
1.2. Gráf-reprezentáció Az elkövetkez®kben lesz olyan játék, amihez kavicsok, bambuszok, rajzok kellenek majd. De van az összesnek egy közös matematikai leírása, melyre a kés®bbiekben néha hivatkozni fogunk. Az egészet elképzelhetjük úgy, mintha egy irányított gráf csúcsain lépkednénk élek mentén: minden állásnak egy csúcsot feleltetünk meg, melyek közül
5
a kezd®állás, illetve a végállások kitüntetett szerepet kapnak, és egy adott csúcsból pontosan akkor vezet él egy másik csúcsba, ha az el®bbi csúcsnak megfelel® állásból megengedett lépni az utóbbi csúcs-állásba. Partizán játékok esetén az éleket megszínezzük pirossal és kékkel, hiszen itt különbséget teszünk a játékosok között, mikor egy lépés megengedettségér®l beszélünk. Egy játszma tehát tulajdonképpen egy, a gráfon megtett sétával azonosítható.
1.1. De níció.
A fenti gráfot a játék gráf-reprezentációjának fogjuk nevezni.
A gráf-reprezentáció nem összetévesztend® a játékok ún. játékgráfjával, amit a kés®bbi gráfos játékoknál fogunk használni.
1.2. De níció.
Egy meghatározott játék esetén játszmának nevezzük a játék egy lefo-
lyását. Ez ekvivalens egy, a gráf-reprezentációban kezd®állástól végállásig vezet® úttal.
1.3. A végességr®l Tegyük fel, hogy van egy véges, végesfokú játékunk. Mit is jelent ez a gráfra nézve? Azt, hogy egyrészt nincsen a kezd®állásból induló, végtelen hosszú séta, és minden csúcs végesfokú.
El®bbib®l következik, hogy a gráf aciklikus, mert ha körbe-körbe
haladhatnánk, végtelen sétát kapnánk. Így a séta helyett az út kifejezést is használhatjuk, hiszen egy játszma során kétszer ugyanazt az állást, gráf-értelemben ugyanazt a lépést nem tehetjük meg.
1.3. Állítás. Egy véges, végesfokú játék esetén a játszmák hosszának van fels® korlátja: tudunk olyan
N
természetes számot mondani, hogy a játék
N
lépésen belül véget ér.
A bizonyításhoz sokkal könnyebb egy er®sebb állítást belátni: Bármely állásból indulunk, az onnan induló játszmák hosszának van fels® korlátja. Innen indirekt bizonyítással adódik, hogy ha létezik olyan állás, melyb®l vezet tetsz®legesen hosszú út, akkor az abból kiinduló véges sok él közül az egyik biztosan olyan csúcsba vezet, melyre ez a tulajdonság örökl®dik: a kapott csúcsból is vezet tesz®leges hosszú út. Ezt a gondolatmenetet akármeddig, a végtelenségig is iterálhatjuk, így viszont végtelen hosszú úton mennénk végig, ami ellentmondás.
6
1.4. Grundy számok és NIM Ezt a témát most felületesen fogjuk elemezni, mintegy ismétlésképpen. Legegyszer¶bb játékunkat egy kupac kaviccsal játsszuk, és a szabály is egyszer¶: egy játékos egy lépésben egy vagy két kavicsot vehet el, továbbá az veszít, aki nem tud lépni. Jelen esetben tehát az nyer, aki az utolsó kavicsot elveszi. Mint minden játékot, ezt is lehet gráfként ábrázolni:
9
8
7
6
4
5
3
2
1
0
1. Ábra. Kiszínezzük az állásokat
El®ször felismerjük, hogy vannak állások, ahová szeretünk lépni, ezek legyenek a zöl-
dek. És vannak a pirosak, ahová nem szeretünk lépni. A színezést érdemes a végállásból visszafelé haladva elvégezni, és két dologra ügyelni közben: zöldr®l csak pirosra léphessünk, és minden pirosról tudjunk zöldre lépni. A színezett ábrával a nyer® stratégia pofonegyszer¶, és persze 100 százalék biztonságot ad, ha mi választhatjuk meg, kit illessen meg a kezdés joga: ellenfelünket, ha zöldr®l indulunk, bennünket, ha pirosról.
1.4.1. NIM A NIM szabálya, így játszása sem sokkal bonyolultabb az el®z®nél, egy nyer® stratégiához azaz a jól játszáshoz azonban sokkal többet kell gondolkodni. Kezdésként néhány kupac kavicsot teszünk az asztalra, majd minden lépésben kiválasztunk egy kupacot, és abból valamennyi kavicsot, de legalább egyet elveszünk. Az nyer, aki az utolsó kavicsot veszi el. Felmerülhet a kérdés, hogy minek bajlódunk még a stratégiákkal, mikor a színezés-módszerrel már mindent tudunk. A NIM-állásokat is színezhetjük, de sajnos el®fordulhat, hogy egy nagyobb csata el®tt napokig színeznünk kell. Egykupacos játékunkban gyorsan felfedeztünk egy szabályosságot piros, piros, zöld, piros, piros, zöld, stb. , de itt ez nem megy olyan könnyen.
7
A játék megértéséhez egy másik játékot fogunk elemezni: Néhány sorban pénzérméket helyezünk el, fejjel vagy írással felfelé. Egy lépés abból áll, hogy a soron következ® játékos kiválaszt egy sort, melyben legalább egy érme szerepel írással felfelé, és a következ®t teheti: egy írást mindenképp megfordít, és a t®le jobbra lev® érmék közül azokat fordítja meg, amelyeket akarja. Ha nincs több írás, végállásban vagyunk.
2. Ábra. Az érme-fordítós játék egy lépése
Két fontos dolgot állapíthatunk meg a játékkal kapcsolatban:
1.4. Megjegyzés.
A nyer® stratégia az, ha minden oszlopban páros számú fejjel felfelé
lev® érmét hagyunk magunk után. Könnyen ellen®rizhet®, hogy ez mindig megléphet®, és az ellenfél ezt mindig elrontja lépéseivel.
1.5. Megjegyzés.
Amennyiben úgy tekintünk a játékra, hogy a fejre, mint 0-ra, ill.
az írásra mint 1-re gondolunk, a játékot így is megfogalmazhatjuk:
leírunk néhány
számot kettes számrendszerben, és felváltva kiválasztunk egy számot, azt csökkentjük legalább 1-gyel, úgy, hogy nemnegatív egész számot kapjunk, és a maradékot felírjuk kettes számrendszerben az eredeti szám helyére.
8
1.6. De níció.
Két, vagy több szám NIM-összegén azt a számot értjük, melyet úgy
kapunk, hogy maradék-átvitel nélkül összeadjuk ®ket kettes-számrendszerben. Az összeg egy helyiértékén 1-es áll, ha páratlan sokszor áll egyes az összeadandó számok azonos helyértékén, 0 akkor, ha páros sokszor. A NIM-összeadást így jelöljük:
a ⊕ b = c,
pl.:
5⊕3=6 Ez ugyanaz, mint a bitenkénti összeg, két változó esetén a programozásban használt bitenkénti kizáró vagy (XOR) m¶velettel azonos.
1.7. Megjegyzés.
Zöldre színezzük a NIM játék azon állásait, melyben az egyes kupa-
cokban lev® kavicsok számának NIM-összege 0. Minden más állás piros. Akár így is fogalmazhatunk: néhány ku-
= 6
pac kaviccsal játszunk, egy játékos egy lé-
= 13
pésben kiválaszt egy kupacot és abból valamennyi kavicsot elvesz, legalább egyet.
= 4
Az nyer, aki az utolsó kavicsot elveszi. Ez
= 1
pedig nem más, mint a NIM. Lássuk tehát
=
a NIM nyer® stratégiáját: a számokat ket-
= 14
tes számrendszerben felírva, minden helyiértéken páros számú 1-es kell, hogy álljon.
3. Ábra. NIM, érmék helyett számjegyekkel
1.4.2. Grundy-számok Most kisebb kitér® után azt a gondolatmenetet folytatjuk, hogy zöldre, illetve pirosra színeztük az állásokat ez egy kupac kavicsos játékunkban. A Grundy-számozás a zöldpiros színezés továbbfejlesztése. Minden állást megcímkézünk egy egész számmal:
1.8. De níció.
Egy állás Grundy-száma a legkisebb olyan nemnegatív egész szám, ami
nem fordul el® azon állások Grundy-számai között, ahová az adott állásból lépni lehet. Ehhez persze kell a jól de niáltság , hogy ezt meg lehet csinálni, és ez egyértelm¶. De ez könnyen látható, ha gyelembe vesszük, hogy egy játékot reprezentáló gráf csak aciklikus lehet, így van topologikus sorrendje.
9
Ha az utolsóval kezdve (ami nyilván
végállás..) egyesével visszafelé haladva címkézzük meg az állásokat, egy jó és egyértelm¶ Grundy-számozást kapunk. A Grundy-számozás, mint rekurzív m¶velet indokolja, hogy látszólag egy fogalom bevezetéséhez magát a fogalmat használtuk fel. Nézzük a fenti példában az egyes állások Grundy-számait:
0
2
1
0
2
1
0
2
1
0
9
8
7
6
5
4
3
2
1
0
4. Ábra. Példa Grundy-számozásra
A színezés tehát a Grundy-számok egy gyenge változata: a zöld szín¶ek a 0 címkét kapják, míg a pirosak a pozitív egész számok valamelyikét.
1.9. De níció. Egy játék Grundy-számán a kezd®állásának Grundy-számát értjük. G
játék esetén
Γ(G)-vel
Ezt
fogjuk a továbbiakban jelölni.
Mi van akkor, ha nem tudunk dönteni kétféle játék között, mert a partnerünk mást szeretne játszani, mint mi? Természetesen még mindig a szimmetrikus, kombinatorikus játékok berkein belül vagyunk. mindkét játékot játsszuk egyszerre!
Lehet egy egyezményes alternatíva:
El®készítjük a kezd®állást mindkét játékban, és
mindenki dönthet, hogy a saját lépése címén az egyik, vagy a másik játékban végez-e el egy lépést. Logikus lenne, ha azt mondanánk, az nyer, aki valamelyik játékban nyer, de most ragaszkodjunk az általánosabb az veszít, aki nem tud lépni elvhez, és ennek megfelel®en mindegy, hogy az ellenfél nyert az egyik játékban, ha a másikban még van lépés és nyerhetünk. Tehát
1.10. De níció.
az nyer, aki utoljára nyer!
Két játék összegén a következ® játékot értjük: legyen a két játék gráf-
G1 = (V1 , E1 ) és G2 = (V2 , E2 ). Ekkor az összeg játék gráfjában a halmaza V1 × V2 , azaz rendezett párok halmaza. Kezd®állás lesz az a rendezett
reprezentációja csúcsok
pár, melynek elemei külön-külön kezd®állások, végállás(ok) az(ok), mely(ek)nek elemei végállások. Két rendezett pár között akkor vezet él, ha vagy az els®, vagy a második
10
elemük megegyezik, míg a másik elemek között eredetileg vezetett él:
((x, y), (w, z)) ∈ E1+2 ⇔ (x = w ∧ (y, z) ∈ E2 ∨ y = z ∧ (x, w) ∈ E1 )
1.11. Tétel. Két játék összegében egy állás Grundy-száma a két külön játékállás Grundyszámának NIM-összege. (Biz. nélkül)
1.12. Következmény.
Két játék összegének a Grundy-száma a két játék Grundy-
számának NIM-összege. Ebben a pillanatban kétféleképpen is megkaptuk a NIM játék nyer® stratégiáját: a pénzérmés analógia már elég volt ahhoz, hogy megfejtsük, de most már gondolhatunk úgy is rá, mint játékok összegére:
n
kupac
n
játék!
Az összeadott játékok egy-
kupacosak, és önmagukban nem sok értelmük van: a kezd® mindig nyer, ugyanis itt annyit vesz el a kupacból, amennyit akar.
Itt viszont ahány kavicsból áll a kupac,
annyi a Grundy-szám. Buta játékunk tehát nagyon is sok értelmet nyer, ha többször hozzáadjuk önmagához!
11
2. Zöld sövényvágás
5. Ábra. Zöld sövényvágás
12
2.1. A zöld sövényvágás szabályai 2.1. De níció. Vegyünk egy G = (V, E) irányítatlan gráfot, és egy F ⊂ V úgy, hogy
G
minden komponensében legyen
F -beli
csúcs. A játék menete a következ®:
a játékosok felváltva vesznek el egy-egy élt a gráfból. Ha valamely
x ∈ / F
és
x-b®l
nem vezet út
F -beli
csúcshalmazt
csúcsba, akkor
x-et
x
és minden
csúcsra igaz, hogy
x-b®l
kiinduló élt
törlünk azonnal. Így egy él elvételével akár több is törl®dhet a halmazból. Az veszít, aki nem tud lépni. Ez a sövényvágó játék.
6. Ábra. Felváltva veszünk el éleket
A fenti de níció persze pontosan az, amit egy sövényvágó játéktól elvárunk: Adott egy sövény-gráf, melynek bizonyos csúcsai a földön vannak, és a sövény minden eleme össze van kötve a földdel.
Egy lépésben pontosan egy élt törölni kell.
Ami ezután
a földhöz nem kapcsolódik, az leesik, így szintén törl®dik a gráfból. Az nyer, aki az utolsó élt veszi el.
2.2. A zöld bambuszliget A zöld bambuszligetben n®nek a legegyszer¶bb gráfok: olyan erd® ez, melyben 2 a maximális fokszám.
13
7. Ábra. Zöld bambuszliget
Az els® felismerés a játékkal kapcsolatban az, hogy ha a bambuszokat párba állíthatjuk úgy, hogy egyforma hosszú (izomorf ) bambuszok kerüljenek egy párba, akkor a kezd® veszít, mert a második játékos minden lépésre az adott él megfelel®jével válaszol. Ha nincsenek párok, akkor is gyorsan tudunk dönteni, hogy kezdjünk-e, vagy átadjuk a lehet®séget, ugyanis...
2.2. Megjegyzés.
...megintcsak NIM-et játszunk!
A bambuszok számát megfeleltethetjük a kupacok számának, az egyes bambuszok hosszát (éleinek számát) a megfelel® kupacban lev® kavicsok számának. Világos, hogy innent®l a lépések is kölcsönösen megfeleltethet®ek egymásnak: egy 5-hosszú bambusz alulról negyedik élét levágni ugyanaz, mint egy 5 kavicsból álló kupacból két kavicsot elvenni. A nyerési feltétel: elvenni az utolsó bambuszdarabot, illetve kavicsot.
14
8. Ábra. Tulajdonképpen NIM-et játszunk
=
=
9. Ábra. Így a NIM-összeadás megint m¶ködik
2.3. Az illesztési szabály Az illesztési szabály egy könnyen látható és átgondolható, a továbbiakban nélkülözhetetlen állítást mond ki:
2.3. Állítás.
Legyen
G
egy tetsz®leges sövényvágó játék gráfja,
H
és
H0
pedig további
játékgráfok, melyeknek összesen egy-egy csúcsa ér a földhöz és Grundy-számuk egyenl®: Γ(H) = Γ(H 0 ). G egy tetsz®leges x csúcsára illesztve H -t, illetve H 0 -t, két új játékgráfot
15
ragaszthatunk össze magunknak.
Az illesztési szabály a következ®:
a kapott játékok
Grundy-száma megegyezik.
2.4. Megjegyzés.
Ha
A
és
B
játékokra a
egyszer¶bb a játékok összegére ezt belátni:
Γ(A) = Γ(B) állítást akarjuk igazolni, néha Γ(A + B) = 0. Két játék összege pedig ebben
az esetben nem más, mint a két játékgráf egymás mellé rajzolása. Most az összegjátékra fogjuk belátni, hogy Grundy-száma 0, tehát a kezd® nem nyerhet, ha a másik játékos a megfelel® lépéseket teszi meg. A fenti állítás bizonyítása nem nehéz: A
H x
G
második játékos nyer® stratégiáját kell
H'
meghatározni.
x
Ha az els® játékos
vesz el: mi elvesszük az él párját.
G
leesik,
x
G-b®l Ha x
párja is le fog, innent®l egyértel-
m¶ a gy®zelem. Tegyük fel, hogy a másik H -ból vett el! Ekkor H és H 0 maradékának különbözik a Grundy száma.
Ve-
gyünk el egy élt úgy, hogy újra egyenl® 10. Ábra. Illesztési szabály
legyen!
Világos, hogy a végállapotba is
csak a második játékos érhet el így. Az illesztési szabály legfontosabb következménye: tetsz®leges olyan
x
G
játékgráfnak vegyük
csúcsát, mely két komponenst köt össze, azaz elvágó csúcs!
Csak az egyik
komponens érintkezzen a földdel. Ekkor a leveg®ben lev® komponenst kicserélhetjük tetsz®leges, azonos Grundy-számú gráfra, legegyszer¶bb esetben egy bambuszra.
2.4. Zöld erd®ben... A zöld bambuszokat a NIM után gyorsan kiismertük.
Nézzük, mi történik, ha egy
egész erd®t vágunk ki!
2.5. De níció.
Egy fagráfot, melynek egy csúcsa van a földön, zöld erd® játéknak
nevezünk. A földön lév® csúcsot akár több csúcsnak is vehetjük, így ténylegesen egy erd®t kapunk. fogalmazhattunk volna így is:
egy erd® gráf minden komponensének pontosan egy
csúcsa legyen a földön.
16
2.6. Megjegyzés. Az illesztési szabály miatt az erd®b®l bambuszokat csinálhatunk anélkül, hogy a Grundy-szám változna. Ez
azt
jelenti,
hogy
bármely
erd®nek
1 2=3
könnyen meghatározhatjuk mostantól a
4 5=1
Grundy-számát!
~ ~
2.5. Paritás szabály
~ ~
A paritás szabály egy apró észrevétel, mely hasznos lesz, mikor az illesztési sza-
11. Ábra. Fából bambusz
bályt sorozatosan fogjuk alkalmazni. Mi-
az illesztési szabállyal
kor kett®, vagy több bambusz egy pontból indul, azokat helyettesíthetjük egy bambusszal. Az új bambusz hosszának paritását pedig az fogja meghatározni, hogy eredetileg hány darab páratlan bambusz volt az elágazásnál. Ez a NIM összeg de níciójából könnyen ellen®rizhet®:
2.7. Állítás.
Egy elágazás, vagy akár egy egész erd® bambuszosítása során az élek
számának paritása nem változik.
2.8. Következmény.
Ha egy zöld erd®vágásnál páratlan sok élt számlálunk, ragasz-
kodnunk kell a kezdéshez!
2.6. Zöld sövényvágás a kezdetek A zöld sövényben megengedjük a köröket, többszörös éleket, hurokéleket. A zöld sövényvágás problémájához már nem használhatjuk közvetlenül az eddig látott NIM-összegre alapuló módszereket. Pár egyszer¶sítést viszont megengedhetünk, melyek a játék Grundy-számát nem fogják változtatni.
2.9. Megjegyzés.
A játék mit sem változik, ha a földön lév® csúcsokat összehúzzuk.
2.10. Megjegyzés.
A hurokéleket falevelekkel helyettesíthetjük.
17
2.11. De níció.
Adott
G
játékgráfban két különböz® csúcs,
x
és
y.
A két csúcs össze-
húzásával keletkezett gráfot úgy kapjuk, hogy a két csúcsot gráfelméleti értelemben össze-
x=y
húzzuk, azaz
csúcsba érkezik minden olyan él, ami eddig
x-be
vagy
y -ba
ment;
ezenkívül az összehúzott csúcson annyi új hurokélet de niálunk, ahányszoros él eredetileg a két csúcs között vezetett. Végeredményben tehát egy ugyanannyi él¶, eggyel kevesebb csúcsú gráfot kapunk.
2.7. Összehúzható! 2.12. Tétel.
Egy körsétán belül tetsz®legesen választott két csúcs összehúzásával a Grundy-szám változatlan marad. Indirekt fogunk bizonyítani. hogy
n
Legyen
n
olyan szám,
él¶ ellenpélda létezik, ennél kevesebb él¶ vi-
szont nem.
Az
n
x=y
él¶ ellenpéldák közül veszünk egy
olyat, mely csúcsainak száma minimális. Legyen ez a sövény-gráf
x
y
G.
Most belátunk pár dolgot
2.13. Lemma. G-ben
G-r®l:
nincsen olyan csúcspár, mely-
nek összehúzásával a Grundy-szám ne változna.
12. Ábra. Összehúzunk két csúcsot
G-ben van olyan csúcspár, mondjuk a és b csúcsok, melyek összehúzásával a Grundy-szám változik. De miért ne lehetne olyan c és d csúcs, melyek összehúzása nem okoz gondot? c és d közül legfeljebb egy megegyezhet a-val, vagy b-vel, ez az indoklást nem fogja elrontani. Ha mindkett® megegyezik, 0 úgy az állítás nyilvánvaló. c és d összehúzásával G gráfot kapunk. a és b összehúzásával ˜ gráfot, míg mindkét csúcspár összehúzásával G ˜ 0 gráfot kapjuk. Tudjuk azt, hogy G és G ˜ Grundy-száma különböz®, de azt is, hogy G ˜ és G ˜ 0 , valamint G0 és G ˜ 0 Grundy száma G
Tudjuk, hogy
megegyezik, hiszen az ellenpéldánál kisebb csúcs-számú gráfokról és csúcs-összehúzás 0 utáni változatukról van szó. Ekkor világos, hogy G és G Grundy-száma is különböz®, összességében tehát ezt kaptuk:
˜ = Γ(G ˜ 0) Γ(G) 6= Γ(G0 ) = Γ(G)
18
b
a
d c
G
a=b
~ / G' ~
/
~ ~
~ ~
a
b
~ G
c=d
d c
a=b
c=d
~ ~ ~G'
14. Ábra. Csak egy csúcs lehet a földön.
13. Ábra. Nincs olyan csúcspár, melynek összehúzásával a Grundy-szám ne változna.
Ezzel a lemmát beláttuk.
2.14. Lemma. G-nek egyetlen csúcsa lehet csak a földön. Ellenkez® esetben ugyanannyi él¶, de kevesebb csúcsú ellenpéldát találnánk, ha a földön lév® csúcsokat összehúznánk ugyanis ez a játék állásain, lépésein semmit nem változtatna.
2.15. Lemma. G nem rendelkezhet olyan a, b csúcsokkal, melyeket 3, vagy több élidegen út köt össze.
H -val az a és b csúcsok összehúzásával kapott gráfot. Γ(H) 6= Γ(G), így Γ(G + H) 6= 0, vagyis az indirekt feltevés szerint G + H -ban létezik jó kezd® lépés. G minden élének létezik megfelel®je H -ban és vi0 0 szont. Mi történik, ha a második játékos az elvett él megfelel®jével válaszol? G és H 0 0 gráfokat kapunk, melyekre igaz, hogy H -t úgy kaptuk G -b®l, hogy az a és b csúcsokat
Tegyük fel, hogy létezik ilyen csúcspár. Jelöljük
(melyek még mindig egy körséta csúcsai! legalább két élidegen út maradt..) összehúz0 0 0 tuk. G -nek továbbá n − 1 éle van. Így nem lehet ellenpélda, tehát Γ(G + H ) = 0. Így viszont mégsem nyerhet a kezd®játékos, hiszen most mutattuk meg, hogy a második játékosnak minden kezdésre van nyer® válasza. Ezzel az indirekt bizonyításunk indirekt részbizonyítását beláttuk.
G-ben
tehát nincs olyan pontpár, melyeket három élidegen
19
út köt össze.
2.16. Lemma. G-ben
nem lehet olyan kör, ami
nem érintkezik a földdel. Tegyük fel indirekt, hogy van ilyen Mi történik, ha
C
éleit elvágjuk?
C
G-ben! 0 Nevezzük G kör
C1
nek az élek elvágása után maradt darabot. A föl-
C
C2
dön maradt komponens ekkor legfeljebb egy csúcsát tartalmazhatja
C -nek.
a-t és b-t , akkor út G'-ben, mert egy
Ha kett®t tartalmazna
egyrészt
a
és
b
között vezet
csúcs van a földön, így egy 15. Ábra. Nincs olyan kör,
komponensben vannak. Továbbá vezetett köztük két út
C -ben
is:
ami nem érintkezik a földdel.
ez összesen három élidegen út,
ami a korábbiak miatt ellentmondás. Így csak egy
C -beli
x-nek.
0
csúcs maradt, nevezzük ezt
G-t leírhatjuk úgy is, hogy a G és a maradék legyen H gráfok összessége, közös pontjuk csak egy van, x. C kör is H része ekkor, természetesen. Ha 0 veszem csak H -t, mint játékot, úgy, hogy x van a földön, illetve H -t, melyet H -ból 0 kapok a C kör összehúzása után, megállapíthatjuk, hogy Γ(H) = Γ(H ), mivel H nem lehet ellenpélda. Az illesztési szabály miatt ekkor az eredeti G gráfban is igaz, hogy C Ezek alapján
összehúzásával a Grundy-szám nem változik. Így a lemmát igazoltuk. A fenti három lemmából a következ®, negyediket fogalmazhatjuk meg:
2.17. Lemma. G
csak egy kört tartal-
maz, ami földön lev® ponton is átmegy. Ha két kör is lenne a földön, ezek mind tartalmaznák a földön lev® csúcsot, más közös pontjuk viszont nem lehet, mert ekkor a föld és az említett pont között há-
16. Ábra. Végül egy hidat kaptunk!
rom út is vezetne. Így a két kör két külön komponens része, és ezeken (minthogy nem ellenpéldák) külön-külön összehúzhatnánk a köröket. Ez
G
esetében pedig nem lehetséges.
20
Nézzük tehát, hogyan nézhet ki
G!
Van benne egy kör,
C:
ez a földön át halad. A
földön lev® csúcsból két él indul a kör mentén.
2.18. Állítás.
Több él nem indul a földb®l.
Tegyük fel, hogy van harmadik, földb®l induló él.
G
nem állhat több, csak a földön
érintkez® komponensb®l, hiszen akkor a komponensek nem-ellenpéldák, így összegük sem lenne az. Így kell, hogy legyen olyan földb®l induló, érkez® út, mely
C
egy élét sem tartalmazza. A föld és
x
C
kör egy másik
x
csúcsába
között így három élidegen út
vezetne. Ez ellentmondás. Most megengedünk egy kis módosítást, pusztán azért, hogy
G-t
majd könnyebb le-
gyen lerajzolni: egy kör, melynek minden nem-földön-lev® csúcsából egy fa indulhat ki, melyet bambusszal helyettesíthetünk, ezt meg is tesszük. A földön lev® csúcs helyett kett®t fogunk rajzolni.
Egyszer¶ és szemléletes összegzését kapjuk így a fenti
lemmáknak:
2.19. Következmény. G tulajdonképpen egy híd, amin bambuszok vannak.
2.8. Bambuszok a hídon Most a kapott hídról mondunk ki állításokat:
2.20. Megjegyzés.
A hídról azt szeretnénk belátni, hogy összehúzható. Ez pontosan
azt jelenti, hogy ha a hídon lev® bambuszokat egyenként a híd mellé másoljuk, a kapott játék Grundy-száma a híd éleinek paritásától függ: 0, ha páros, illetve 1, ha páratlan sok élb®l áll.
2.21. De níció. G
b®vítésének fogjuk hívni a fenti módon, bambuszok hozzáadásával
nyert játékgráfot. Jele:
2.22. Lemma.
˜. G
A híd nem állhat páros sok élb®l, mert ekkor a híd összehúzható lenne.
Tegyük fel ugyanis indirekt, hogy páros sokból áll!
˜ -n G
játszva elég megmutatni, hogy
a második játékosnak van nyer® stratégiája. Mit tehet a kezd® játékos? Ha a hídból vesz el, páratlan Grundy-számú állásba lép, mert a kapott zöld erd® játéknak páratlan
21
sok páratlan komponense lesz. Ez mindenképpen rossz lépés, így nem éri meg elvenni a hídból.
A bambuszok fognak el®bb elfogyni ezt feltehetjük , majd a híd páros
számú éle: a bambuszokat páronként fogyasztva, majd a híd bontásánál mindenre a tükörképével válaszolva a második játékosnak van nyer® stratégiája:
Γ(G) = B1 ⊕ B2 ⊕ ... ⊕ Bk , ahol B1 , ..., Bk
k
a hídon lev®
˜ = 0. Γ(G)
Ebb®l
darab bambusz hossza. Tehát
a híd összehúzható.
2.23. Megjegyzés.
Most már feltehetjük, hogy páratlan sok híd-él van. Arra fogunk
törekedni, hogy belássuk:
˜ = 1. Γ(G)
2.24. Állítás. Nem tudunk olyat lépni G b®vítésében, hogy 1 Grundy-számú játékgráfot kapjunk. Ha a hídból veszünk el, egy páros élszámú erd®t kapunk: a paritás szabály miatt ennek a Grundy-száma páros.
Ha valamelyik bambuszból veszünk el, a bambusz párjával
ugyanezt kell tenni, és a maradék Grundy-száma 1 lesz! Ugyanis
G-nél
kisebb gráfról
beszélünk, bambusz-párokkal és összehúzott páratlan-híddal; és ha egy-egy lépés után 1 Grundy-számút kaptunk, a kezd® lépés után nem lehetett 1.
2.25. Megjegyzés.
Ha egy állásból egy lépés után a Grundy szám nem lehet 1, erede-
tileg 0 vagy 1 lehetett a Grundy-száma.
Elegend® tehát azt belátni, hogy tudunk egy következik, hogy nem 0, hanem 1 a Grundy-száma
G
~ G
17. Ábra.
G
22
b®vítése
jó
kezd®lépést!
b®vítésének.
Ebb®l már
2.9. A-A-B-B-A-B-B A híd éleire melyekr®l feltehetjük, hogy páratlan sokan vannak , bet¶ket,
B -ket
írunk. Balról jobbra haladva,
A-val
A-kat
és
kezdünk, majd a következ® szabály szerint
folytatjuk: Ha olyan csomóhoz érkezünk, melyb®l páratlan hosszú bambusz indul ki, akkor ugyanolyan bet¶vel folytatjuk, mint el®tte, ha pedig az adott csúcsból páros hosszú bambusz (vagy semmi sem) indul, váltunk: ha eddig
A
volt, most
B
jön és
viszont.
2.26. Lemma.
˜ -ben (Hídvágó-lemma) G
a kezd® játékosnak semmiképp se jó olyan
bet¶jel¶ élt elvenni, amib®l páros számú van, mert ekkor a kapott
H
játékra
Γ(H) ≡
2 (mod 4),
tehát nem jó kezd®lépésnek. Ha viszont a többi híd-élb®l vesz el ezekb®l 0 0 páratlan sok van , az így kapott H játékra Γ(H ) ≡ 0 (mod 4)
Bizonyítás:
A hídból bármely élt elvéve két fát
kapunk, amelyeknek már könnyen meghatározhatjuk a Grundy-számát.
Az els® fontos észrevé-
tel az, hogy a bambuszok teljes hossza helyett vehetjük csak a hossz maradékát szen
(mod 4):
hi-
A
Γ(H) meghatározásához veszem egy bambusz
B B A A B
A
hosszát, hozzáadok 1-et, NIM-hozzáadom a következ® bambusz hosszát, stb. Mivel az állítás csak a kettes számrendszerbeli utolsó két számjegyre vonatkozik, a többi teljesen mindegy, így egy 7
18. Ábra. A híd-éleket megbet¶zzük
hosszú bambusz helyett 3 hosszúval is számolhatok, egy 12 hosszúságú bambuszra akár úgy is tekinthetünk, mintha ott se lenne. Ez eddig szinte triviális, most viszont belátjuk, hogy
(mod 2)
is elég a bambuszok
hosszát nézni! Az állítást ebben a formában fogalmazzuk meg:
2.27. Állítás.
Ha egy
B
bambusz tetejér®l letörünk egy 2-hosszú utat, és ugyanennyit
letörünk a híd melletti másolatáról is,
Γ(H) (mod 4)
nem változik.
Képletek helyett inkább jöjjön egy szöveges indoklás:
A hidat elvágtuk valahol, és
maradt két fa. Az egyik ugyanolyan, mint edddig, a másik fát valahol két éllel meg0 rövidítettük, az eredeti B bambuszból egy B -t csináltunk. A fa Grundy-számát ebben a speciális esetben így számoljuk ki:
veszem a földt®l legtávolabbi bambusz
23
hosszát. Hozzáadok egyet. NIM-összeadom a következ® bambusz hosszával. Hozzáadok egyet. És így tovább. A paritás minden m¶veletnél ugyanaz, mintha az a két él nem is hiányozna. A kérdés az, hogy hogyan változik a második helyiérték? 1. Egy nem
B
bambusznál: Ha eddig változott, most is fog, ha nem, akkor pedig
nem. 2. Ha
B
bambusznál tartok: Ha eddig nem változott, most fog, és viszont.
3. Mikor épp 1-et adok hozzá: a második helyiérték változása csak az aktuális érték paritásától függ. A paritás pedig lépésenként is ugyanaz. Összességében ezt kaptuk: A 2-es helyiértéken lev® szám 1-gyel többször, vagy 1-gyel kevesebbszer változik, mint az eredeti hídnál. Igen ám, de élt! Így ez a szám
(mod 4)
B
párjából is letörtünk két
mégiscsak ugyanaz.
Most már indokolt a lemma bizonyításához a következ®t felhasználni:
2.28. Következmény. Ha a lemma igaz 0- és 1-hosszú bambuszokra, akkor akármilyen hosszúakra, így
˜ -re G
is alkalmazhatjuk.
A lemmát a híd éleinek számára alkalmazott teljes indukcióval bizonyítjuk.
Els® lépés: Ha a hídnak csak egy éle van, akkor egy bet¶b®l csak úgy lehet páros sok, hogy
0
van bel®le. Ezekre a nem létez® élekre az állítás nyilván igaz. Ha azt az egy élt elvesszük, akkor vége van a játéknak, a maradék Grundy-száma 0.
Azt továbbra is feltesszük, hogy páratlan sok híd-él van, és így az indukciós lépéseknél is mindig kettesével lépünk. Be fogjuk tehát látni, hogy ha páratlan számra igaz a lemma, akkor
Indukciós lépés:
Vegyünk egy
2k + 1-re
2k + 1
hosszú
2k − 1-ig
minden
is.
H
hidat, maximum 1-hosszú bambu-
szokkal! Vágjunk el egy híd-élt! Ha a kapott két fából az egyik tartalmaz is, akkor nyilván tartalmazni fog egymás melletti
A -B
A
és
B
élt
élpárt is. A két él között nincs
bambusz, ezt a bet¶zés szabályából tudjuk. Ha ezt a 2-hosszú utat kivágjuk, majd két
24
végénél összeragasztjuk, az újonnan kapott fa Grundy-számának els® bitje megmarad, a második pedig megváltozik, hiszen két egymást követ® hozzáadok egyet-lépés marad ki a fent tárgyalt mechanizmusból.
Ha a kapott gráfban elvágunk egy olyan
bet¶jel¶ híd-élt, amilyen bet¶b®l páratlan sok van, a maradék gráf Grundy-száma 4gyel osztható az indukciós feltevés szerint. De az eredeti gráfban pont ebb®l a bet¶b®l 0 volt páros sok, és az eredeti gráf második bitje pont változott. Így Γ(G ) ≡ 2 (mod 4) teljesül.
A
B
B
B A
A
A
B
~ ~A
B
A
A A B
B
A A
A
A
A
B
B
B
B
B B
19. Ábra. Az élek kivágása nem rontja el a bet¶zést
2.29. Állítás.
Az
A-B
út kivágásával a bet¶zési szabályt nem rontjuk el, azonos bet¶k
között páratlan, míg különböz®ek között páros hosszú bambusz lesz továbbra is. Ez az ábráról könnyen leolvasható.
2.30. Megjegyzés.
Ha esetleg a híd lábánál húzunk össze két élt, a földre kerülhet egy
bambusz. Ezt a bambuszt viszont a párjával együtt eltüntethetjük, és a Grundy-szám sem változik így. Mi van akkor, ha a kapott két fa közül egyikben sincs két különböz® bet¶jel¶ él? Ekkor nem m¶ködik a fenti indukciós bizonyítás. Nézzük, mit állíthatunk a homogén bet¶jel¶ fákról! Egy fa esetében kétféleképpen számolhatjuk ki a Grundy-számot:
25
1. Ugyanolyan bet¶s élt vágtunk el, mint a fa bet¶i: Ekkor egy
n-hosszú
2n.
Grundy-száma
2. Az elvágott él és a fa éleinek bet¶je különböz®: A fa Grundy-száma éle, egyébként
híddarab
1,
ha van
0.
Tudjuk továbbá, hogy a fák híd-éleinek paritása megegyezik. (Mert híd-élekb®l összesen páros sok marad egy elvágása után.) A homogén fák esetét most bontsuk részesetekre! 1.
Földön lev® híd-élt vágtunk el, ennek bet¶je megegyezik a többiével. A maradék fának
2x
híd-éle van, Grundy-száma
bet¶b®l páratlan sok volt.
4x,
ez 4-gyel osztható, az adott
Páros sok bambusz-másolat van, mert bármely két
szomszédos híd-él között van egy bambusz. Ezek a bambusz-másolatok kiejtik egymást, így nem kell foglalkozni velük, Grundy-számuk
0.
Így
4x-et
kapunk,
ami igazolja az állítást erre az esetre. 2.
Földön lev® híd-élt vágtunk el, ennek bet¶je különbözik a többit®l. maradék fának
2x
híd-éle van, Grundy-száma
1.
A
Páratlan sok bambusz-másolat
van, mert egy helyen nincs bambusz a hídon, a másolatok Grundy-száma
1, mert
a párok kiejtik egymást és egy marad. Egy darab olyan bet¶s él volt, amilyet elvágtunk, így 4-gyel osztható számot szeretnénk kapni: valóban:
1 ⊕ 1 = 0,
így
ezt igazoltuk. A további négy esetben feltesszük, hogy nem földön lev® híd-élt vágtunk el. Ez azért fontos, mert ekkor egy fa-maradékról feltehetjük, hogy van éle. 3.
A két fából az egyikben csak A, másikban csak B élek vannak, és mindkett®ben páratlan híd-él van. Ekkor a két fa híd-él-hossza legyen 2x+1 és
2y + 1.
Grundy-száma
(4x + 2) ⊕ 1,
vagy
(4y + 2) ⊕ 1,
így
4z + 3 alakú.
Ehhez
még hozzá-NIM-adjuk a bambusz-másolatok Grundy-számát, ami 0, ha páros sok van bel®lük, és 1, ha páratlan. Összesen páros sok hely van bambuszoknak, és egyszer váltunk a híd bet¶zése során, ott nincs bambusz.
Tehát páratlan sok
bambusz-másolat van.
(4z + 3) ⊕ 1 ≡ 2 (mod 4) és olyat vettünk el, tehát beláttuk.
26
amib®l páros sok van. Ezt az esetet
4.
A két fából az egyikben csak A, másikban csak B élek vannak, és mindkett®ben páros híd-él van. Ekkor a két fa híd-él-hossza legyen 2x és 2y. Grundy-száma
4x ⊕ 1,
4y ⊕ 1,
vagy
így
4z + 1
alakú. Ehhez hozzá-NIM-adjuk a
bambusz-másolatok Grundy-számát, ami 1, mert páratlan sok van.
0 (mod 4)
(4z +1)⊕1 ≡
és olyat vettünk el, amib®l páratlan sok van, az állítás tehát most is
igaz. 5.
A híd bet¶i mind azonosak.
A két fa híd-él-hossza legyen
x
és
y.
Grundy-
2x ⊕ 2y = 2(x ⊕ y). Bambusz-másolatból páros sok van, így azokat ignorálhatjuk. x és y paritása megegyezik: x ⊕ y ≡ 0 (mod 2), ebb®l 2-vel szorozva, azaz a biteket balra tolva ezt kapjuk: 2(x ⊕ y) ≡ 0 (mod 4). Páratlan sok azonos száma
bet¶b®l vettünk el egyet, és a várt eredményt kaptuk. 6.
Csak az elvett él különbözött a többit®l.
Mindkét fa Grundy-száma
1,
és
összesen páros sok bambusz-másolat van, mivel két helyen hiányzik a hídról a bambusz.
1 ⊕ 1 = 0,
tehát
4-gyel
osztható. Ami jó, hiszen egyetlen ilyen bet¶s
híd-él volt. Most tehát egy indukcióval beláttuk az állítást úgy, hogy a végén külön vizsgáltuk azokat az eseteket, ahol a fák homogének bet¶k szempontjából, itt nem is használtuk az indukciós feltevést. A hídvágó-lemmát tehát beláttuk. Még mindig az a célunk, hogy megmutassuk, van olyan él, melyet elvéve a kapott gráf Grundy-száma 0 lesz. Most már tudjuk, hogy...
2.31. Következmény.
...nem éri meg olyan bet¶jel¶ élt elvenni, amelyb®l páros sok
van.
2.10. Felezünk 2.32. Lemma.
(Felez® lemma)
Ha most
gráfelméleti értelemben
összehúzzuk az
olyan híd-éleket, melyek bet¶jéb®l páros sok van, az így egymás mellé került bambuszok hosszát NIM-összeadjuk, és ennek megfelel®en a kapott összeg hosszúságúval helyettesítjük (illesztési szabály), és ezután minden bambusz hosszát elfelezzük (lefelé kerekítve, ha páratlan volt), akkor a Grundy-szám is feleannyi lesz, mint volt.
27
Bizonyítás:
Tegyük fel, hogy
A
jel¶ híd-élb®l van páratlan sok. Nevezzük redukált
gráfnak azt, amit a bambuszok felezésével és a
B
jel¶ élek összehúzásával kapunk.
Vegyünk egy adott A-jel¶ élt, és töröljük ki az eredeti gráfból: ekkor több fa keletkezik, ezek közül válasszunk egyet. Ha a redukált gráfból töröljük ki ugyanazt az élt, akkor ott is keletkezik egy ennek megfelel® fa, amit nevezzünk redukált fának. Azt látjuk be, hogy a redukált fa Grundy-száma az eredeti fa Grundy-számának a fele, lefele kerekítve.
2.33. Megjegyzés.
Ha egy híd-él összehúzása során egy hídon lev® bambusz a földre
kerül, akkor azt onnantól gyelmen kívül hagyhatjuk a másolatával együtt. Így földre kerül® bambuszokkal a továbbiakban nem fogunk számolni.
2.34. Állítás.
Ha a fa egy A-jel¶ éle feletti részfát nézzük, akkor annak a Grundy-
száma páratlan, egy B-jel¶ él feletti részfa Grundy-száma meg mindig páros.
Bizonyítás:
A fában legfelül lév® híd-élre igaz az állítás, mert
tehát ha a legfels® híd-él
A
B
jel¶ élt töröltünk,
jel¶, akkor a fában felette lév® rész két
bambusz, tehát páratlan. Hasonlóan, ha a legfels® és
A
A
jel¶ él közti
B jel¶, akkor a felette lév® rész egy A
közti bambusz, tehát páros. Most már csak azt kell belátni, hogy ez a tulajdonság
örökl®dik a híd-éleken egyesével lefelé haladva. Egy ilyen lefelé lépésnél a Grundy-szám a következ®képpen változik: el®bb hozzáadunk 1-et, majd NIM-hozzáadunk egy másik számot: ez a szám páros, ha a következ® bet¶ különbözik az el®z®t®l, egyébként pedig páratlan. Ez pedig pont azt jelenti, hogy ha bet¶t váltunk, paritást is váltunk.
2.35. Állítás. Ha az egyik fában egy híd-él feletti részfát nézünk, akkor a redukált fában az ennek megfelel® részfa Grundy-száma az eredeti fele, lefelé kerekítve. Az el®z® bizonyítás mintájára fogjuk ezt is belátni fentr®l lefelé. A legfels® híd-élre ez nyilván igaz: a legfelül lev® bambuszt megfeleztük, lefelé kerekítve, ez ugyanígy igaz a Grundy-számra is. A lefelé lépésnél szét kell választanunk pár esetet aszerint, hogy milyen bet¶jel¶ élr®l milyenre lépünk tovább. Az el®z®, paritásról szóló szabályt már tudjuk, most megmutatjuk, hogy ez az állítás is örökl®dik. Nézzük tehát, milyen élr®l milyenre léphetünk!
1.
A → B:
A jel¶ él feletti részfa Grundy-száma páratlan, legyen 2k + 1, A redukált változaté pedig k . Most hozzávesszük az A élt, ez k + 1. Az A és B élek között van egy eredetileg páros, 2l hosszú bambusz, ennek a redukált Ekkor az
28
l a hossza. Egyrészt tehát az eredeti fában a lépés után a Grundy-szám (2k + 1) + 1 ⊕ 2l = 2(k + 1 ⊕ l), másrészt a redukált fában k + 1 ⊕ l, pont a fele. fában
2.
A → A: Megint páratlan, 2k + 1 Grundy-számú részfából indulunk, ami redukálva k . Az eredeti fában hozzáadunk 1-et, majd egy páratlan-hosszú bambuszt: (2k + 2) ⊕ (2l + 1) = (2k + 2 ⊕ 2l) + 1 = 2(k + 1 ⊕ l) + 1, a redukált fában pedig miután 1-et hozzáadtunk, l-et NIM-adunk hozzá: k + 1 ⊕ l -et kapunk, amit szerettünk volna.
3.
B → B:
Páros,
2k ,
illetve redukálva
k
a Grundy-számmal indulunk, de most
csak az eredeti fában adunk hozzá egyet! Majd természetesen a páratlan hosszú bambuszt is hozzávesszük: fában egyszer¶en 4.
k⊕l
(2k + 1) ⊕ (2l + 1) = 2k ⊕ 2l = 2(k ⊕ l).
A redukált
lesz a Grundy-szám, az eredeti fele.
B → A: Induló Grundy-szám: 2k , és k . Az eredeti fában (2k + 1) ⊕ 2l = 2(k ⊕ l) + 1 számot kapunk, a redukáltban k ⊕ l lesz, mivel itt sem adunk hozzá 1-et.
2l
B
A
l
2k+1
A k
2k+2
2l
l
2l+1
2l+1
2k+1
k+1
A
(k) l
A
2l+1 2k+2
B 2k 2l
k
l
A 2k+1
2l
l
B 2k B
2l+1
2k+1
A
A k l
l
k+1
(k) l
k
20. Ábra. A Grundy-szám felez®dik
Már csak egy lépés van hátra: az utolsó él
A
él,
2k + 1
az utolsó, földön lev® híd-élen is lelépünk.
Grundy-számú részfa van felette, az éllel együtt
29
Ha ez
2k + 2
a
teljes fa Grundy-száma. A redukált fában pedig legalul,
2k -ból 2k + 1
lesz az eredeti, míg marad
k -ból k + 1 lesz. Ha pedig B él van a k a redukált fában, ahol ugye az élt
összehúztuk. A felezésr®l szóló lemma bizonyításának lezárásaként már csak az kell, hogy mindez
G
b®vítésére is igaz. A részfákra már láttuk, a bambuszokra külön-külön nyilván igaz, hiszen itt a hossz és a Grundy-szám teljesen ugyanaz.
Úgy gondoljunk a felezésre,
hogy az adott szám kettes számrendszerbeli alakjában egy helyiértékkel jobbra toljuk a számjegyeket, az utolsót törölve. Világos, hogy Grundy-számok összegének a fele így a Grundy-számok felének összege lesz. A felez® lemmát tehát beláttuk.
2.11. Készen vagyunk! Most már birtokában vagyunk mindennek ahhoz, hogy a körösszehúzási tételt belássuk. Ellenpéldánkról,
G
G-r®l beláttuk, hogy egy híd, és azt is, hogy ha találunk jó kezd®lépést
b®vítésében, akkor készen vagyunk.
Van ilyen a híd-élek között!
a Grundy-szám. fel, hogy egy jó
A
Olyan élt keresünk, aminek elvételével 0 lesz
e
A
élt vettünk el, legyen ez egy
Visszafelé gondolkodunk: tegyük
jel¶ él! Nyilván ekkor páratlan sok
híd-él van, ezt a hídvágó-lemmából tudjuk. Most a felez® lemmában tanult módon
húzzuk össze a
B
éleket, és felezzük el a bambuszokat!
lett. Mi történik, ha redukáljuk csoportba fog tartozni
A A
e?
G-t
A Grundy-szám
0
volt,
0
is
és aztán újrabet¶zzük? Az új bet¶zésben melyik
Páratlan, vagy páros sok lesz az új bet¶jéb®l?
A B B B A
(A)
B
A
(A)
C
(A)
D
C
30
e-t
(D)
C C
21. Ábra. Hogyan találjuk meg
A válasz az, hogy csak páratlan lehet, hiszen
(A) (A)
E
e-t?
kivágva a redukált hídból
0
lesz
a maradék Grundy-száma!
Megint a hídvágó-lemmát alkalmaztuk.
Ha a hidat és
a bambuszokat annyiszor redukáljuk, amennyiszer csak lehet, végül egy egy-él¶ hidat kapunk, aminek a Grundy-száma 1. Ezt az élt, ami minden redukálás után megmaradt, nevezzük el az eredeti hídban
e
e-nek,
és most már a felez® lemma miatt tudjuk, hogy
elvételével az eredeti b®vített hidas játékban is
így
e jó kezd®lépés.
Innen pedig tudjuk, hogy
0
Grundy-számú játékállást kapunk,
G összehúzható, ami ellentmond indirekt
feltevésünknek.
3. Partizán játékok és a piros-kék sövényvágás
22. Ábra. Piros-kék sövényvágás: egy lehetséges kezd®állás
3.1. A partizán játékokról általában A partizán játékokról még a bevezetésben szó esett. Itt az egyik játékos nem ugyanazokat a lépéseket teheti meg, mint a másik. Amennyiben a játékot, mint állás-csúcsok között lépés-éleken át megtett sétát értelmezzük egy irányított gráfban, úgy a partizán játék gráf-reprezentációjában az éleket kékkel és pirossal színezhetjük, és az egyik játékos csak a kék, míg a másik csak a piros éleken haladhat. Milyenek ezek a játékok? Bonyolultabbak? Mindenképpen. A szimmetrikus játékot, mint egy speciális esetet is felfoghatjuk itt. Mik azok az alapvet® feltevéseink, amelyek
31
változtak?
A szimmetrikus játékokban ugyanazt léphetjük, mint az ellenfél, ugyan-
azokat az állásokat szeretjük, mint az ellenfél. Na de mi van akkor, ha mi szeretünk valahova lépni, ahová ® nem? Azaz: ha van olyan állás, ahova bármelyikünk lép, én nyerhetek? Ennek bemutatására egyszer¶ példa a sakk. Ha megkérdeznénk valakit, vajon a sakkban ugyanazt lépheti-e az egyik, mint a másik, azt mondhatná: persze, így igazságos, egyenl® a játék.
Pedig egy olyan lépés sincs, amit mindketten léphetnek! Hiszen az
egyikük csak a világos, másik pedig csak a sötét bábukat mozdíthatja. Ha pedig van 16 világos bábu a táblán és egy sötét király, majdnem mindegy, ki lépett utoljára, ebbe az állásba valószín¶leg csak a világos játékos szeret lépni. Eddig két kategóriába soroltunk egy játékot: aki kezd, az nyer, vagy aki kezd, az veszít. Most mivel nem mindegy, hogy melyik játékosként ülünk le játszani, a kategorizálás némiképp módosul:
3.1. Megjegyzés.
Egy partizán játékot négy kategóriába sorolhatunk:
1. Az nyer, aki kezd. 2. Az veszít, aki kezd. 3. A piros játékos nyer. 4. A kék játékos nyer. Valójában a játék minden állását ezen kategóriák közé sorolhatjuk, majd a kezd®állás határozza meg a játék kategóriáját.
3.2. Mi lesz a Grundy-számokkal? A legels® példajátékunk egy partizán módosulatát játsszuk: van egy kupac kavicsunk, melyb®l a két játékos felváltva vesz el valamennyit: 1. A piros játékos egyet, vagy kett®t, 2. A kék játékos egyet, vagy hármat.
32
Ennek a játéknak a gráf-reprezentációját fogjuk vizsgálni.
9
8
7
6
4
5
3
2
1
0
23. Ábra. Így léphetünk. De hogyan színezzünk?
Van-e értelme most is Grundy-számokkal operálni? Els® ránézésre nem sok, hiszen egy állásról még azt sem tudjuk eldönteni, hogy piros-e vagy zöld, hiszen az attól függ, hogy a Piros, vagy a Kék játékos szempontjából nézzük.
Az ötlet az, hogy minden
állás kapjon két színt! Egyet az egyik játékos szemszögéb®l, egyet a másikéból.
9
8
7
6
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
24. Ábra. Kiszíneztük az állásokat
Ha több, mint 3 kaviccsal játszunk, a színezés eredményét lényegében így lehet összefoglalni: mindig a pirosnak van nyer® stratégiája. A stratégia pedig tulajdonképpen az, hogy soha ne lépjünk pirosként olyat, hogy 1 vagy 3 kavics maradjon! Ezt minden esetben tudjuk teljesíteni, és így már biztosítva van a nyerés. Eddig egy állás színét nem tudtuk eldönteni, hiszen az függött attól, hogy ki lépett oda. Most nézzük meg a fenti ábrát! Megdupláztuk az állásokat, és egy kicsit bonyolultabb gráfot kaptunk, viszont erre már igaz, hogy az állás meghatározza azt is, hogy ki lépett oda. Ki is színeztük, és ezt kaptuk! A gráf irányítatlan verziója páros. Mit is jelent ez? Hogy egy játszma során folyamatosan az alsó és a fels® sor között lépkedünk, ahogy azt az ábrán is látjuk. Felelevenítjük egy játszma menetét: feltehetjük, hogy piros kezd, ami azt jelenti, hogy választ egy, a
33
kezd®állásból kiinduló piros élt, és abba az állásba lép, amelybe az él mutat. Majd kék jön, a jelenlegi állásból kiinduló kék élt választ (ha nincs ilyen, kék veszít), stb. Ez a színezetlen és a színes ábrán is érvényes, és nyilván a két gráfon játszani gyakorlatilag
ugyanaz. A különbség annyi, hogy a színes ábrán csak kék él indul egy állásból, ha a kék következik, és ugyanez igaz pirosra is.
3.2. Megjegyzés.
Mi értelme volt akkor kiszínezni az éleket is? Hiszen semmit sem
determinál. A válasz az, hogy
semmi!
Ugyanis éppen most csináltunk partizán játékból szimmet-
rikus játékot! Persze, ha a játékot, mint szimmetrikus játékot elmesélnénk valakinek, az valahogy így hangozna: Van egy kupac kavicsunk, és egy pénzérménk, kezdetben írással felfelé. Egy lépés a következ®: ha az érmén az írás van felül, 1-et vagy 2-t elveszünk a kupacból és megfordítjuk az érmét.
Ha fej van felül, 1-et vagy 3-at veszünk el a kupacból és
megfordítjuk az érmét. Az veszít, aki nem tud lépni.
3.3. Megjegyzés.
A partizán játékok tehát els® látásra tágabb fogalmat takarnak,
melynek a szimmetrikus játékok speciális esetei. Most azonban a Grundy-számozhatóság érdekében azt is megmutattuk, hogy fordítva is lehet látni a dolgokat: egy partizán játékot leírhatunk speciális szimmetrikus játékként is. Ugyanezen elv alapján tehát nemcsak színezni, de akár Grundy-számozni is tudunk:
1 1 1 1 1 1 2 2 1 0 9
8
7
6
5
4
3
2
1
0
9
8
7
6
5
4
3
2
1
0
0 0 0 0 0 0 0 0 1 0 25. Ábra. Grundy-számozás
34
Ez azt jelenti, hogy egy partizán játék eredeti gráf-reprezentációján a csúcsok Grundyszámozása helyett
Grundy-számpározást csinálunk!
(1, 0) (1, 0)
9
(1, 0)
8
7
(1, 0)
6
(1, 0)
(1, 0)
4
5
(2, 0)
3
(2, 0)
2
(1, 1)
1
(0, 0)
0
26. Ábra. Grundy-számpározás
(., 0) Grundy-számpárú vagyunk, a (0, .) alakú számpá-
Ha megvannak a számpárok, így játsszunk: ha pirossal vagyunk, állásba lépjünk, ahol
.
akármi lehet. Ha pedig kékkel
rokkal ellátott állásokba kell lépni. Ha pedig erre nincs lehet®ségünk, akkor sajnos az ellenfelünknek van nyer® stratégiája.
3.3. Piros-kék sövényvágás A piros-kék sövényvágás mint a neve is mutatja abban különbözik a zöld sövényvágástól, hogy itt az élek pirosak, vagy kékek. Az egyik játékos csak kék, míg a másik csak piros élt törölhet. Az veszít, aki nem tud lépni, tehát nincs már a pályán az ® színéb®l él. Nézzünk pár egyszer¶bb esetet! 1. A legegyszer¶bb, mikor csak egy szín van..
nyilvánvaló, hogy ekkor csak az
nyerhet, akinek a színéb®l áll a gráf. 2. Szimmetrikus játék: mi van akkor, ha két egyforma alakzatunk van, egyik piros, másik kék? Ekkor az veszít, aki kezd, ez könnyen meggondolható. 3. Kvázi-szimmetrikus játék: két alakzat van, melyekre a következ® érvényes: a két alakzat egyforma, tehát minden élnek van egy párja a másik alakzatban. Ekkor az él és a párja különböz® szín¶.
Ekkor a másodiknak lép® játékos mindig el
35
tudja érni, hogy nyerjen: bármit lép a kezd® játékos, ® mindig a törölt él párját veszi el a következ® lépésben. Így a második játékos minden lépése után kváziszimmetrikus állást kapunk.
27. Ábra. Egyszer¶bb esetek
3.4. De níció.
Zéró játéknak nevezünk egy játékot, vagy annak játékgráfját, ha igaz
az, hogy aki kezd benne, az veszít.
3.5. Megjegyzés.
A szimmetrikus és a kvázi-szimmetrikus játék tehát zéró-játék.
3.4. Kategorizáljunk! Mostanra már tudunk olyan piros-kék játékgráfot rajzolni, melyben a piros nyer, függetlenül attól, hogy ki kezd. Ilyen például az, ha egy darab piros él van. Hasonlóan, tudunk olyat is, ahol csak a kék nyerhet. Zéró játéknak neveztük azokat, ahol az veszít, aki kezd, és erre is láttunk már példát. Van azonban egy negyedik kategóriája a partizán játékoknak, amire még nem láttunk példát: az nyer, aki kezd. Vajon létezik ilyen sövény?
3.6. Állítás.
Nincs olyan piros-kék sövény, melyben mindig a kezd®nek van nyer®
stratégiája.
Bizonyítás:
Tegyük fel, hogy van egy ilyen játék! Mondjuk, hogy kékkel vagyunk és
mi kezdünk. Van egy nyer® stratégiánk, melyben az
A
él törlésével kezdünk. Innent®l
pedig ellenfelünk bármely lépésére van egy biztos válaszlépésünk. Mi van akkor, ha az ellenfelünk kezd? Ha úgy lépünk, mintha mi kezdtünk volna és úgy vesszük, mintha
36
az
A
él nem lenne ott, akkor játszhatjuk ugyanúgy a stratégiánkat, ráadásul van egy
plusz saját szín¶ élünk is. Egyetlen nehézsége lehet ennek a mintha játéknak: mit csináljunk, ha az ellenfél esetleg olyan élt vesz el, mely az ott?
Ekkor viszont nyer® állásba hozhatjuk magunkat:
A
él hiányában nem lenne
töröljük
A-t,
és az eredeti
terv szerint folytathatjuk a stratégiánkat. Így meg tudjuk verni az ellenfelet ebben az esetben is.
3.5. Zéró? Több? Kevesebb? Ha tehát nem zéró játékkal állunk szemben, csak olyan lehet egy játékgráf, hogy a kezd® személyét®l függetlenül eldönthet®, hogy ki fog nyerni. A játék tehát valakinek kedvez. Mondjuk a pirosnak jó ezt a játékot játszani. Feltehetjük a kérdést: mennyire jó a pirosnak? Ha a földre tennénk még egy kék élt, akkor is tudna nyerni? És ha még tízet, akkor is? Mennyi el®nnyel indul a piros játékos? Próbáljuk meg a játékokat egy számegyenesen elhelyezni!
28. Ábra. Játékgráfok a számegyenesen
3.5.1. Mennyit ér a játék? Egy játék számegyenesen elfoglalt helyét az fogja meghatározni, hogy a kék szemszögéb®l mennyit ér a játék. El®ször az olyan játékokat nézzük, ahol senki nem vághat el élt úgy, hogy az ellenfél színéb®l is leesik egy él.
Ez azt jelenti, hogy a piros, il-
letve a kék élek által meghatározott részgráf külön-külön is játékgráfot alkot, minden komponensének van csúcsa a földön. Nevezzük ezeket egyszer¶ játékoknak.
Egy egyszer¶ játék értéke
n − m,
ha egyrészt
játékgráfja.
37
n
darab kék és
m
darab piros élb®l áll a
Ezekre a játékgráfokra igaz az is, hogy ha egy játék értéke akkor
n
n < 0,
n > 0,
ahol
n
egész szám,
piros élt kell a játékgráf mellé a földre rakni, hogy zéró játékot kapjunk. Ha
akkor
n
3.7. Állítás.
darab kéket.
Az egyszer¶ játékokban a játékok összegének értéke pont a játékok érté-
kének összege. Ez triviális, hiszen mindegy, hogy a kék élek számából a pirosak számát külön-külön vonjuk ki, majd a különbségeket összeadjuk, vagy el®bb összeadjuk az azonos szín¶eket, és utána vesszük a különbségüket.
3.5.2. Már a bambuszok sem egyszer¶ek! Megpróbálunk elhelyezni a számegyenesen egy olyan játékot, amely nem egyszer¶, tehát a játékosok már
29. Ábra. 4-4: zéró játék!
ténylegesen keresztbe tehetnek egymásnak azzal, hogy saját szín¶ él elvágásával valamennyi lehullhat az ellenfél színéb®l is. A legegyszer¶bb ilyen játékgráf egy bambusz, aminek egy kék és egy piros éle van, legyen a kék a földön. Ezt a játékot a kék nyeri mindenképpen. Vagyis a számegyenesen mindenképp pozitív számot kap. De melyiket? Nézzük, hogy hány piros élt kell a játékgráf mellé rakni, hogy zéró játékot kapjunk! Tegyünk mellé egy pirosat. Ha a piros kezd, elveszi a fels® piros élt, majd a kék a sajátját, aztán megint a piros jön. És nyer. Ha pedig a kék kezd, levágja a nagyobb bambuszt és a piros elveszi a másikat. Megint a piros nyer. Hová tegyünk egy ilyen játékot a számegyenesen? szám...
legyen fél?
Ilyen er®vel
2/3
is lehetne.
0-nál nagyobb, de 1-nél kisebb De azt mondhatjuk, hogy ezt az
ismeretlen számú játékgráfot megduplázzuk, és két ilyen bambusz lesz a kezd®állás! Ekkor a kék nyer, akár kezd, akár nem.
De ha egy piros élt odateszünk harmadik
bambusznak, akkor zéró játékot kapunk! Tehát ha a játék értéke Így
x = 1/2.
38
x,
akkor
2x − 1 = 0.
1 2
1 -2
1
0
30. Ábra. Törtszám lett, így a leglogikusabb
Van ennek értelme? Ahhoz, hogy a nem egyszer¶ piros-kék sövényvágó játékoknak is értéket adhassunk, vannak alapvet® elvárásaink: minden gráf esetén ki tudjuk számolni ezt az értéket a fenti módon, egymás mellé másolással. A legfontosabb pedig az, hogy a játékok összegének értéke mindig az értékek összege legyen. Ezt a témát most nyitva hagyjuk, érdekességként..
4. Piros-kék-zöld sövényvágás Elérkeztünk a legbonyolultabb sövényvágó játékhoz: mindhárom eddigi szín szerepelhet a játékgráfunkban, azaz lehet egy él olyan, hogy csak az egyik, csak a másik, ill. mindkét játékos törölheti azt. Mivel a zöld sövényen jobban eligazodunk, így ezt használjuk majd kiindulási pontként, és el®ször azt vizsgáljuk, mi van, ha csak bizonyos szabályok szerint, korlátozott számban fordulnak el® piros és kék élek.
4.1. Nagyrészt zöld játékok Egy apró lépéssel eltávolodunk a csak zöld játéktól: pontosan egy kék él is legyen a játékban.
4.1. Állítás.
Ha pontosan egy kék él van, és a többi zöld, a kék játékosnak van nyer®
kezd®lépése.
39
A módszer a következ®: a kék kiszámítja a kék él nélküli maradék zöld játék Grundyszámát.
Ha ez 0, akkor elveszi a kék élt, és ezzel tulajdonképpen átadja a kezdés
lehet®ségét a megmaradt zöld sövényvágó játékban. Ha a Grundy-szám nem 0, akkor lejátszhatja a játékot úgy, mintha a kék él ott se lenne: hiszen a piros játékos nem nyúlhat kék élhez! A végén a kék játékos úgy nyer, hogy még egy kék él is maradhat, ha az eredetileg a földön volt. Az viszont nem biztos, hogy a kék mindenképpen nyer.
Ha a piros tud olyan kezd®lépést, mellyel
a kék él lehullik, és egyben a maradék zöldek Grundy-száma is 0 lesz, úgy a piros nyer.
4.2. A számegyenes-módszer megbukik A partizán játékok négy kategóriájában az aki kezd, az nyer típusú a piros-kék sövényvágásnál 31. Ábra. Egy kék él is van
nem szerepelt.
Most, hogy zöld élek is vannak,
egyszer¶en tudunk ilyet találni:
például minden
zöld, 0 Grundy-számú játékgráf. El tudjuk-e helyezni ezeket a háromszín¶ játékgráfokat is a számegyenesen? Az aki kezd, az nyer típusú játékok jelenléte már rossz érzést kelthet bennünk ezzel kapcsolatban, hiszen az sem a pirosnak, sem a kéknek nem kedvez igazán, zéró játéknak mondanánk, de azért mégsem ugyanaz. Sajnos a válasz az, hogy az eddig mágikusan m¶köd® számegyenes-ötletnek itt nem vesszük hasznát.
Azért nem, mert a játékok
összegével szembeni elvárásaink nem teljesülnek. Álljon itt egy konkrét példa:
40
32. Ábra. Virágok a számegyenesen?
Az els® játékban csak egy virág van. Nyilván az nyer, aki kezd, és a teljes virágot letépi. A második ábrán már nem ilyen egyszer¶ a stratégia. Ha valaki elvágja az egyik virág szárát, ellenfele elvágja a másikét és gy®z. Tehát semmiképp nem szabad elvágni zöld élt. Ha viszont felváltva veszik el a szirmokat, akkor el®ször a piros játékos kényszerül arra, hogy zöld élt vágjon el. Így mindenképpen a kék nyer, akár kezd, akár nem. Ha az els® játék értéke
0,
akkor kétszer nulla már nagyobb, mint nulla...? Ezeket a játékokat
már nem ilyen könny¶ besorolni.
41
