Nim
Archibald and Cookie Monster take turns removing 1, 2, 3, or 4 cookies from a pile of 100 cookies. The player to remove the last cookie wins. Archibald goes first. By Zermelo’s Theorem, one of these players can guarantee a win. Identify which one and their winning strategy.
One approach is to consider the winning states of the game. Note that if there is ever a position with 1, 2, 3, or 4 cookies, then the current player’s turn will win. We can call these winning positions. However, if a player has a position with 5 cookies, then any possible move will put their opponent in a winning position, so we say that 5 cookies is a losing position. Furthermore, note that with 6, 7, 8, or 9 cookies, the current player can take away enough cookies to put their opponent in a losing position.
We see that if the number of cookies is divisible by 5, then the current player is losing; otherwise, the current player can win by making the number of cookies divisible by 5. Since we start with 100 cookies, Cookie Monster can guarantee a win.
In general, if we are allowed to remove 1 to $n-1$ cookies from the pile, then a player can win if and only if the number of cookies in the pile is not a multiple of n.
Now, consider a similar game. This time, there are two piles; one with 8 cookies and one with 10 cookies. On each turn, a player can remove any positive integer number of cookies from exactly one of the piles. The player who removes the last cookie wins. Once again, Archibald goes first. Who has the winning strategy?
The winning strategy utilizes a similar idea; this time, if the number of cookies in each pile is different, remove cookies from the larger pile until both piles contain the same number of cookies.
Due to the symmetry of the piles, Archibald's strategy of mirroring Cookie Monster's moves guarantees that Archibald will always have a valid move after any move Cookie Monster makes. Therefore, Cookie Monster can never be the last player to make a move in the game. So, Archibald will win with optimal play.
In general, a player can win the game if, on their turn, the number of cookies in each pile is different.
Nim is a generalized version of the above game, with any number of piles, each starting with any number of cookies. Try to identify the generalized winning strategy.
Hint: Consider the base 2 representations of the number of cookies in each of the piles.
Consider the bitwise XOR of all sizes of the piles.
If you’re unfamiliar with the bitwise XOR, suppose we had two piles; one with 7 cookies, and one with 11 cookies. Here’s a brief demonstration of how to calculate 7 XOR 11 (for shorthand, we write $7 \oplus 11$):
- Express $7$ and $11$ in binary, giving $0111$ and $1011$ (If necessary, make them the same length by appending 0’s at the front of the shorter number).
- For each index, write a $1$ if the bits are different and a $0$ if the bits are the same. So, we write $1100.$ This is equal to $10$ in base $10,$ so we have $7 \oplus 11 = 10.$
We claim that the game is in a winning position if and only if the XOR of all pile sizes is not equal to $0.$ That is, if the XOR of all pile sizes is not equal to $0,$ we can always remove cookies from a pile such that it is equal to $0;$ otherwise, any move will make the XOR of all pile sizes equal to $0.$ Indeed, the XOR of all pile sizes when there are no cookies left (which is a losing game state) is equal to $0.$
Note that XOR satisfies the following properties:
- $a \oplus b = b \oplus a$ (communativity)
- $(a \oplus b) \oplus c = a \oplus (b \oplus c)$ (associativity)
- $a \oplus a = 0$
For convenience, If there are $n$ piles, let $x_1, x_2, \dots, x_n$ denote the $n$ pile sizes before a player’s turn, and let $y_1, y_2, \dots y_n$ denote the $n$ pile sizes after the player’s turn. We have $x_i = y_i$ for all piles $i$ except for one pile $k$ where $x_k > y_k.$
Define $s = x_1 \oplus x_2 \oplus \dots \oplus x_n$ and $t = y_1 \oplus y_2 \oplus \dots \oplus y_n.$ So, we have $$\begin{aligned} t &= 0 \oplus t \\ &= s \oplus s \oplus t \\ &= s \oplus (x_1 \oplus x_2 \oplus \dots \oplus x_n) \oplus (y_1 \oplus y_2 \oplus \dots \oplus y_n) \\ &= s \oplus (x_1 \oplus y_1) \oplus (x_2 \oplus y_2) \oplus \dots \oplus (x_n \oplus y_n) \\ &= s \oplus x_k \oplus y_k. \\ \end{aligned}$$
To prove that states with $s = 0$ are losing, we need to show that if $s = 0,$ then $t \neq 0.$ If $s = 0,$ then we in fact have $t = x_k \oplus y_k \neq 0$ since $x_k$ and $y_k$ must be different.
To prove that states with $s \neq 0$ are winning, we want to prove that there exists a certain $k$ such that subtracting some number of cookies from $x_k$ causes $t = 0.$ To find such a $k,$ consider the position $p$ of the leftmost bit of $s$ that is equal to $1.$ There must be a pile size $x_k$ such that the bit position $p$ in the binary representation of $x_k$ is equal to $1.$ Then, consider $s \oplus x_k.$ Note that all bits to the left of position $p$ in $s \oplus x_k$ are the same as the bits to the left of position $p$ in $x_k$, but the bit at position $p$ changes from a $1$ to a $0.$ Thus, we have $x_k > s \oplus x_k.$ So, making $y_k = s \oplus x_k$ is a valid move. However, note that $$\begin{aligned} t &= s \oplus x_k \oplus y_k \\ &= s \oplus x_k \oplus (s \oplus x_k) \\ &= 0, \end{aligned}$$ so reducing the pile of size $x_k$ to size $s \oplus x_k$ is a winning strategy.
For example, suppose we have three piles of sizes 3, 4, and 5 cookies. Then, we rewrite them in base 2, giving $$\begin{align*} 3 &= 011_2 \\ 4 &= 100_2 \\ 5 &= 101_2 \end{align*}.$$ We hence compute $s = 3 \oplus 4 \oplus 5 = 2 \neq 0,$ so we are in a winning position.
For the winning strategy, we see that $s = 10_2,$ which has a 1 in the 2's place. The only pile that has a size with a 1 in the 2's place is the pile of size 3. Thus, we need to reduce this pile to size $3 \oplus 2 = 1.$ In other words, the winning move is to take two cookies from the pile with 3 cookies. Indeed, we compute $1 \oplus 4 \oplus 5 = 0.$