Pythagoras interactief

We gaan ervan uit dat degene die de laatste lucifer pakt het spel wint. De positie met één stapel van één lucifer is dan winnend. Ook een positie met één stapel met meer dan één lucifer is winnend: we nemen gewoon de hele stapel weg.

Nu analyseren we posities met twee stapels. De 1-1 positie (twee keer één lucifer) is verliezend: na elke zet blijft nog maar één stapel over. De 2-1 positie is winnend, want het weghalen van 1 lucifer uit de grootste stapel levert de (verliezende) 1-1 positie op. De n-1 positie (n>1) is om dezelfde reden winnend. De 2-2 positie is verliezend, want het weghalen van 1 lucifer levert de winnende 2-1 positie op, en het weghalen van 2 lucifers (een hele stapel) verliest eveneens. Zo doorgaande blijken twee gelijke stapels te verliezen, en twee verschillende stapels te winnen.

Het is mogelijk zo alle spelposities te analyseren. De startpositie 1-3-5-7 blijkt verliezend te zijn. De computer wint daarom altijd! Maar als de computer begint, is het mogelijk altijd te winnen!

Als de spelregel zodanig veranderd wordt, dat degene die de laatste lucifer wegneemt verliest, dan is de startpositie 1-3-5-7 eveneens verliezend.

Het stap voor stap analyseren van alle posities is tijdrovend en niet zo elegant. Gelukkig is er een wiskundige theorie die dit in één klap voor alle mogelijke posities doet. Daarvoor moeten de aantallen lucifers in elke rij geschreven worden als binaire getallen.

Deze theorie werkt als volgt. Zet de getallen van de aantallen lucifers in binaire schrijfwijze onder elkaar, de 1-tallen onder de 1-tallen, de 2-tallen onder de 2-tallen, de 4-tallen onder de 4-tallen, enzovoort. Tel de cijfers in elke kolom bij elkaar op. De uitkomst heet de "Nim-som" van de positie. Bijvoorbeeld:

     1                                101
    11                                 10
   101                                  1
   111                                101
   --- +                              --- +
   224 <- even Nim-som                213 <- oneven Nim-som

Een Nim-som heet even als alle scijfers in de som even zijn, anders heet de Nim-som oneven.

We gaan er eerst vanuit dat degene die de laatste lucifer pakt het spel wint. De regel is dat dan dat posities met even Nim-som verliezend zijn, en posities met oneven Nim-som winnend. Bijvoorbeeld, alle volgende posities zijn even, en daarom verliezend: 1-2-3, 1-4-5, 2-4-6.

De volgende stellingen verklaren het verband tussen het even/oneven en het winnend/verliezend zijn van een stelling.

Stelling 1. De verliezer van het spel eindigt met een even positie (0-0-0-0).

Stelling 2. Een even positie wordt altijd veranderd in een oneven positie (en nooit in een even positie)

Stelling 3. Elke oneven positie kan altijd met een geldige zet in een even positie veranderd worden.

Voor de alternatieve spelregel (degene die de laatste lucifer pakt verliest), is de regel maar iets anders: de oneven posities zijn weer winnend en even posities zijn weer verliezend, met uitzondering van 1-1 en 1-1-1-1 (winnend) en 1 en 1-1-1 (verliezend).

Literatuur

1. Charles L. Bouton, Nim, a game with a complete mathematical theory, Annals of Mathematics, Series 2, Vol. 3, p. 35-39, 1901-1902.
2. Dr. Fred Schuh, Wonderlijke problemen, leerzaam tijdverdrijf door puzzle en spel, 2e druk, p. 111-122, W.J.Thieme & Cie, Zutphen.
3. Martin Gardner, Nim and Tac Tix, in: Mathematical Puzzles and Diversions, Simon and Schuster, 1959.
4. Berge, Graphs (Chapter 14), Elsevier Science.

© 2000 Elsevier Science/Pythagoras