Nim is a mathematical game where two players take turns removing objects from heaps. The mathematical theory behind the game was fully developed in [1] by C. Bouton. What follows is a rough description of the game and a proof that gives the winning strategy.
Description
Given $n$ heaps, each with a number $k_{i}$ of objects in it, two players take turns removing as many objects as desired from one heap. A player is forced to remove at least one object, but it is possible to take all the objects in a heap. The winner of the game is the person who takes the last object off the table.
Given heaps of sizes $(1, 2, 3),$ Ligia and Paul decide to play a game of Nim, and Bob, being the gentleman that he is, lets Ligia start.
- Ligia takes 1 from the first heap, leaving $(0, 2, 3)$
- Paul takes 1 from heap 3, leaving $(0, 2, 2)$
- Ligia takes 1 from heap 2, leaving $(0, 1, 2)$
- Paul takes 1 from heap 3, leaving $(0, 1, 1)$
At this point, Paul has won the game. We shall see that, if Paul doesn't make any mistakes, he will win from that initial position only if he goes second. First, some preliminary remarks:
- From any position with only one heap, the player that starts will always win (he can take the entire heap).
- Any position with two heaps of equal size constitutes a loss for the player that has to move. If player A takes $k$ pieces from one of the two heaps, player B can take $k$ pieces from the second and reestablish equality.
- Any position with two heaps of unequal sizes constitutes a win for the first player. He can just equalise the two heaps, and from (2) we know that position is a loss for player B.
For three heaps, it gets tricky. If the reader is so inclined, he can try and solve Nim for three heaps. Some interesting heap sizes to consider are $(1, 2, 2), (1, 2, 3), (2, 4, 6)$.
For those less inclined toward work, the following theorem states whether the player that starts has a winning strategy.
Theorem: The first player to move has a winning strategy iff the nim-sum of the heap-sizes is not 0.
A nim-sum of two elements is the sum of its bits neglecting carry. For those with a background in programming, a nim-sum is the same as a XOR operation. For instance:
$$3 \oplus 2 = 11 \oplus 10 = 01 = 1$$
Proof:
Let $x_{1}, x_{2}, x_{3},... , x_{n}$ be the initial heap-sizes, and suppose one player removed objects from heap $k$. Let $$s = x_{1} \oplus x_{2} \oplus ... x_{n}$$ $$t = y_{1} \oplus y_{2} \oplus ... y_{n}$$
where $y_{i}$ is the heap-size after the move was done. We know $x \oplus x = 0$ and we also know that the nim-sum is associative and commutative. Therefore
$$t = 0 \oplus t = (s \oplus s) \oplus t = s \oplus (s \oplus t) = s \oplus (x_{k} \oplus y_{k})$$
Because $x_{i} = y_{i}$ whenever $i \neq k$.
Lemma 1: If $s = 0$ then $t \neq 0$ no matter what move was made.
This follows immediately from $t = s \oplus x_{k} \oplus y_{k}$ since $x_{k} \neq y_{k}$
Lemma 2: If $s \neq 0$ then there is a move such that $t = 0$.
Let p be the position of the leftmost bit in the binary representation of $s$ and take $k$ such that $x_{k}$ has 1 on position p - such a choice is always possible since otherwise the p-th bit of $s$ would be 0. Let $y_{k} = x_{k} \oplus s$. We claim $y_{k} < x_{k}$ since the leftmost bit of $y_{k}$ is on a position less than the p, and every other change in bits amounts to at most $2^p - 1$. Then
$$t = s \oplus x_{k} \oplus (s \oplus x_{k}) = 0$$
So we can take $x_{k} - (s \oplus x_{k})$ objects from pile $k$.
This completes the proof, since we know $0, 0,... , 0$ is a position with nim-sum 0, and we can reduce any non-zero nim-sum to a zero nim-sum, and no 0 nim-sum can be taken into another 0 nim-sum.
Returning to Ligia and Paul, we see that $$1 \oplus 2 \oplus 3 = 0,$$ therefore the first player will lose, given perfect play on both sides. But let's say Ligia hasn't been paying attention to her brother when he tried explaining Game Theory to her, and she thinks she can win. Replicating the moves above, we have:
Returning to Ligia and Paul, we see that $$1 \oplus 2 \oplus 3 = 0,$$ therefore the first player will lose, given perfect play on both sides. But let's say Ligia hasn't been paying attention to her brother when he tried explaining Game Theory to her, and she thinks she can win. Replicating the moves above, we have:
- Ligia takes 1 object from the first pile. Position is now $(0, 2, 3)$
- Paul knows his Game Theory, and he knows how to do nim-sums. He easily computes $$0 \oplus 2 \oplus 3 = 1$$ The most significant bit in the binary representation of $1$ is on the right-most position, and, out of $2$ and $3$, only $3$ has a 1-bit on the right-most position. We compute $1 \oplus 3 = 2,$ so we take $3 - 2 = 1$ objects from the last pile. Position is now $(0, 2, 2)$
- We know $(0, 2, 2)$ is losing. Even if we didn't know, we could easily compute the next moves to see that Ligia's cause is indeed hopeless.
This shows that the starting player has a winning strategy only if the nim-sum of the starting elements is not zero, and the winning play on each turn is to reduce the current position to one with nim-sum zero. For more information, a good introductory article in game theory that covers Nim in sufficient detail is [2]. A more detailed approach can be found in either [3], or [4].
References:
[1] C. L. Bouton: Nim, a game with a complete mathematical theory, Annals of Mathematics 3 (1901–02), 35–39
[2] Thomas S. Ferguson, Game Theory
[3] Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy: Winning Ways for your Mathematical Plays
[4] John H. Conway, On Numbers and Games
