Skip to main content\( \newcommand{\identity}{\mathrm{id}}
\newcommand{\notdivide}{{\not{\mid}}}
\newcommand{\notsubset}{\not\subset}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\gf}{\operatorname{GF}}
\newcommand{\inn}{\operatorname{Inn}}
\newcommand{\aut}{\operatorname{Aut}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cis}{\operatorname{cis}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\Null}{\operatorname{Null}}
\definecolor{orange}{RGB}{255, 165, 0}
\definecolor{crimson}{RGB}{220,20,60}
\definecolor{pink}{RGB}{255,20,147}
\definecolor{darkGreen}{RGB}{34,139,34}
\definecolor{olive}{RGB}{128,128,0}
\definecolor{teal}{RGB}{0,128,128}
\definecolor{turquoise}{RGB}{64,224,208}
\definecolor{navy}{RGB}{30, 144, 255}
\definecolor{purple}{RGB}{128,0,128}
\definecolor{indigo}{RGB}{216, 191, 216}
\definecolor{maroon}{RGB}{128,0,0}
\definecolor{gold}{RGB}{255,215,0}
\definecolor{lemon}{RGB}{255, 250, 205}
\definecolor{peru}{RGB}{205, 133, 63}
\definecolor{alizarin}{rgb}{0.82, 0.1, 0.26}
\definecolor{brightmaroon}{rgb}{0.76, 0.13, 0.28}
\definecolor{cardinal}{rgb}{0.77, 0.12, 0.23}
\definecolor{tuscanred}{rgb}{0.51, 0.21, 0.21}
\definecolor{steelBlue}{rgb}{0.27, 0.51, 0.71}
\definecolor{tyrianpurple}{rgb}{0.4, 0.01, 0.24}
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\Q{\mathbb Q}
\def\N{\mathbb N}
\def\C{\mathbb C}
\def\ba{{\mathbf{a}}}
\def\bb{\mathbf{b}}
\def\bh{{\mathbf{h}}}
\def\bu{{\mathbf{u}}}
\def\bv{{\mathbf{v}}}
\def\bw{{\mathbf{w}}}
\def\bx{{\mathbf{x}}}
\def\by{\mathbf{y}}
\def\bone{{\mathbf{1}}}
\def\bzero{\mathbf{0}}
\def\var{{\mbox{var}}}
\def\P{{\mathbb{P}}}
\def\E{{\mathbb{E}}}
\def\cA{{\mathcal{A}}}
\def\cB{{\mathcal{B}}}
\def\cC{{\mathcal{C}}}
\def\cP{\mathcal P}
\def\cF{{\mathcal F}}
\def\cE{\mathcal E}
\def\cO{\mathcal O}
\def\kin{k^{\mathrm{in}}}
\def\kout{k^{\mathrm{out}}}
\newcommand{\indeg}[1]{k^{\mathrm{in}}_{#1}}
\newcommand{\outdeg}[1]{k^{\mathrm{out}}_{#1}}
\tikzset{->-/.style={decoration={
markings,
mark=at position .5 with {\arrow{latex}}},postaction={decorate}}}
\newcommand{\pile}[1]{\bullet{#1}}
\newcommand{\ppile}[1]{\bullet({#1})}
\newcommand{\nim}[1]{*{#1}}
\newcommand{\bc}{C}
\newcommand{\R}{{\mathbb R}}
\def\nimsum{\, \oplus \,}
\def\mex{{\mathrm{mex}}}
\def\g{g}
\newcommand{\inter}{{\mathrm{int}}}
\def\cA{{\mathcal A}}
\def\cB{{\mathcal B}}
\def\cF{{\mathcal F}}
\def\cG{{\mathcal G}}
\def\cH{{\mathcal H}}
\def\cN{{\mathcal N}}
\def\cQ{{\mathcal Q}}
\def\cP{{\mathcal P}}
\def\W{{\mathbb W}}
\newcommand{\nimbleboard}[1]{
\begin{scope}[shift={(.25, .4)}]
\draw (0,-.3) -- (#1,-.3) -- (#1+.45, .7) -- (#1+.45, 1);
\draw (0,0) -- (#1,0);
\draw (.45,1) -- (#1+.45,1);
\foreach \i in {0, ..., #1} {
\draw (\i, -.3) -- (\i, 0) -- (\i+.45,1);
}
\foreach \i in {1, ..., #1} {
\node[style={font=\sffamily\scriptsize}] at (\i - .5, -.15) {\i};
}
\end{scope}
}
\newcommand{\coin}[1]{
\begin{scope}[shift={#1}]
\draw[color=white, fill=white] (-.4, 0) -- (-.4, -.1) -- (.4,-.1) -- (.4,0) -- cycle;
\draw[thick, fill=white] (0,0) ellipse (0.4 and 0.10);
\draw[thick, fill=white] (.4,-.1) arc (0:-180:0.4 and 0.10);
\draw[thick] (0.4,0) -- (0.4, -.1);
\draw[thick] (-0.4,0) -- (-0.4, -.1);
\end{scope}
}
\newcommand{\bean}[2]{
\begin{scope}[shift={#1}, rotate={#2}]
\draw [very thick, fill=gray!50] plot [smooth cycle] coordinates {(-.2,0) (-.175, .07) (-.1,.1) (0,.075) (.1,.1) (.175, .07) (.2,0) (.15, -.07) (0,-.1) (-.15, -.07)};
\end{scope}
}
\newcommand{\heap}[2]{
\begin{scope}[shift={#1}]
\draw[very thick] (0,0) circle ({#2});
\end{scope}
}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)
Section 3.4 Who Wins?
In this section, we prove that the Sprague-Grundy value of a position tells us whether it is an \(\cN\)-position or a \(\cP\)-position. We have seen some nice evidence that the Sprague-Grundy value is actually a generalization of the nim value. Indeed, our main result is analogous to Theorem 2.3.2: we are in an \(\cN\)-position if and only if the Sprague-Grundy value is nonzero.
Theorem 3.4.1.
The \(\cG\) be any combinatorial game. The game position \(X \in \cG\) is
Our proof is a streamlined form of the proof of Theorem 2.3.2. In that proof, we had an explicit formula for the nim sum, rather than a recursive definition that uses the values of the followers. Starting with that formula, we had to understand the behavior of the nim value, compared to the nim value of the followers. The recursive definition for the Sprague-Grundy value makes our general argument a breeze.
Proof.
Let \(\cA = \{ X \in \cG \mid g(X)=0 \}\) and \(\cB = \{ Y \in \cG \mid g(X) \neq 0 \}\text{.}\) If \(X \in \cA\text{,}\) then no follower of \(X\) is in \(\cA\) (because otherwise \(g(X) \neq 0\)). In other words, every follower of \(X\) is in \(\cB\text{.}\) Meanwhile, if \(Y \in \cB\) then \(g(Y) \neq 0\text{.}\) This means that there is at least one follower of \(Y\) that is in \(\cA\text{.}\) By Theorem 1.3.6, \(\cA\) is the set of \(\cP\)-positions and \(\cB\) is the set of \(\cN\)-positions.
In the next section, we will finally show that the nim value of a Nim position is identical to its Sprague-Grundy value. In other words, the Sprague-Grundy value is truly a generalization of the Nim value.