Skip to main content

Section 3.2 Subtraction Games

Let's calculate some examples of Sprague-Grundy values for some simple games. We'll get to Nim soon enough, but for now we explore a class of games called Subtraction Games. Our first game is named \(S(1,2,3)\text{.}\) The game plays like Nim, except you are only allowed to take 1, 2 or 3 beans from a heap.

Exploration 3.2.1.

Play a few games of single heap \(S(1,2,3)\text{.}\) Start small, with heap sizes \(n=1,2,3,4,5,6\text{,}\) etc. Keep playing until you figure out the winning strategy, as well as characterizing the \(\cN\)-positions and \(\cP\)-positions.

Now that you have mastered one-heap \(S(1,2,3)\text{,}\) let's calculate its Sprague-Grundy values. Just as with Nim, it is helpful to use a notation that distinguishes heaps from numbers. The starred symbol \(*n\) is reserved exclusively for a nim heap of size \(n\) (where we are allowed to remove any number of beans). For Subtraction (and other various take-away games), we will use the "bullet" notation \(\pile{n}\) to denote a heap of size \(n\) in a subtraction game. We have

\begin{equation*} \begin{array}{rcl} g \left(\pile{0} \right) &=& \mex \{ \} =0, \\ g \left(\pile{1} \right) &=& \mex \{ g(\pile{0}) \} = \mex \{ 0 \} = 1, \\ g \left(\pile{2} \right) &=& \mex \{ g(\pile{0}), g(\pile{1}) \} = \mex \{ 0,1 \} = 2, \\ g \left(\pile{3} \right) &=& \mex \{ g(\pile{0}), g(\pile{1}), g(\pile{2}) \} = \mex \{ 0,1,2 \} = 3, \\ g \left(\pile{4} \right) &=& \mex \{ g(\pile{1}), g(\pile{2}), g(\pile{3}) \} = \mex \{ 1,2,3 \} = 0. \end{array} \end{equation*}

We see that the Sprague-Grundy value equals the size of the heap until we reach \(n=4\text{.}\) At this point, we can only remove 1, 2 or 3 beans. Therefore position \(\pile{0}\) is not among the followers of position \(\pile{4}\text{.}\) If we continue this way, we get the Sprague-Grundy values shown here:

\begin{equation*} \begin{array}{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 \\ \hline \g(\pile{n}) & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 \end{array} \end{equation*}

What is the relationship between these values and the \(\cN\)-positions and \(\cP\)-positions of \(S(1,2,3)\) that you found by playing the game? Are you willing to make any conjectures at this point?

Let's try another game of Subtraction, using a different subtraction set. Given a set \(A \in \W\text{,}\) the Subtraction game \(S(A)\) is played as you would expect: make Nim moves, but restricted to numbers that appear in the subtraction set \(A\text{.}\) Here are the Sprague-Grundy values for \(S(2,3)\text{:}\)

\begin{equation*} \begin{array}{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 \\ \hline \g(\pile{n}) & 0 & 0 & 1 & 1 & 2 & 0 & 0 & 1 & 1 & 2 & 0 & 0 & 1 & 1 \end{array} \end{equation*}

Without playing \(S(2,3)\text{,}\) can you guess whether \(\pile{10}\) is an \(\cN\)-position~or a \(\cP\)-position? How about \(\pile{9}\text{?}\)

Exploration 3.2.2.

Find the Sprague-Grundy values for a few more subtraction games \(S(s_1,s_2, \ldots, s_k)\text{.}\) Experiment with different sizes of subtraction sets, different values, and different relationships between these values. Be creative!

Here are the Sprague-Grundy values for a more complicated game: \(S(2,5,7)\text{.}\)

\begin{equation*} {\small \begin{array}{c|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 & 21\\ \hline \g(\pile{n}) & 0 & 0 & 1 & 1 & 0 & 2 & 1 & 3 & 2 & 2 & 0 & 3 & 1 & 0 & 0 & 1 & 1 & 2 & 2 & 3 & 3 & 2 \end{array} } \end{equation*}

There is a nice technique for calculating the Sprague-Grundy values for a game with a tricky subtraction set (like \(2,5,7\)). We use something called a Grundy scale. Intuitively, a Grundy scale is a ruler with tick marks that identify the allowed subtractions. It is pretty easy to calculate the first 7 values of \(S(2,5,7)\text{,}\) so we will pick up our calculation there. Here is the partially filled in table for \(S(2,5,7)\text{:}\)

Figure 3.2.1. A Sprague-Grundy scale.

Below this table is the Grundy scale for \(S(2,5,7)\text{,}\) positioned under the column for \(\pile{7}\text{.}\) You create the Grundy scale on a separate piece of paper. Starting at the double arrow, we create 3 arrows to the left, at distances 2, 5 and 7. As shown the double arrow points to 7 and the single arrows point to the followers of \(\pile{7}\text{.}\) This makes it easy to calculate the Sprague Grundy value for \(\pile{7}\text{:}\)

\begin{equation*} \g(\pile{7}) = \mex \{ \g(\pile{5}), \g(\pile{2}), \g(\pile{0}) \} = \mex \{ 2, 1, 0 \} = 3. \end{equation*}

To find \(\g(\pile{8})\text{,}\) we just move our Grundy scale to the right. It's a snap to see that \(\g(\pile{8}) = \mex \{ 1,1,0 \} = 2\text{,}\) and shown below.

Figure 3.2.2. Using the Sprague-Grundy scale to find the next value

We treat a Grundy scale like a ruler: it quickly identifies the Grundy values of the followers. We create the Grundy scale on a separate piece of paper so that we can continue to shift it rightwards, and then calculate successive Grundy values of Subtraction Games. Hopefully, you can see what the Grundy value for \(\pile{9}\) should be from the following picture. (You can check your calculation against the completed table above.)

Figure 3.2.3. Finding another valuing using the Sprague-Grundy scale.

At this point, you should be pretty confident that \(\pile{n}\) is a \(\cP\)-position~if and only if \(\g(\pile{n})=0\text{.}\) We will prove this in the next section.

Undoubtedly, you will also have noticed that the Sprague-Grundy values for \(S(1,2,3)\) and \(S(2,3)\) are periodic. The Sprague Grundy values for \(S(2,5,7)\) eventually become periodic as well, thought it takes a little while for them to settle down. In other words, \(S(2,5,7)\) does become periodic if we ignore the first few values. (Keep calculating these values for \(n \geq 22\) to see the pattern that emerges).

Our next theorem shows that this is always the case: every Subtraction Game with a finite subtraction set eventually becomes periodic.

Without loss of generality, we have \(s_1 < s_2 < \cdots < s_k\text{.}\)

For \(n \geq s_k\text{,}\) we have

\begin{equation*} \g(\pile{n}) = \mex \{ \g(\ppile{n-s_1}), \g(\ppile{n-s_2}), \ldots , \g(\ppile{n-s_k}) \}. \end{equation*}

Since there are only \(k\) followers, we have \(\g(\pile{n}) \leq k\text{,}\) with \(\g(\pile{n})=k\) precisely when the followers of \(\pile{n}\) take on the Sprague-Grundy values \(0,1,2,\ldots , k-1\) in some order.

Partition \(\W\) into disjoint sets \(B_0, B_1, \ldots, B_m, \ldots\) where \(B_0 = \{ 0, 1, 2, \ldots , s_{k}-1 \}\text{,}\) \(B_1 = \{ s_k, s_k + 1, \ldots, 2 s_k -1 \}\) and in general,

\begin{equation*} B_i = \{ i \cdot s_k, i \cdot s_k + 1, \ldots , (i+1) s_k -1 \}. \end{equation*}

There are an infinite number of \(B_i\)'s. However, there are \((k+1)^{s_k}\) possibilities for the sequence of Sprague-Grundy values associated to each \(B_i\text{.}\) This means that these blocks Sprague-Grundy sequences of length \(s_k\) must repeat! In other words, there exists \(i \neq j\) such that \(B_i = B_j\text{.}\) Furthermore, there must be an infinite number of repeats (because there are only a finite number of possible blocks.

Next, we show that as soon as we encounter our first repeated block, we can be sure that the sequence has become periodic. Choose \(i < j\) such that \(B_i=B_j\text{,}\) and this is the first such pair of repeating blocks in the sequence. In other words, setting \(N=i \cdot s_k\) and \(M = j \cdot s_k\) we have

\begin{equation*} \begin{array}{rcl} \g(\pile{M}) &=& \g(\pile{N}), \\ \g(\ppile{M + 1}) &=& \g(\ppile{N + 1}), \\ & \vdots & \\ \g(\ppile{M + s_k -1}) &=& \g(\ppile{N + s_k - 1}). \end{array} \end{equation*}

But this forces \(\g(\ppile{M + s_k}) = \g(\ppile{N + s_k}) \) because

\begin{equation*} \begin{array}{rcl} & & \g(\ppile{M + s_k)} \\ &=& \mex \{ \g(\ppile{M + s_k - s_1}), \g(\ppile{M + s_k - s_2}), \ldots , \g(\ppile{M + s_k - s_{k-1})}, \g(\ppile{M} ) \} \\ &=& \mex \{ \g(\ppile{N + s_k - s_1}), \g(\ppile{N + s_k - s_2}), \ldots , \g(\ppile{N + s_k - s_{k-1}}), \g(\pile{N} ) \} \\ &=& \g(\ppile{N + s_k}) \end{array} \end{equation*}

This repetition continues (for the same exact reason). We have \(\g(\ppile{M + s_k+1}) = \g(\ppile{N + s_k+1}), \) and \(\g(\ppile{M + s_k+2}) = \g(\ppile{N + s_k+2})\text{,}\) and so on. Therefore, the sequences continue to coincide forever.

We make one comment about the above proof. We do successfully prove that the sequence must repeat after a certain point, but our proof does not claim to find the first heap size where the Sprague-Grundy values start to repeat. We also don't learn much about the actual period of the sequence. The problem: we blindly chose to look at the sequence in huge blocks, regardless of the actually behavior of the sequence. In a sense, we are considering a "worst case scenario," so all we learn is that the period is at most \(M-N= s_k(j-i).\) We can get an upper bound on \(j-i\) using the Pigeonhole Principle, which says that \(j-i \leq (k+1)^{s_k}\text{.}\) Our resulting bound on the period of the Sprague-Grundy values is \(s_k (k+1)^{s_k}\text{,}\) which can be very large indeed.