NIM binair

© h.hofstede (h.hofstede@hogeland.nl)

NIM.

Nim is een oud kroegspelletje waar het tweetallige stelsel in verscholen zit.

Zoals het hoort in een kroeg zijn de regels van het spel simpel:

Er liggen een willekeurig aantal stapeltjes (bijvoorbeeld 4) met elk een willekeurig aantal lucifers op de bar (hiernaast voor het gemak als 4 rijtjes met 3, 7, 4, 1 lucifer getekend).
Er zijn twee spelers.
Om de beurt nemen die nu een aantal lucifers weg, waarbij de enige regels zijn:

1.	Je moet minstens één lucifer wegnemen.
2.	Alle lucifers die je wegneemt moeten uit één stapeltje komen.

Wie geen lucifer meer kan pakken heeft verloren (en die geeft uiteraard een rondje, maar dat hoef ik er natuurlijk niet bij te zeggen).

De winnende strategie.

Schrijf eerst de aantallen van de stapeltjes als tweetallige getallen onder elkaar, met daaronder de som van de kolommen:

11
111
100
1

223

We noemen deze kolomsom EVEN als alle cijfers ervan even zijn, en in alle andere gevallen ONEVEN. . De kolomsom hierboven is dus ONEVEN vanwege die laatste 3.
Als je nu uit één stapeltje een aantal lucifers weghaalt, dan verander je dus één van de vier binaire getallen. Dat betekent dat de kolomsommen hoogstens één kunnen veranderen.

eerste observatie:

Als de kolomsom EVEN is, dan wordt deze som na weghalen van een aantal lucifers altijd ONEVEN.

Logisch toch? Als even getallen hoogstens één veranderen worden ze oneven. Je moet minstens één van die getallen veranderen want je mag niet nul lucifers weghalen. Dus er zal minstens ééntje oneven worden.

tweede observatie:

Van een ONEVEN kolomsom kun je door weghalen altijd een EVEN kolomsom maken.

Dat is het snelst te bewijzen door een recept te geven om dat te doen:
Kies de eerste kolom vanaf links die ONEVEN is. Verander in het grootste getal dat een 1 in die kolom heeft die 1 in een 0 en verander verder ook alle enen/nullen van de andere oneven kolomsommen in dat getal.
Dat geeft altijd een kleiner getal, en dat is dus te bereiken door lucifers weg te nemen uit de stapel van dat grootste getal.

in bovenstaand voorbeeld:
De laatste kolom is oneven. Het grootste getal met een 1 in die kolom is 111. Maak van die laatste 1 een 0, en laat de rest gelijk. Dan wordt dat getal 110, dus dat bereik je door van de stapel van 7 lucifers er eentje weg te nemen.

nog een voorbeeldje:
Stel dat de stapels 24 - 4 - 9 - 25 zijn, dan geeft dat deze binaire getallen:

11000
100
1001
11001

23102

• De kolomsom is oneven vanwege de 1 en de 3.
• De meest linker oneven kolom is die met de 3.
• Het grootste getal met in die kolom een 1 is 11001
• Verander daarvan de tweede en derde kolom (want dat zijn de oneven kolommen), dan wordt het 10101
• Kortom: verander de laatste stapel van 25 naar 21.

Deze twee observaties leiden ons tot de volgende simpele winnende strategie:

Immers, dan moet je tegenstander dat (observatie 1) wel voor jou veranderen in een ONEVEN kolomsom, en dan kun jij dat daarna weer (observatie2) veranderen in een EVEN kolomsom.
Dat gaat zo alsmaar door, maar de aantallen lucifers worden wel steeds kleiner. Dat moet dus uiteindelijk wel eindigen in de situatie waarin jij voor je tegenstander twee stapeltjes met elk één lucifer weglegt.
Hij moet er een pakken.... Jij pakt de laatste....
Dus zul je winnen......

(Het enige geval waarin je mogelijkerwijs niet wint is uiteraard dat je tegenstander deze strategie ook kent, en dat jij moet beginnen met een EVEN kolomsom, of dat hij mag beginnen met een ONEVEN kolomsom).

NIM verdekt opgesteld.

Het volgende spel bestaat uit een rechthoekig bord van willekeurige grootte met op elke rij twee fiches, een rode en een gele. De rode fiches zijn van speler ROOD, de gele van speler GEEL. Om de beurt moeten de spelers één van hun fiches een aantal plaatsen in de rij naar links of naar rechts verschuiven. Ze mogen echter niet langs het fiche van de tegenstander gaan.
Een voorbeeldsituatie op een bord van 4 bij 7 staat hieronder.

Degene die niet meer kan zetten heeft verloren.

Eigenlijk zijn we hier gewoon NIM aan het spelen met als stapeltjes de tussenruimtes tussen de fiches.
In het voorbeeld hierboven liggen er als het ware de NIM-stapeltjes 1 - 4 - 4 - 3
Intussen kunnen we eenvoudig berekenen dat de winnende zet nu is om van het laatste stapeltje 1 te maken, dus door het fiche op de onderste rij twee naar dat van je tegenstander toe te schuiven.

Het enige verschil met echt NIM is dat iemand een stapeltje nu ook groter kan maken door zijn fiche naar de buitenrand toe te verplaatsen. In dat geval kun je de grootte van het stapeltje meteen herstellen door jouw fiche op die rij evenveel dezelfde kant op te schuiven.