Skip to main content

Chapter 26 Subtraction Games

Calculating the mex of a set of whole numbers.

Recall that \(\W = \{ 0,1,2,3, \ldots \}\text{.}\) For a subset \(S \subset \W\) the mex of \(S\) is the minimum excluded value

\begin{equation*} \mex (S) = \min \{ i \in \W \mid i \notin S\}. \end{equation*}

Calculating the Sprague-Grundy value of a game position.

Given a position \(X\) of a game with followers \(\cF(X) = \{ Y_1, Y_2, \ldots , Y_k \}\) The Sprague-Grundy value of the position is

\begin{equation*} g(X) = \mex \{ g(Y_1), g (Y_2), \ldots g(Y_k) \} \big\}. \end{equation*}

This formula for the Sprague-Grundy value recursive: you is calculate the value for \(X\) by looking at the values of the followers. This is a lot like working your way back up a game tree to figure out whether \(X\) is an \(\cN\)-position or a \(\cP\)-position.

Subtraction Games.

A subtraction game \(S(k_1, k_2, \ldots , k_r)\) is a nim game with a single heap in which you are only allowed to remove \(k_1, k_2, \ldots , k_r\) beans on any given turn. We will use

\begin{equation*} \pile{n} \end{equation*}

to denote a heap of \(n\) beans. It will be helpful to be able to differentiate between the number \(n\) and the pile \(\pile{n}\text{.}\)

Exercises Practice Problems

1. Subtraction \(S(1,2,3,4)\).

  1. Play \(S(1,2,3, 4)\) with pile sizes \(n=1,2,3, \ldots\text{.}\) Determine which pile sizes are \(\cP\)-positions and which ones are \(\cP\)-posititions.

    \begin{equation*} \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4& 5 & 6 & 7 & 8& 9& 10 & 11 & 12 \\ \hline \hline \cP \mbox{ or } \cN? &&&&&&&&&&&& \end{array} \end{equation*}

  2. Calculate \(g(\pile{n})\) for the game \(S(1,2,3,4)\text{.}\)

    \begin{equation*} \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4& 5 & 6 & 7 & 8& 9& 10 & 11 & 12 \\ \hline \hline g(\pile{n}) &&&&&&&&&&&& \end{array} \end{equation*}

  3. Compare your answers to (a) and (b). What do you observe? Make a conjecture about the relationship of the Sprague-Grundy value to the winner of the game.

2. Subtraction \(S(1,2,4)\).

  1. Calculate \(g(\pile{n})\) for the game \(S(1,2,4)\text{.}\)

    \begin{equation*} S(1,2,4): \qquad \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4& 5 & 6 & 7 & 8& 9& 10 & 11 & 12 \\ \hline \hline g(\pile{n}) &&&&&&&&&&&& \end{array} \end{equation*}

  2. Is \(\pile{8}\) an \(\cN\)-position or a \(\cP\)-position in \(S(1,2,4)\text{?}\) If it is an \(\cN\)-position, list every winning move.

  3. Is \(\pile{9}\) an \(\cN\)-position or a \(\cP\)-position in \(S(1,2,4)\text{?}\) If it is an \(\cN\)-position, list every winning move.

3. Subtraction \(S(3,4)\).

  1. Calculate \(g(\pile{n})\) for the game \(S(3,4)\) Note that there is no legal move for a pile of size 1 or of size 2, so \(g(\pile{1})=0\) and \(g(\pile{2})=0\text{.}\)

    \begin{equation*} S(3,4): \qquad \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4& 5 & 6 & 7 & 8& 9& 10 & 11 & 12 \\ \hline \hline g(\pile{n}) &&&&&&&&&&&& \end{array} \end{equation*}

  2. Is \(\pile{8}\) an \(\cN\)-position or a \(\cP\)-position in \(S(3,4)\text{?}\) If it is an \(\cN\)-position, list every winning move.

  3. Is \(\pile{10}\) an \(\cN\)-position or a \(\cP\)-position in \(S(3,4)\text{?}\) If it is an \(\cN\)-position, list every winning move.

4. Subtraction \(S(3,5)\).

Here is the table of Sprague-Grundy values for \(S(3,5)\)

\begin{equation*} \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} n & 0 & 1 & 2 & 3 & 4& 5 & 6 & 7 & 8& 9& 10 & 11 & 12 & 13 & 14 & 15 &16 & 17 & 18 & 19 & 20 \\ \hline \hline g(\pile{n}) &0&0&0&1&1&1&2&2&0&0&0&1&1&1&2&2&0&0&0&1&1 \end{array} \end{equation*}

Who wins the following games of \(S(3,5)\text{?}\)

  1. \(\displaystyle \pile{4}\)

  2. \(\displaystyle \pile{10}\)

  3. \(\displaystyle \pile{14}\)

  4. \(\displaystyle \pile{20}\)

5. Two-Heap Subtraction \(S(3,5)\).

Now let's play 2-heap \(S(3,5)\text{.}\) Just like 2-heap nim, you choose one pile and then make a valid move in that pile.

  1. Play the following \(S(3,5)\) games to determine whether each one is an \(\cN\)-position or a \(\cP\)-position.

    1. \(\displaystyle ( \pile{4} , \pile{4})\)

    2. \(\displaystyle (\pile{4} , \pile{5})\)

    3. \(\displaystyle (\pile{5} , \pile{6})\)

    4. \(\displaystyle ( \pile{6} , \pile{7})\)

  2. Now calculate the following nim sums \(g(\pile{n}) \oplus g(\pile{m})\) for the \(S(3,5)\) positions that you just played. What do you notice?

    1. \(\displaystyle ( \pile{4} , \pile{4})\)

    2. \(\displaystyle (\pile{4} , \pile{5})\)

    3. \(\displaystyle (\pile{5} , \pile{6})\)

    4. \(\displaystyle ( \pile{6} , \pile{7})\)

  3. Decide whether the following \(S(3,5)\) positions are \(\cN\)-positions or \(\cP\)-positions. If it is an \(\cN\)-position, give the list of winning moves.

    1. \(\displaystyle ( \pile{4} , \pile{11})\)

    2. \(\displaystyle (\pile{7} , \pile{13})\)

    3. \(\displaystyle (\pile{7} , \pile{14})\)

    4. \(\displaystyle ( \pile{13} , \pile{18})\)

6. The Sprague-Grundy Value for Nim.

Recall that we use \(*n\) to denote a heap of \(n\) beans in nim.

  1. What is \(g(*n)\text{,}\) the Sprague-Grundy value of a nim heap of size \(n\text{?}\) Start with \(n=0,1,2,3,\ldots\) until you see the pattern.

  2. Calculate the Sprague-Grundy values of the following two-heap nim positions

    \begin{equation*} \begin{array}{c|c|c|c|c|c} g(*n \oplus *m) & *0 & *1 & *2 & *3 & *4 \\ \hline \hline *0 &&&& & \\ \hline *1 &&&& & \\ \hline *2 &&&& & \\ \hline *3 &&&& & \\ \hline *4 &&&& & \\ \end{array} \end{equation*}

  3. Calculate the nim sum \(n \oplus m\)

    \begin{equation*} \begin{array}{c|c|c|c|c|c} n \oplus m & 0 & 1 & 2 & 3 & 4 \\ \hline \hline 0 &&&& & \\ \hline 1 &&&& & \\ \hline 2 &&&& & \\ \hline 3 &&&& & \\ \hline 4 &&&& & \\ \end{array} \end{equation*}

  4. Compare your answers to problems 2 and 3. What do you observe?