NIM

Voor ons op tafel (meestal op de bar) liggen een willekeurig aantal stapeltjes lucifers met in elk stapeltje een willekeurig aantal lucifers. We gaan het volgende spelletje spelen: om de beurt halen we een aantal lucifers weg. Er zijn maar twee regels:

1. Je moet minstens één lucifer weghalen
2. Alle lucifers die je weghaalt moeten uit het zelfde stapeltje komen.

Wie de laatste lucifer weghaalt heeft gewonnen.
Eerst maar even spelen dan?

In het volgende programma kun je tegen de computer of tegen een medespeler oefenen. Veel plezier.....
Als je een poosje speelt zul je al snel merken dat het winnend is om symmetrische posities voor je tegenstander weg te leggen. Liggen er bijvoorbeeld nog twee stapeltjes met elk 14 lucifers, en is hij aan de beurt, dan heb je gewonnen: je doet gewoon hetzelfde als hij en je houdt de situatie symmetrisch. Haalt hij er 5 weg uit het ene stapeltje, dan doe jij dat uit het andere. Op deze manier zul jij altijd de laatste krijgen. 

Dat brengt ons op het idee het tweetallige stelsel te gaan gebruiken. 
"Er zijn 10 soorten wiskundigen: degenen die binair denken en degenen die dat niet doen!"

De redenering is als volgt:

Schrijf alle aantallen van de stapeltjes binair op. 
Als je dat lastig vindt kun je het met het machientje hiernaast omrekenen.

In dit geval geeft dat  101 , 11 , 10 , 100 en 1010
Schrijf deze getallen onder elkaar en tel de kolommen op:

geef je getal:

  101
    11
    10
  100
1010
1232

Omdat je met wegnemen maar één van de vijf getallen kunt veranderen, zullen van de onderste vier getallen (de kolomsommen) sommigen 1 veranderen, anderen niet. Stel dat ze allemaal even zijn. Dan zal je tegenstander er zeker sommigen oneven van moeten maken. Maar daarna kun jij ze weer even maken. Hij weer oneven. Jij weer even....

We blijven de cyclus even-oneven-even-.... volgen, terwijl het aantal lucifers steeds minder wordt. Op een gegeven moment zal dat moeten resulteren in twee gelijke rijen die je voor hem weglegt, en je hebt gewonnen!

Waarom kun je van oneven altijd even maken?
Kies de eerste kolom vanaf links die oneven is. Verander in dat binaire getal de 1 in een 0 en verander daar verder ook alle enen/nullen van de andere oneven kolomsommen. Dat geeft altijd een kleiner getal, en dat is dus te bereiken door lucifers weg te nemen.

Voorbeeld
In de situatie hierboven zijn de eerste en derde kolom oneven. Daarom verander je 1010 in 0000 (verander de eerste en derde kolom). De winnende zet is dus de hele stapel van 10 wegnemen.

  

Stel dat je tegenstander vervolgens één lucifer uit de stapel van 5 weghaalt. Dat geeft de NIM-som:

100
  11
  10
100
221

Om de som weer even te maken moet je de laatste kolom veranderen. Dat kan door 11 in 10 te veranderen: Pak één lucifer uit de stapel van 3 weg. Dat laat nu 4-2-2-4 over en de situatie is volledig symmetrisch: wat hij in de ene stapel van 4/2 doet, doe jij in de andere stapel van 4/2.
GEWONNEN!

Tip om snel te tellen:
Zet je vingers op tafel, allemaal naar beneden. (stand "0"). Neem als pink de eenheden, ringvinger de 2-tallen, middelvinger de 4-tallen, enz.). Ga de stapeltjes langs en elke keer als er een 1 in het binaire getal staat verander je de positie van die vinger (optillen/ weer naar beneden laten). De vingers die uiteindelijk omhoog staan bepalen welke kolommen je moet veranderen. Bij het oorspronkelijke voorbeeld zul je na afloop je wijsvinger en ringvinger omhoog hebben en de rest op tafel. Dat betekent dat je 1010 moet veranderen, en dat kan alleen door de hele stapel van 10 weg te halen. Simpel!!!!!

 

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.