Nim (spel)

Nim is een spel voor twee spelers, waarbij de spelers om beurten een aantal voorwerpen (bijvoorbeeld lucifers) moeten wegnemen van een aantal stapels. De spelers doen om de beurt een zet, die er uit bestaat dat van één stapel minimaal één voorwerp en maximaal de hele stapel wordt weggenomen.

In de gewone versie wint de speler die het laatste voorwerp wegneemt. Er is ook een zogenaamde misère-versie van het spel, waarbij de speler die het laatste voorwerp moet nemen verliest. Deze versie, die de meest gebruikelijke is, komt voor in de film L'Année dernière à Marienbad (1961) van Alain Resnais. Sindsdien wordt het spel in het Frans jeu de Marienbad genoemd.

Het spel (of varianten daarvan) werd vermoedelijk al duizenden jaren gespeeld in het Verre Oosten. Het werd onder de naam Nim voor het eerst beschreven in 1901 door C. L. Bouton van de Harvard-universiteit, die ook de volledige theorie van het spel ontwikkelde. De naam komt wellicht van het Duitse woord nimm! hetgeen "neem!" betekent.

Bouton bewees wiskundig dat voor eender welk aantal stapels en voorwerpen er voor een van beide spelers een strategie bestaat om altijd te winnen, zowel voor de gewone versie als voor de misère-versie.

Nim wordt tegenwoordig als wiskundig spel gebruikt ter illustratie van de stelling van Sprague-Grundy uit de combinatorische speltheorie.

Een positie is gewonnen als je door verstandig spel altijd kunt winnen. Een positie is verloren als je, bij verstandig tegenspel, altijd verliest, welke zet je ook doet.

Dit is de manier om de winnende zet(ten) te vinden als jij aan zet bent:

1. Schrijf de aantallen voorwerpen in de stapels als binaire getallen.
2. Zet de getallen van de aantallen voorwerpen in elke stapel in binaire schrijfwijze onder elkaar, de 1-tallen onder de 1-tallen, de 2-tallen onder de 2-tallen etc. Tel dan de cijfers in elke kolom bij elkaar op. De uitkomst heet de nim-som van de positie.
3. Als alle getallen van de nim-som even zijn, dan is de positie winnend. De tegenspeler moet dan in diens volgende zet altijd ergens een kolom-som oneven maken. Voor jou bestaat er dan in de volgende zet minstens één combinatie waarbij je alle getallen weer even kan maken. Dat is dan de zet die je moet doen.

Heb je bijvoorbeeld de aantallen voorwerpen 1-3-5-7, dan is dat in binaire getallen 111-101-11-1. Onder elkaar geeft dit:

111
101
011
001
---
224

Dus is de nim-som 2,2,4. Deze positie is dus winnend.

In de misère-versie is de winnende strategie dezelfde als bij het normale spel, behalve wanneer er (aan het einde van het spel) door de zet alleen nog maar stapels van 1 voorwerp zouden overblijven. De winnende zet is dan zo dat er een oneven aantal stapels van 1 voorwerp overblijft (bij het gewone spel zou bij de winnende zet een even aantal stapels van 1 voorwerp overblijven).

De Deense wetenschapper Piet Hein ontwikkelde een versie van het spel, Nimbi, waarvoor (nog) geen winnende strategie bekend is^[1]. In plaats van de voorwerpen in hoopjes op te delen, rangschikt men ze in een vierkant of rechthoek. Om beurten neemt nu elk van beide spelers één of meer aangrenzende voorwerpen die horizontaal of verticaal op één lijn liggen. Ook hier pakt men bij elke beurt minstens één voorwerp. Bijvoorbeeld:

X X X X X X X X X X X X X X X X X X X
X X X X X X X X X X X X X X X X X X X
X X X X X X X → X X X X X X → X X X etc.
X X X X X X X X X X X X X X X X X X X
X X X X X X X X X X X X X X X X X X X X X

• (fr) Jacques Bouteloup, Jeux sur graphes, jeux de Nim, Amiens, ADCS, 1996