Het afbreken van trappen

De opgave van de najaarsprijsvraag 2002 vroeg naar de strategie van het afbreken van trappen, en meer algemeen van partieel geordende verzamelingen, of aanverwante spelen.

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.

De prijsvraag

Bestudeer het spel "trapafbreken" of (een speciaal geval van) de gegeneraliseerde versie. Welke standen zijn gewonnen voor de speler aan zet? Welke zijn verloren? Is er een strategie?

Een rij

Een rij ter lengte 1 is een P-positie:
0
de speler aan zet moet de laatste steen pakken en heeft verloren. Een langere rij is een N-positie:
0+XXXXX
de speler aan zet pakt de steen gemerkt met + en wint.

Twee rijen

Een trap die twee rijen hoog is, is een P-positie precies wanneer de twee rijen 1 in lengte verschillen. Dus
XXXX
0XXXX
is 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.

Symmetrie

Trappen van de vorm
X
X
X
0XXX
zijn P-posities: op elke zet is er een gespiegeld antwoord.

Ook zijn spiegelbeelden van P-posities weer P-posities, dus

X
XX
XX
XX
0X
is een P-positie.

Kleine standen

Nu wordt het moeilijker - een systeem is niet zo makkelijk aan te geven, maar kleine standen kunnen gemakkelijk met de hand geanalyseerd worden. Om te laten zien dat een stand een P-positie is, moeten we laten zien dat we op elke zet van de tegenstander een verpletterend antwoord weten. Als we op zet a antwoord b geven. dan zijn de posities a en b onvergelijkbaar. (Want als a rechtsboven b ligt dan ontstaat na a,b dezelfde situatie als na b, en de tegenstander had kunnen winnen.) Maar dat betekent dat op zet b het antwoord a verpletterend is. Dus de figuur wordt overdekt met paren die we dezelfde letter kunnen geven.

a
b
cd
0cabd
Deze 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
0cbx
met 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
0fbdgch
levert 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
0gbdhxyf
met 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.)

Drie rijen

Laat [p,q,r] de stand aangeven die ontstaat door in een oneindig hoge en brede trap (het eerste kwadrant, met coordinaten gegeven door niet-negatieve gehele getallen) de vier zetten (p,0), (q,1), (r,2), (0,3) te doen. Dit is de stand met drie rijen - de onderste ter lengte p, de middelste ter lengte min(p,q), de bovenste ter lengte min(p,q,r).

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 7
Bijvoorbeeld: 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).

Rechthoeken

Een rechthoek die niet 1-bij-1 is, is een N-positie. Pak de top: misschien is dat de winnende zet. En als dat niet de winnende zet is, dan heeft de tegenstander een winnend antwoord x. Maar dan doen wij bij nader inzien zelf x.


De opgave vroeg nog:

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.


Grafen

De opgave ging verder met een grafen-variant: We kunnen van V ook alle punten en sommige paren nemen, en vinden dan een graaf. Het spel wordt: pak om de beurt iets weg, hetzij een kant, hetzij een punt samen met alle kanten op dat punt. Wie de laatste zet doet wint. Is er voor dit spel een theorie op te stellen?

Bomen en bossen

Een bos is een P-positie dan en slechts dan als het aantal punten en het aantal samenhangscomponenten beiden even zijn.

(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.)

Involuties

Stel dat de graaf G een graaf een automorfisme van orde 2 heeft met de eigenschap dat als x,y door het automorfisme verwisseld worden dan zijn x,y niet verbonden. Dan is G een P-positie dan en slechts dan als de graaf op de vaste punten en kanten onder het automorfisme een P-positie is.

Volledige grafen

De volledige graaf Kn is een P-positie dan en slechts dan als n een 3-voud is.

(Als n = 1 (mod 3), haal een punt weg. Als n = 2 (mod 3), haal een kant weg, en gebruik de involutie-stelling.)


Gerichte grafen

Trapafbreken is een speciaal geval van spelen op een partieel geordende verzameling, en spelen op een graaf is dat ook. Equivalent met het spel op een partieel geordende verzameling is "grafen snoeien" op een gerichte graaf.

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.

Serie- en Parallelschakeling

Een graaf heet opvolger van een andere graaf als hij in één zet bereikbaar is uit die andere graaf.

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.