Eerst de terminologie. De standen waar een speler naar streeft zijn die waarin zijn tegenstander verliest, want dan wint hij zelf. Sommige inzenders noemen zulke standen "gewonnen", andere inzenders noemen ze "verloren". Om misverstand te vermijden noemen we ze P-posities. Dit is de Engelse terminologie: "previous player wins". Hier is de P van Previous, en ook van Positive. De andere standen heten dan N-posities, met N van Next of Negative.
0de speler aan zet moet de laatste steen pakken en heeft verloren. Een langere rij is een N-positie:
0+XXXXXde speler aan zet pakt de steen gemerkt met + en wint.
XXXX 0XXXXis een P-positie. Dit is makkelijk in te zien: vanuit zo'n positie voeren alle mogelijke zetten naar een positie waarbij beide rijen evenlang zijn of minstens twee in lengte verschillen, en dan is er altijd een antwoord dat het lengteverschil weer 1 maakt. Tenslotte belanden we in de situatie met rijen ter lengte 0 en 1, en dat is een P-positie.
X X X 0XXXzijn P-posities: op elke zet is er een gespiegeld antwoord.
Ook zijn spiegelbeelden van P-posities weer P-posities, dus
X XX XX XX 0Xis een P-positie.
a b cd 0cabdDeze figuur laat zien dat de trap met rijlengten 1,1,2,5 een P-positie is: op een zet met een label volgt de andere zet met datzelfde label, en in alle gevallen ontstaat een situatie waarvan al bekend is dat het een P-positie is.
Paren mogen overlappen: het kan zijn dat a het goede antwoord is op zowel b als c. Omgekeerd kun je dan bij een zet op a kiezen of je b of c speelt - beide zijn goed. Bijvoorbeeld in
ab cd 0cbxmet x=a,d blijkt dat de trap met rijlengten 2,2,4 een P-positie is. Gespiegeld is dit de trap met rijlengten 1,1,3,3. Op deze manier blijken 2,3,5 en 2,4,6 en 2,5,7 en 2,6,8 en 3,3,6 en 3,4,7 en 3,5,5 en 4,4,8 en 4,7,7 en 1,1,2,5 en 1,1,3,3 en 1,1,4,6 en 2,2,2,6 en 2,2,3,7 en 2,2,4,8 en 2,2,5,5 en 2,3,3,5 en 2,3,5,7 en 2,3,6,8 en 2,4,4,7 en 2,4,5,8 alle P-posities. Inderdaad:
ab cdea fghe 0fbdgchlevert het bewijs voor 2,4,4,7 gegeven 3,4,7 en 1,1,3,3 en 2,2,3,7 en 2,2,2,6. En
ab cdef ghija 0gbdhxyfmet x=e,j en y=c,i levert het bewijs voor 2,4,5,8.
(Al deze standen zijn door inzenders als P-posities geidentificeerd.)
Het is duidelijk dat er bij gegeven q,r precies één p is waarvoor [p,q,r] een P-positie is. Want: er kunnen niet twee verschillende p zijn waarvoor [p,q,r] een P-positie is: als p' > p dan kun je met een enkele zet van [p',q,r] naar [p,q,r] gaan. En er moet er tenminste één zijn, want anders is er op elk van de oneindig vele mogelijkheden voor p telkens een antwoord op de tweede of derde rij, en die zijn eindig, dus 1 antwoord zou bij meer dan 1 waarde van p voorkomen, tegenspraak. Dus er is een functie f(q,r) zo dat [p,q,r] een P-positie is dan en slechts dan als p = f(q,r).
De zetten mogelijk vanuit [p,q,r] zijn die naar [p',q,r] of [p,q',r] of [p,q,r'] met p' < p en q' < q en r' < r (waarbij de nieuwe toestand niet gelijk is aan de oude). Dit laat zien dat f(q,r) gegeven wordt door een eenvoudige recurrente betrekking: Als r > q dan is f(q,r) = f(q,q). Als f(q-1,r) < q dan is f(q,r) = f(q-1,r). In de overige gevallen is f(q,r) het kleinste positieve gehele getal dat niet onder de waarden f(q',r) en f(q,r') met q' < q en r' < r voorkomt.
Een klein tabelletje, met q horizontaal en r verticaal:
4 | 1 3 4 6 8 9 10 7 3 | 1 3 4 6 7 5 5 5 2 | 1 3 4 5 6 7 8 9 1 | 1 3 2 2 2 2 2 2 0 | 1 2 3 4 5 6 7 8 -------------------- | 0 1 2 3 4 5 6 7Bijvoorbeeld: f(7,4) = 7 zegt dat 4,7,7 een P-positie is, wat we boven ook al zagen.
Er zijn interessante vermoedens over het asymptotisch gedrag van f(q,q).
Wie wint er bij de 4 bij oneindig rechthoek?
Een zet op de onderste rij maakt er een eindige rechthoek van en is dus fataal. Een rij op de tweede rij maakt er een positie van met oneindig lange bodemrij en eindige rest, en we zagen boven al dat er dan een unieke zet op de bodem is om er een P-positie van te maken. Maar de zet (0,2) heeft groot succes: hij geeft de tegenstander een 2 bij oneindig rechthoek, en de tegenstander verliest.
(Iets preciezer: laten er v punten en c componenten zijn. Het Grundy getal of Nim getal van een bos is (i) 0 als v en c beide even, (ii) 1 als v en c beide oneven, (iii) 2 als v even en c oneven, en (iv) 3 als v oneven en c even.)
Als deze bewering eenmaal geformuleerd is, is het bewijs triviaal. (Pak je een kant dan verandert de pariteit van c (terwijl v gelijk blijft). Pak je een punt dan verandert de pariteit van v, terwijl c met d-1 toeneemt als dat punt graad d had. Als v oneven is is er zeker een punt met even graad d. En als c even is terwijl v oneven is, dan is er een kant en ook een blad en kunnen we het blad pakken.)
(Als n = 1 (mod 3), haal een punt weg. Als n = 2 (mod 3), haal een kant weg, en gebruik de involutie-stelling.)
Het spel gaat als volgt: Op een gerichte graaf bestaat een zet uit het weghalen van een punt x samen met alle punten die vanuit x bereikbaar zijn. Wie niet kan zetten (omdat de graaf geen punten heeft) verliest.
Op het eerste gezicht is dit iets algemener dan het spel op de partieel geordende verzameling omdat bij de correspondentie tussen x < y en x -> y de antisymmetrie niet behouden blijft, maar dat is schijn: sterke samenhangscomponenten van de gerichte graaf kunnen tot een enkel punt worden samengetrokken zonder dat er aan het spel iets verandert. Dus, we mogen de graaf acyclisch nemen, en nu zijn beide gezichtpunten equivalent.
Van een graaf houden we bij wat zijn Grundygetal is, en bovendien wat de Grundygetallen zijn van al zijn opvolgers. (Het Grundygetal van een stand is het kleinste niet-negatieve gehele getal dat geen Grundygetal is van een opvolger. Een stand is een P-positie precies als het Grundygetal 0 is.)
Als de gerichte graaf de vereniging is van een twee disjuncte grafen - "parallelschakeling" - dan heeft deze graaf een Grundygetal dat de XOR (Nim-som) is van de Grundygetallen van beide, en zijn opvolgers zijn de disjuncte vereniging van de ene graaf en een opvolger van de ander en hebben dus ook bekende Grundygetallen.
Als de gerichte graaf de "serieschakeling" is van twee andere: zeg G = A -> B, d.w.z. dat elk punt van B bereikbaar is vanuit elk punt van A, dan volgen de gegevens nodig voor G ook uit de gegevens van A en B: de opvolgers van A -> B zijn A' en A -> B' waarbij A' en B' opvolgers van A en B zijn, en het Grundygetal van A -> B volgt uit de Grundygetallen van alle A' en dat van B. Als volgt: laat B Grundygetal b hebben, dan is het Grundygetal van A -> B nummer b in de rij van niet-negatieve gehele getallen die geen Grundygetal van een A' zijn (tellend vanaf 0).
Bijvoorbeeld: als A gegevens 1{0,4,5,6,7} heeft, en B heeft gegevens 2{0,1,4,5,6} dan is de rij niet-negatieve gehele getallen die geen Grundygetal van een A' zijn 1,2,3,8,9,10,11,12,... en voor de A' vinden we {0,4,5,6,7} en voor A -> B' vinden we {1,2,9,10,11} zodat A -> B gegevens 3{0,1,2,4,5,6,7,9,10,11} heeft.
Dit algoritme volstaat om voor elke gerichte graaf die ontstaat uit een combinatie van serie- en parallelschakelingen het Grundygetal en dus ook de strategie te bepalen.