Section 2.1 The Game of Nim
In this chapter, we develop the lovely mathematical theory of the game of Nim. This two-player game starts with a few heaps (or piles) of beans (or stones or coins). A move consists of removing some or all of the beans in a single heap. The players take turns, and the winner is the person who makes the last move.
Borrowing the multiset notation from Nimble, we use \(\{ n_1, n_2, \ldots. n_k \}\) to represent a Nim game with \(k\) heaps, where the \(i\)th heap contains \(n_i\) beans, \(1 \leq i \leq k\text{.}\) For example, Figure 2.1.1 shows the game position \(\{ 4, 3, 7 \}.\) There are 14 possible moves from this position. Are any of these options winning moves? We will soon see that the answer to this question is "No." This Nim position is a \(\cP\)-position.
Exploration 2.1.1. Nim.
Play some games of Nim. Once again, you can use whatever markers you like as your beans. Try playing various games with one heap, two heaps and three heaps. Can you find a winning strategy for Nim? Are there any similarities between Nim and Nimble? \end{recess}The game of Nim is the Rosetta Stone for combinatorial games. Charles Bouton analyzed the game of Nim over a century ago. The insights he held and the mathematical framework he devised remain the foundation of the theory of combinatorial games. The name "Nim" appears in the vocabulary of combinatorial games like a mathematical motif. This name appears in definitions like "nim addition" and "nim value."
In fact, the name Nimble is a clever play on words: the game of Nimble is actually Nim in disguised form! This masquerade is quite thin and easy to reveal. In Nim, we can reduce a heap of \(n\) beans to a heap of \(n-1, n-2, \ldots, 2, 1\) or 0 beans. In Nimble, we can move a coin from square \(n\) to square \(n-1, n-2, \ldots, 2, 1\) or off the board (onto "square 0"). So here is the disguise: the coins in a game of Nimble mark the sizes of the heaps in the corresponding game of Nim. This shows that Nim and Nimble are actually the same game, and Figure 2.1.2 demonstrates this correspondence.
In general, we have:
Fact 2.1.3.
The Nim position with heap sizes \(\{ k_1, k_2, \ldots , k_r \}\) is equivalent to the Nimble position with coins on squares \(\{ k_1, k_2, \ldots , k_r \}\text{.}\)
By "equivalent," we mean that a move in Nim corresponds to a move in Nimble. If we remove \(m\) beans from a heap of size \(k\) in Nim, then the analogous move in Nimble is to move the token from square \(k\) to square \(k-m\text{.}\) Therefore, a winning strategy in Nim can be converted into a winning strategy in Nimble, and vice versa.
So who wins at Nim? As a warm-up, consider a Nim game with one heap of \(n\) beans. This game is clearly an \(\cN\)-position, since the Next player can simply remove all of the beans. In fact, this is the only move that guarantees a win. If we leave any beans behind, our opponent can immediately take them all to win the game. Two-heap Nim is also easy to resolve: we leave it as an exercise that \(\{ n, m \}\) is an \(\cN\)-position precisely when \(n \neq m\text{.}\) Three-heap Nim is more complicated, so we are best served by moving directly to the \(k\)-heap case.
In the rest of this chapter, we will develop Bouton's theory of Nim, which gives us a straightforward criteria for determining whether a given Nim position is an \(\cN\)-position (Next player wins) or a \(\cP\)-position (Previous player wins). The key to this framework is to use binary representations of numbers. So let's start by discussing this method of representing numbers.