A Look at Nim
Recall that 1-pile Nim is an N position. Take all except the last coin. Recall also that in 2-pile Nim, it’s an N position if the two piles are not equal – use strategy stealing.
so is in
What about ? It looks like we’re going to need a different method.
Charles Bouton (1962) found a way to solve Nim games. Here’s his approach:
- Split the piles into piles of powers of 2; ie. binary.1
- Then, you XOR all the piles, which is called finding the Nim-Sum of the numbers.2 The intuition here is that for an position, it is possible to reduce the current set into a strategy-stealing solution. In other words, we should take out the coins that differ from the two sets; ie. an XOR of the two sets.
- We have 2 cases. Iff3 the xor (or Nim-Sum) is 0, then the position is a -position. Otherwise, the position is a -position.
- To generate a valid number, take out coins from the largest pile until the xor of the piles is 0.
Formally, a Nim position .
Let consist of all positions such that the Nim Sum of pile sizes is 0. This gives us two sets, . We must now check 3 conditions:
- Terminal positions are in .
- Let , where not all . WLOG, suppose we move by reducing to , . The new Nim Sum is . We know this is not 0, since if it were, (which is a contradiction).
- Let . . In the Nim Sum, consider the leftmost column that has an odd number of ones. We pick the largest pile, flipping zeros into ones and ones to zeros to turn the column sum to 0. This gives a move to .
This proves the theorem, as .
Let’s revisit .
- In binary, we have .
- Next, we XOR all our numbers:
- To generate our winning strategy, we want to take out enough coins from the largest pile until the xor of the piles is 0. In other words, we want the largest pile to become , or to take out 19 from that pile. (To verify, )
Is in or ?
gives a Nim Sum of . We can move to . The remainder of the winning moves is left as an exercise for homework.