How to Be a Player: Impartial Combinatorial Games

1.

Find the mex of the following subsets of \(\W\text{.}\)

1. \(\displaystyle \{ 1,3,5,7 \}\)

2. \(\displaystyle \{ 2,4,6,8 \}\)

3. \(\displaystyle \{ 0,1,2,4,8,16 \}\)

4. \(\displaystyle \{ 1,2,3,4,5 \}\)

5. \(\displaystyle \{ 0,2,3,5 \}\)

6. \(\displaystyle \{ 0,1,2,3,4,5,6,7 \}\)

2.

Calculate the Sprague-Grundy values for the following Subtraction Games. Keep going until these values become periodic.

1. \(\displaystyle S(2,5)\)

2. \(\displaystyle S(2,6)\)

3. \(\displaystyle S(2,7)\)

4. \(\displaystyle S(2,3,5)\)

5. \(\displaystyle S(1,4,6)\)

3.

Find the Sprague-Grundy values for \(S(1,2,3,4,5 \text{.} \)

4.

Prove that your answer from the previous problem is correct using strong induction. Hint: your base cases are \(0,1,2,3,4,5\text{.}\) In order to prove the result for \(n\text{,}\) it is best to think of \(n\) as \(n = 6m + r\) where \(0 \leq r \leq 5\text{.}\)

5.

Continue to calculate the Sprague-Grundy values for \(S(2,5,7)\) as found in Table Figure 3.2.3. Notice that this sequence of 22 values repeats itself. Will this continue? How can you be sure?

6.

Show that the Sprague-Grundy values for \(S(2,4,7)\) are periodic, but that this sequence does not settle down until the heap size is greater than 7. What is the period of this sequence for large pile sizes?

7.

1. Create a table of Sprague-Grundy values for \(S(1,2)\) for pile sizes \(0 \leq n \leq 4\text{.}\)

2. Create a table of Sprague-Grundy values for \(S(1,2,3)\) for pile sizes \(0 \leq n \leq 4\text{.}\)

3. Now consider a two-pile game \((\pile{n}, \pile{m})\) where we play \(S(1,2)\) on the left pile and \(S(1,2,3)\) on the right pile. Create a \(5 \times 5\) table of Sprague-Grundy values for this two-pile game. The rows of your table should correspond to \(S(1,2)\) moves on the left pile, and the columns of your table should correspond to \(S(1,2,3)\) moves on the right pile.

8.

Consider the subtraction game \(S(A)\) where \(A= \{ s_1, s_2, \ldots s_k \}\) where \(s_1 < s_2 < \cdots < s_k\text{.}\) Prove that \(g(\pile{n}) =1\) if and only if \(g(\ppile{n-s_1}) =0\text{.}\)

9.

1. Calculate the nim sum \(2 \oplus 3\)

2. Create the game tree for \(\nim{2} \oplus \nim{3}\text{.}\)

3. Starting at the leaves of your tree, mark the Sprague-Grundy value for each game position in your tree by using Definition \ref{def-sprague}. Check that the Sprague-Grundy value of your root \(\nim{2} \oplus \nim{3}\) matches the nim value in part (a).

10.

Use strong induction to prove Lemma 3.3.1. Namely, prove that the Sprague-Grundy value of \(*n\) is \(g(\nim{n})= n.\)