Application: Winning the game of Nim

The game of nim is very simple to play and has an interesting mathematical structure. Nim is a game for two players, who alternate taking turns to play. Initially the players are given a ``state'' or ``position'' consisting of several piles of tokens. On each turn a player picks a pile and then removes at least one token from that pile. The player who picks up the last token wins ^1.2. Assuming your opponent plays optimally, some positions cannot be won. Such positions are called losing (for the player whose turn it is to move). The positions which are not losing are called winning. (In [BCG], a winning position is defined for the player who just moved.)

The following question has a mathematical answer.

Question: Which positions are losing for the player whose turn it is to move?

The answer is determined by the ``nim sum'' of the piles. The ``nim sum'' of $r$ piles with $m_1$ elements in the $1^{st}$ pile, $m_2$ elements in the $2^{nd}$ pile, ..., $m_r$ elements in the last ($r^{th}$) pile, is obtained as follows:

1. Write each of these numbers in binary and represent this binary number as a vector of 0's and $1$'s with 0's filled in on the end to make them all the same length:
   $$v_1=[a_{10},a_{11},...,a_{1n}], v_2=[a_{20},a_{21},...,a_{2n}], ..., v_r=[a_{r0},a_{r1},...,a_{rn}],$$
   so that $m_i=a_{i1}+a_{i2}2+...+a_{in}2^n$ ($i=1,...,r$),

2. Define the nim sum vector of the position vector to be the vector sum $v_1+v_2+...+v_r$ (componentwise addition).

3. Define the nim sum $G(m_1,m_2,...,m_r)$ of the position to be the number whose binary digits are the entries in the nim sum vector.

If each of the sums $a_{1j}+a_{2j}+...+a_{rj}$ (for $j=0,..,n$) is even then the nim sum is 0 and we call the position even. Otherwise, we call the position odd. In the book by Ball and Coxeter [BC], one finds the following result.

Theorem 1.3.4   Odd positions are winning and even positions cannot be won if your opponent plays optimally.

If an initial position is not a losing position, what strategy should one use to win? Make a move which leaves your opponent an even position. In the special case when you only have two piles, a simpler version of this strategy is simply to make the two piles equal by taking tokens from the larger pile.

Example 1.3.5   Suppose Laura plays Robert and that the initial position is

$$\begin{array}{ccc} \bullet & &\\ \bullet & \bullet&\\ \bullet&\bullet & \bullet \end{array}$$

which is an even position (the nim sum vector is $[2, 2, 0, 0]$). Laura has graciously allowed Robert to play first and he removes one token from the first pile. Laura plays by removing the one (and only) token from the third pile. The position is now

$$\begin{array}{ccc} \bullet & \bullet&\\ \bullet&\bullet & \end{array}$$

which is again an even position (the nim sum vector is $[0, 2, 0, 0]$). Robert plays by removing another token from the first pile. Laura plays by removing one token from the second pile. The position is now

$$\begin{array}{ccc} \bullet&\bullet & \end{array}$$

(the nim sum vector is $[2, 0, 0, 0]$). Robert removes one token from one pile and Laura wins by taking the last remaining token.

For more detailed answers to these questions, see the references [BC] or [HW].

Exercise 1.3.6   Show $a=14$ is $1110$ in binary, is $112$ in $3$-ary, is $24$ in $5$-ary, and is $14$ in $10$-ary.

Exercise 1.3.7 (Bachet's measuring problem)   An assayer owns a balance scale for ore smaples. He places samples on the left scale, weights on the right scale until balance is achieved. He wants to weight all possible samples of grams 1 to n. What is the smallest number of (integral) weights he will need?

Exercise 1.3.8   Use the above rules to answer the following questions. Is 1234567887654321 divisible by 3? 7? 9? 11? 13?

Exercise 1.3.9   Use the above rules to answer the following questions. Is 12345678 divisible by 3? 4? 7? 8? 9? 12?

Exercise 1.3.10   Use the above rules to answer the following questions. Is 1002003004005006 divisible by 3? 4? 7? 8? 9? 11? 12? 13?

Exercise 1.3.11   One quick way to tell if a number was divisible by 7, is as follows. Take the number (expressed in base 10, as are all numbers in the fifth grade), and temporarily put aside the two rightmost digits. Double the number that remains, and add this result to the two-digit number that was just removed. This new result will leave the same remainder as the original number, when divided by 7.

Example: The remainder when 1234 is divided by 7 is the same as $2\cdot 12 +34=58$. Clearly the remainder should therefore be 2.

(a)

Express this ``divisibility test'' in the same form as those above, namely fill in the blank: ``$7\vert a$ if and only if _____________''

(b)

Prove that this test indeed works.

(c)

Invent a related divisibility test for 17. [HINT: Here, consider subtracting rather than adding.]

Exercise 1.3.12   Show that if the starting position in a game of nim is $[2,2]$, then the second player can always win.

Exercise 1.3.13  

Find the nim sum vector for the position

$$\begin{array}{cccc} \bullet & & & \\ \bullet & & & \\ \bul... ...t& \bullet & \\ \bullet&\bullet & \bullet& \bullet \end{array}$$

Exercise 1.3.14   By enumerating all possible games starting from the position

$$\begin{array}{ccc} \bullet & &\\ \bullet & \bullet&\\ \bullet&\bullet & \bullet \end{array},$$

show that the second player can always win.