Wegneemspellen (1 stapel)

Dit gaat over spellen waarin twee spelers om de beurt, volgens bepaalde regels, een aantal fiches weg mogen nemen van een stapel. Wie de laatste legale zet doet heeft gewonnen.
Voor dit soort spellen definieren we het Grundy-getal g. (naar Grundy  (1939) die dit introduceerde). Een eindpositie, dat is een positie waaruit geen zet meer mogelijk is, heeft g = 0.  Voor elke andere positie bepalen we het g-getal als volgt: 

• Het doel van het spel is nu om voor je tegenstander een positie met g-getal 0 neer te leggen.
• Hij moet dan voor jou altijd een positie met g > 0 wegleggen. Hij kan niet wéér een g = 0 positie maken, want een positie die uit een andere volgt heeft altijd een andere g.
• Van die nieuwe positie maak jij weer een g = 0 positie. Dat kan gegarandeerd want g = 0 zit zeker in de opvolgposities want als dat niet zo was, dan had deze postie zelf wel g = 0 gehad.
•  En dat gaat zo alsmaar door totdat je een eindpositie voor hem weglegt.

spel 1. Je mag  per keer 1,2 of 3 fiches wegnemen

De eindpostie met 0 fiches heeft g₀ = 0
Uit de positie met 1 fiche kan alleen 0 bereikt worden, G = {0}, dus positie 1 heeft g₁ = 1
Uit de positie met 2 fiches kunnen 1 en 0 bereikt worden; G = {0,1},  dus positie 2 heeft g₂ = 2
Uit de positie met 3 fiches kunnen 2, 1 en 0 bereikt worden; G = {0,1,2}, dus positie 3 heeft g₃ = 3
Uit de positie met 4 fiches kunnen 3,2 en 1 bereikt worden; G = {1,2,3}, dus positie 4 heeft g₄ = 0
Uit de positie met 5 fiches kunnen 4,3 en 2 bereikt worden; G = {2,3,0}, dus positie 5 heeft g₅ = 1
enz....

Zo vinden we automatisch de winnende posities:  die met  0, 4, 8, 12,.... fiches.
De winnende taktiek is dus: Ga zo snel mogelijk naar een 4-voud toe en blijf viervouden maken. Dat kan gegarandeerd, want als je tegenstander 1,2 of 3 fiches weghaalt, dan haal jij er 3,2,of 1 weg. Uiteindelijk zul je de laatste fiche weghalen.

ALGEMENERE AANPAK

Laten we de verzameling die je weg mag halen S noemen.
In het net genoemde voorbeeldspel was dus  S = {1,2,3}

spel 2.  S = {1,3,4}     (dus per keer mag je 1, 3 of 4 fiches weghalen)

De g-waarden worden nu als volgt:

De g-waarden zijn periodiek met periode 7.
Onze taktiek wordt: bereken n (mod 7) en maak daar 2 of 0 van.
Als er bijvoorbeeld 39 fiches liggen, dan bereken je 39(mod 7) = 4  en om g = 0 te bereiken moet je dus 4 of 2 fiches weghalen.

Is de g-rij altijd periodiek? Dat zou mooi zijn!
Jazeker, mits de verzameling S eindig is. Dus dan is er altijd een winnende strategie te vinden.

Een paar speciale gevallen:

1.    S = {1, p}  heeft de  g-serie:
            Als p oneven is:  g(n) = 01010101.....
            Als p even is :  g(n) = 010101...012  waarbij er 0,5p paren 01 aan de 2 vooraf gaan.

2.    S = {1,2,..., p}  dan is  g(n) = 012...p  dus de nieuwe taktiek wordt: kies als winnende positie een veelvoud van p + 1

Varianten

Een paar varianten maken de winnende speelwijze minder makkelijk te vinden en zijn dus eigenlijk veel interessanter:

variant 1.    Neem S oneindig groot.

variant 2.    Maak S afhankelijk van n

variant 3.    Maak S afhankelijk van het aantal dat de vorige speler nam.

Weer een andere variant....

Het is natuurlijk ook erg leuk om verschil in de fiches te maken!
Laten we ze bijvoorbeeld nummeren van 1 tot en met n.
Om het helemaal wiskundig te maken stellen we als regel, dat je één nummer per keer moet kiezen om weg te nemen, maar dat dan automatisch alle nummers die daar een deler van zijn óók verdwijnen!

Een mogelijke variant met de nummers 1 tm 20 staat hieronder:

Spelers rood en blauw wijzen om de beurt een felgekleurd nummer aan, en ook alle lichtgekleurde delers daarvan verdwijnen. De laatste zet van rood was duidelijk slim: er blijven nog 6 getallen over die geen delers onderling meer hebben. Dus zullen vanaf nu rood en blauw om de beurt een nummer weghalen, dus rood het laatste nummer! De brandende vraag is natuurlijk: "Is er een winnende strategie, en hoe hangt die van n af?" Het is heel eenvoudig te bewijzen dat de eerste speler altijd kan winnen, ongeacht van n. Het bewijs daarvan gaat zó: Stel dat we een tweede variant van het spel spelen, met alle getallen tot en met n, maar zonder het getal 1. Als speler 1 deze tweede variant altijd zou kunnen winnen, dan kan hij de eerste óók winnen door op dezelfde manier te spelen, immers 1 verdwijnt altijd de eerste keer. Als speler 2 deze tweede variant altijd zou kunnen winnen, dan kan speler 1 de eerste variant winnen, namelijk door alleen het getal 1 weg te halen. Dan gaan we immers daarna variant 2 spelen met speler 2 aan de beurt! Mooi bewijsje hé? We weten nu zeker dat er voor elke n een winnende variant voor speler 1 is, maar zonder die variant te kennen!!!!
EN NU OM GELD!!!!!
Ik daag je uit het volgende eenvoudige wegneemspelletje met mij te spelen. We leggen een groot aantal muntjes van 5, 2 en 1 eurocent in een lange rij voor ons op tafel. Om de beurt pakken wij een munt weg, maar het moet steeds één van de buitenste twee zijn. Bewijs dat bij een even aantal munten de eerste speler meestal het meeste geld zal winnen (in ieder geval NOOIT zal verliezen) en dat bij een oneven aantal stenen de tweede speler meestal het meeste geld zal krijgen. In bovenstaande rij (even aantal) kun je bijvoorbeeld altijd winnen als je begint met de munt van twee eurocent rechts! Hoe zit dat? De oplossing is kinderlijk eenvoudig. Laten we de munten om, en om groen en blauw kleuren: De eerste speler kan er nu altijd voor kiezen om óf alle blauwe munten te pakken, óf alle groene munten. Als hij bijvoorbeeld alle groene munten wil, dan pakt hij de rechter groene munt. Dat laat twee blauwe munten over voor de ander. Die moet dus een blauwe pakken, en daardoor komt er weer een groene vrij. En dat gaat zo alsmaar door. De blauwe munten zijn samen 5 + 1 + 5 + 1 + 2 + 1 + 2 = 17 eurocent De groenen zijn samen 2 + 1 + 2 + 5 + 2 + 5 + 2 = 19 eurocent. Je kunt dus altijd winnen door de groenen te pakken:  begin met de munt van 2 eurocent! Bij een oneven aantal kan speler 1 eerst een munt van de rand wegnemen (de kleur daarvan ligt vast) en daarna kan speler 2 de taktiek hierboven gebruiken. Speler 1 zal alleen winnen als de waarde van zijn eerstgepakte munt meer is dan het verschil tussen de overblijvende groene en blauwe rijen. Zelfs al heeft hij een munt méér!