Ken's POTW


Nim
In the game of Nim (as I know it) two players each take turns taking any number of sticks from any one of three piles. The winner is the player who takes the last stick.
  1. If the three piles hold 3, 5, and 7 sticks, and it's your turn to play, what is your best move?
  2. If, instead, there are four piles holding 3, 5, 7, and 9 sticks, and it's your turn to play, what is your best move?
  3. Is there a strategy that can be followed to win the game? (Briefly show how it works in the above examples.)
Extra:

Source: Previous puzzle experience. Some parts used as Ken's Puzzle of the Day 2/10/94.

Solution:
Wilfred Theunissen and Evert Offereins provided solutions to the first two questions above:
1. The best move with 3, 5, and 7 sticks is to remove 1 (one) stick from any pile.
2. The best move with 3, 5, 7, and 9 sticks is to remove 8 sticks from the pile of 9.

3. They also provided me with a full table to follow, showing what combinations of sticks to leave after each move in order to win the game for either winning or losing by taking the last stick. I decided not to show their table [yet; I'll probably show it later] to see if someone can come up with a more generic solution.

For example, what strategy should be followed if the number of sticks increased to 103, 105, and 107? Now, creating a table would be too cumbersome, but a strategy can be found.

Mark Tilford sent this solution: 
The game of Nim was completely analyzed around the turn of the century;
here's the general strategy:

1)  Express the number of items in each pile in binary notation.
(For 3, 5, 7 this is 011, 101, 111)

2)  For each place, count the number of 1's in that position.
(For 3, 5, 7, this is 223)

3)  If the number of 1's in each column is even, then person about to
move will lose; otherwise, he/she can win by making a move that will
make all the values even.

For the 103, 105, 107 case, the answer is:
103 = 1100111
105 = 1101001
107 = 1101011

Number in each column:
      3302123
Need to remove 1100101 to make all digits even;
Remove 101 from the first pile.


In the case when last match loses, adjust the endplay when all but
one/two piles have one marker.
On 11/20/98, Micah Fogel from the Illinois Math and Science Academy sent the following references for game analysis of Nim. One reference is "On Number and Games" by J.H. Conway. Another is "Winning Ways for your Mathematical Plays" by Conway, Berlekamp, and Guy.

He reports for the Extra section above: These references also explain how to play the game where you try to force your opponent to take the last stick. Basically, you play exactly the same way except that piles of one stick are treated as if they had no sticks in them.

He also mentions about 3-player Nim (11/25/98): Thinking about the three player Nim puzzle some more, I searched for some info and came up with the following paper, which is in publication but not yet published: http://www-math.mit.edu/~propp/three.ps which tells the general theory of three player Nim. It's pretty technical, though. The short summary is that except in obvious cases (one big pile or lots of piles with just one stick each, and a couple of other rare exceptions), there is no best possible strategy for any player playing alone. The best strategy is to gang up on the third player. Two people playing as a coalition against one can win in all cases which aren't constrained like I said in the parentheses.

Mail to Ken