Nim Game
 To the Main Page    "Mathematische Basteleien"

What is the Nim Game?
 ....... The Nim Game is a game for two players. It consists of a row of 13 matches. Two players take alternately 1, 2 or 3 matches. The one, who takes the last match, wins.  You also can use coins, cards, beer mats or other things instead of matches.
There are several other nim games with different rows beside this game. I describe them below.

Simulation of the Nim Game with 13 Matches     top
The analysis of this game leads to the additive reduction of the number 13 in the summands 1,2 or 3.
It is an easy task for the computer finding them.
Supposed the two players have the colours red and black.
Red starts. Neither Red nor Black have a strategy.
The following ways of playing are possible.
 0001) 13 = 1+1+1+1+1+1+1+1+1+1+1+1+1 1 game with 13 steps, Red wins, Black loses......

 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 game with 12 steps, Red loses, Black wins......

 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 game with 11 steps, Red wins, Black loses....

 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 game with 10 steps, Red loses, Black wins...

 0290) 13 = 2+1+1+1+1+1+1+1+1  ... 0703) 13 = 2+1+1+1+1+1+1+1+1........... 414 game with 9 steps, Red wins, Black loses...

 0704) 13 = 2+1+1+1+1+1+1+1  ... 1207) 13 = 2+1+1+1+1+1+1+1.............. 504 game with 8 steps, Red loses, Black wins..

 1208) 13 = 2+1+1+1+1+1+1  ... 1564) 13 = 2+1+1+1+1+1+1................ 357 game with 7 steps, Red wins, Black loses.

 1565) 13 = 2+1+1+1+1+1  ... 1690) 13 = 2+1+1+1+1+1................... 126 game with 6 steps, Red loses, Black wins.

 1691) 13 = 1+3+3+3+3  ... 1705) 13 = 3+3+3+3+1....................... 15 game with 5 steps, Red wins, Black loses..

Result: There are 1705 ways of playing the game.
Red wins 1+66+414+357+15= 853 games. Black wins 13+210+504+126 = 852 games.
The probality to win a game is nearly the same for Red or Black.

Nim Game with a Strategy top
The nim game is not fair. There is a strategy for the player who starts so that he can never lose.

In the beginning the later winner Red takes one match. Then he does it the Black's way.
If Black takes 1 match, he takes 3.
If Black takes 2 matches, he also takes 2.
If Black takes 3 matches, he only takes 1.
So they take 4 matches in two steps. You can't lose with 4 matches before going to the last steps.

The games always have 7 moves. There are 27 ways of the game left  instead of 1705 possible ones.
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)

The opponent can see through the simple strategy and can take on it. Therefore you should disguise the rules and only use them towards the end.

Modification of the Game top
There are many alterations of the rules, which require a new strategy.
> You have to raise or to degrade the number of the matches.
> You must not take 1, 2, 3 matches, but other combinations.
> The one, who takes the last match, doesn't win but loses.

Nim Game with Several Rows top The classical nim game consists of three rows of 3, 4 and 5 matches. Two players take any number of matches from one row alternately. The one, who takes the last match, has won.
There is also a strategy for this version, which leads to a safe victory. The winner takes two matches at the beginning. Then he is in a winning position.
The rule for winning is: You must always take so many matches that the "nim sums" are even.

You get the nim sums, if you reduce the numbers of a row in multiple of 4,2 and 1 in the same way as converting a number from the decimal system to the binary system. You must add the coloured numbers. These sums are the three nim sums. Result: The nim sums are 2,1,2.
The winner A should take 2 matches from the left row first.  Result: The nim sums are 2,0,2. All are even. A is in a winning position.

Maybe the next steps are like this.
Second step (B takes 5 from the right row): Result: The nim sums are 1,0,1. Two of them are odd.

Third step (A takes 3 from the middle row): Result: The nim sums are 0,0,2. All are even.

Fourth step (B takes one from the middle row):  Fifth step (A takes the last match):  A is the winner.

The theory of the nim game was discovered by the mathematics professor Charles Bouton at Harvard University in 1901. It is valid for any row and any numbers of matches in a row.

Nim Game on the Internet    top

Deutsch

Gerhard Saurer

Wikipedia
Nim-Spiel

Englisch

Charly Founès

transience
Pearls Before Swine

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

Wikipedia
Nim

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

Feedback: Email address on my main page