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
1auf7StreichholzPyramide,
123Streichholzwegnehmen
(Spiele, kostenloses Download)
Wikipedia
NimSpiel
Englisch
Charly Founès
Marienbad
transience
Pearls
Before Swine
A. Bogomolny (cuttheknot)
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
This
page is also available in German.
URL of
my Homepage:
http://www.mathematischebasteleien.de/
©
2000 Jürgen Köller
top 