Was ist das Nim-Spiel? ...... Das Nim-Spiel ist ein Spiel für zwei Personen.  Gegeben ist ein Haufen von 13 Streichhölzern. Abwechselnd nehmen zwei Personen 1, 2 oder 3 Streichhölzer. Derjenige, der den Haufen leerräumt, hat gewonnen. Statt der Streichhölzer kann man auch Münzen, Spielkarten, Bierdeckel oder andere gleichartige Gegenstände verwenden. Neben diesem Nim-Spiel gibt es Versionen mit mehreren Haufen, die unten beschrieben werden.  Simulation des Nim-Spiels mit 13 Streichhölzer     top Eine Analyse des Spiels läuft auf eine Zerlegung der Zahl 13 in die Summanden 1, 2 oder 3 hinaus.  Es ist für einen Computer eine leichte Aufgabe, diese zu ermitteln.  Es wird angenommen, dass Rot beginnt. Weder Rot noch Schwarz haben eine Strategie.  Folgende Spielverläufe sind möglich. 0001) 13 = 1+1+1+1+1+1+1+1+1+1+1+1+1 1 Spiel mit 13 Zügen Rot gewinnt, Schwarz verliert.  0002) 13 = 1+1+1+1+1+1+1+1+1+1+1+2 ... 0013) 13 = 2+1+1+1+1+1+1+1+1+1+1+1.. 12 Spiele mit 12 Zügen Rot verliert, Schwarz gewinnt  0014) 13 = 2+1+1+1+1+1+1+1+1+1+3 ... 0079) 13 = 2+1+1+1+1+1+1+1+1+1+3.... 66 Spiele mit 11 Zügen Rot gewinnt, Schwarz verliert 0080) 13 = 2+1+1+1+1+1+1+1+1+1  ... 0289) 13 = 2+1+1+1+1+1+1+1+1+1....... 210 Spiele mit 10 Zügen Rot verliert, Schwarz gewinnt 0290) 13 = 2+1+1+1+1+1+1+1+1  ... 0703) 13 = 2+1+1+1+1+1+1+1+1........... 414 Spiele mit 9 Zügen Rot gewinnt, Schwarz verliert 0704) 13 = 2+1+1+1+1+1+1+1  ... 1207) 13 = 2+1+1+1+1+1+1+1.............. 504 Spiele mit 8 Zügen Rot verliert, Schwarz gewinnt 1208) 13 = 2+1+1+1+1+1+1 ... 1564) 13 = 2+1+1+1+1+1+1................ 357 Spiele mit 7 Zügen Rot gewinnt, Schwarz verliert 1565) 13 = 2+1+1+1+1+1  ... 1690) 13 = 2+1+1+1+1+1................... 126 Spiele mit 6 Zügen Rot verliert, Schwarz gewinnt 1691) 13 = 1+3+3+3+3  ... 1705) 13 = 3+3+3+3+1....................... 15 Spiele mit 5 Zügen Rot gewinnt, Schwarz verliert Ergebnis: Es sind 1705 Spiele möglich. Rot gewinnt 1+66+414+357+15= 853 Spiele. Schwarz gewinnt 13+210+504+126 = 852 Spiele.  Die Wahrscheinlichkeit ein Spiel zu gewinnen ist für Rot oder Schwarz fast gleich. Nim-Spiel mit einer Strategie  top Das Nim-Spiel ist nicht fair. Es gibt für den Spieler, der beginnt, eine Strategie, so dass er nie verlieren kann.  Zu Beginn nimmt der spätere Gewinner Rot einen Streichholz. Dann richtet er sich nach seinem Gegner Schwarz. Nimmt dieser 1 Streichholz, so nimmt er 3, nimmt dieser 2 Streichhölzer, so nimmt er auch 2 und nimmt dieser 3 Streichhölzer, so nimmt er nur 1 Streichholz. Bei jeder Runde werden also zusammen 4 Streichhölzer genommen. Mit 4 Streichhölzern vor der letzten Runde kann man nicht verlieren. Die Spielverläufe haben immer 7 Züge. Von den 1705 möglichen Spielen von oben bleiben noch 27 übrig.  01)  13 = 1+(1+3)+(1+3)+(1+3) 02)  13 = 1+(1+3)+(1+3)+(2+2) ... 26)  13 = 1+(3+1)+(3+1)+(2+2) 27)  13 = 1+(3+1)+(3+1)+(3+1)

Variationen des Spiels   top
Es gib viele Abänderungen der Regeln, die jeweils eine neue Strategie erfordern.
> Die Anzahl 13 der Hölzer zu Beginn wird erhöht oder erniedrigt.
> Es dürfen nicht 1, 2 oder 3 Hölzer genommen werden, sondern andere Kombinationen.
> Nicht derjenige, der das letzte Streichholz nimmt, hat gewonnen sondern verloren.

Das Nim-Spiel mit mehreren Haufen   top Das klassische Nim-Spiel besteht aus drei Haufen mit 3, 4 und 5 Streichhölzern. Zwei Personen nehmen von einem Haufen abwechselnd beliebig viele Hölzer. Derjenige, der leerräumt, hat gewonnen.
Auch für diese Version gibt es eine Strategie, die von Anfang an zu einem sicheren Sieg führt. 
Der Gewinner nimmt zu Beginn zwei Hölzer links weg und ist dann in einer Gewinnstellung.
Die Gewinnregel heißt: Man muss jeweils so viele Hölzer wegnehmen, dass die "Nim-Summen" gerade bleiben. 

Man erhält die Nimsummen, wenn man die Anzahl eines jeden Haufens in Vielfache von 4, 2 und 1 zerlegt wie bei der Umrechnung einer Zahl vom Zehnersystem in das Zweiersystem. Die farbig gekennzeichneten Vorzahlen werden addiert. Diese Summen sind die drei Nimsummen. Ergebnis: Die Nimsummen sind 2,1 und 2. 
In der ersten Runde soll der spätere Gewinner A links 2 Hölzer wegnehmen. Ergebnis: Die Nimsummen sind 2,0 und 2, also durchweg gerade. Spieler A ist in einer Gewinnstellung.
Der weitere Spielverlauf könnte so sein.
Zweite Runde (B nimmt rechts 5): Ergebnis: Zwei Nimsummen sind ungerade.

Dritte Runde (A nimmt von der Mitte 3): Ergebnis: Die Nimsummen sind 0,0 und 2, also gerade. 
Vierte Runde (B nimmt von der Mitte 1):  Fünfte Runde (A ist an der Reihe): Der Spieler A nimmt das letzte Streichholz und hat gewonnen.

Literatur   top
Bild der Wissenschaft, 11/1970
Bild der Wissenschaft, 4/1977
Martin Gardner, Mathematical Puzzles & Diversions, New York 1959 (Englisch)

Nim-Spiel im Internet  top

Deutsch

Gerhard Saurer
1-auf-7-Streichholz-Pyramide, 1-2-3-Streichholz-wegnehmen

Wikipedia
Nim-Spiel

Charly Founès 
Marienbad

transience
Pearls Before Swine

A. Bogomolny (cut-the-knot)
The Hot Game of Nim

Wikipedia
Nim