The Game of Nim

The game of Nim is one of the many combinatoric take-away games. Two players take turns removing chips from three piles. Each turn, a player must take away at least one chip from any of the three piles, but the player cannot take chips from more than one pile. There is no limit to how many chips one can take per turn, so a player can take away every chip from a pile. The winner is the player who takes the last chip, rendering all three piles with zero chips.

Matches are a common object to play Nim with,
but the pros advise beginners to keep them unlit.

Simple Positions

There is only one terminal position, (0,0,0), and, as such, is a P-position. Before we dive into the theories of which positions are P or N, let's start with some simple backwards analysis. If there is only one pile left, one can simply remove the entire last pile to move to the terminal P-position. So, (2,0,0) is an N-position. For two piles left, we can see that positions in which the two piles have an equal number of chips, ex. (3,3,0), are P-positions. On this turn, a player must move the position to one such that the two piles are unequal, ex. taking 1,2, or 3 chips from one of the filled piles. It is simply a matter for the opposing player to return to a position with equal number of chips and to continue this pattern until the terminal position is reached. As such, a position with two, unequal piles is an N-position.
If all three piles have at least one chip in them, there are more avenues of attack. Positions in which at least two of the piles are equal, ex. (1,1,1), (1,2,1), (7,3,3), are N-positions, since it is easy to move to a position with two equal piles and an empty third, which are established P-positions. One step more complicated is the (3,2,1) position. This must be a P-position, as every move will result in either a position with three piles with two equal piles or a position of two piles with unequal amounts. Both of these are established N-positions. We could continue on and find more N and P positions, and we would eventually find a pattern. Luckily, someone's done the work for us, but it requires the definition of a nim-sum.

Nim-Sum

Simply put, the nim-sum of two natural numbers is their addition in base 2 without carry. Those who are familiar with binary numbers may already have an idea of how this works. Every number has a unique base 2 representation which is formed by a string of 1's and 0's in digit places that are powers of 2. The first digit has value of 2 power 0 (1), the second has value 2 power 1 (2), the third has value 2 power 2 (4), the forth has value 2 power 3 (8), etc. Whereas in base 10 we know the value of 345 by computing (3*100 + 4*10 + 5*1), in base 2 we can find the value of 101 by computing (1*4 + 0*2 + 1*1) = 5 base 10. Further, 101101 in base 2 computes to (1*32 + 0*16 + 1*8 + 1*4 + 0*2 + 1*1) = 45 base 10. So, to find the nim-sum of two numbers, we just need to add the base 2 versions of them without carrying digits over. For example, nim-sum(22, 51):

$\ \ \ \ \ \ 10110 \\
\ \ \ \ 110011 \\
= 100101$

Since addition modulo 2 is associative and commutative, so too is nim-sum associative and commutative. So, it doesn't matter what order we add the numbers up. Important to realize is that every number is its own negative. That is, the nim-sum of x and x is 0. So, the cancellation law holds with nim-sums.

Suppose nim-sum(x, y) = nim-sum(x, z).
Then nim-sum(x, x, y) = nim-sum(x, x, z).
Since numbers are their own negative, nim-sum(0, y) = nim-sum(0, z)
Thus, y = z.

Now that we understand nim-sums, we can understand Bouton's 1902 Theorem.

The Theorem of the Game of Nim

The theorem states that a position, (X1, X2, X3), in Nim is a P-position if and only if the nim-sum of its components is zero. That is, nim-sum(X1, X2, X3) = 0. For example, take the position (13, 12, 8). Converting these numbers to base 2 and then adding them yields:

$13 = 1101 \\
12 = 1100 \\
\ \ 8 = 1000 \\
\ \ \ \ = 1001$

1001 $\neq$ 0, so the theorem says that this is an N-position. There must be a move to a P-position, such that when the nim-sum is found again, it comes out to zero. There are more than one move that results in a P-position. One of them is to take away 9 from the pile of 13, leaving 4 in that pile.

$\ \ 4 = 0100 \\
12 = 1100 \\
\ \ 8 = 1000 \\
\ \ \ \ = 0000$

This yields a nim-sum of 0, and so should be a P-position. Of note is that the theorem works for games of Nim with more than three piles. Indeed, any number of piles more than one pile will work. This is only good if we can prove that Bouton's Theorem is true, so let's do that.

Found exclusively within pudding, delicious proof
can only be eaten with the spoon of knowledge. 

The Proof of the Theorem

Let A refer to the set of Nim positions with nim-sum zero, and let B refer to the set of positions of positive, non-zero nim-sums. We check the three standard conditions.

1. All terminal positions are in A. Indeed, they are. The only terminal position is the one with no chips, and nim-sum(0, 0, 0, ...) = 0.
2. From each position in B, there is a move to a position A. This is always possible following these steps. Construct the nim-sum as a column addition and look at the leftmost column with an odd number of 1's. Change any of the numbers that have a 1 in that column to a number such that there are an even number of 1's in each column. Since the 1 in the most significant digit is changed to a 0, this step makes the number smaller. Thus, this is a legal move to a position in A.
3. Every move from a position in A is to a position in B. If (X1, X2, ...) is in A, then nim-sum(X1, X2, ...) = 0. If X1 is changed to X1' < X1, then it is impossible that nim-sum(X1', X2, ...) = 0 because the cancellation law would imply that X1 = X1'. So, nim-sum(X1', X2, ...) $\neq$ 0, and so (X1', X2, ...) is in B.

With all three conditions met, the proof is concluded.

Final Thoughts

Feel free to use this game to your advantage, perhaps to set up a game of Nim with your friends so that you always end up winning. In case they wise up to your antics, tune in to a future blog post where someone will talk about variants of the game of Nim to keep your friends on their toes.

Pointing out grammatical errors to me is appreciated!