Skip to main content

Section 3.1 Mex

In the first two chapters, we cracked the game of Nim: the nim value of a Nim position determines the winner. However, Nim is not the only game in town. The goal of this chapter is to introduce a broader framework that applies to all impartial combinatorial games. Our investigation will culminate in the Sprague-Grundy value of a game position.

The heart of the Sprague-Grundy value is a function called mex. The domain of the mex function is the set of subsets of the whole numbers \(\W = \{ 0 ,1, 2, 3, \ldots \}\text{.}\) The domain is also called the power set of \(\W\text{,}\) and is denoted by \(\mathcal{P}(\W)\text{.}\) The mex of a set \(S \in \mathcal{P}(\W)\) is the least whole number that does not appear in \(S\text{.}\) In other words, the function \(\mex : \mathcal{P}(\W) \rightarrow \W\) is given by

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

Here are some examples:

\begin{equation*} \begin{array}{rcl} \mex ( \{0, 1, 3 \} )&=&2 \\ \mex ( \{1, 2, 3 \} )&=& 0 \\ \mex (\{0, 3, 6 \}) &=& 1 \\ \mex (\{2, 4, 6 \}) &=& 0 \\ \mex (\{0,1,2,3, 5, 7,9 \}) &=& 4 \\ \mex ( \emptyset )&=& 0 \end{array} \end{equation*}

So the mex of a set is the smallest missing whole number. Like the nim value, we will be particularly interested in whether the mex of a set is zero or nonzero. Therefore, we want to emphasize that

Note that \(\mex( \emptyset) = 0\) since the number \(0\) is certainly the smallest number that is not a member of \(\emptyset\text{.}\)

We stress that the mex function assigns a whole number to a set of numbers. We are interested in assigning a number to a position of a game. To avoid confusion, we will follow two conventions.

  • First, we will restrict the term "mex" to sets of numbers, and use the term "Sprague-Grundy value" for the number assigned to a game position.

  • Second, we need a new notation for a nim heap of size \(n\text{.}\) From this point forward, we will use the symbol \(\nim{n}\) for this game position. The nim game with heap sizes \(5, 3, 8\) will now be denoted by

    \begin{equation*} \nim{5} \oplus \nim{3} \oplus \nim{8}, \end{equation*}

    rather than by \(\{5,3,8\}\text{.}\)

Our definition for Sprague-Grundy value is recursive, based on the values of the followers of the position.

Definition 3.1.2.

Let \(\cG\) be a combinatorial game and let \(X\) be a position in this game. Let \(\cF(X) = \{Y_1, Y_2, \ldots , Y_k \}\) be the followers of position \(X\text{.}\) Then the Sprague-Grundy value of \(X\) is

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

We make two quick observations. First, if game position \(X\) has no followers then \(\g(X) = \mex (\emptyset) = 0\text{.}\) Second, if position \(X\) has followers \(\cF(X) = \{ Y_1, Y_2, \ldots , Y_k \}\) then \(\g(X)\) might still be zero: it depends on whether any of the followers have zero Sprague-Grundy value.