# Sprage-Grundy function periodicity for finite substraction games

I've currently working through the following problem: consider the game of subtraction, an impartial combinatorial game which consists of a pile of $k$ coins from which two players take turns to remove a ceratin amount $s \in S$ with $S \subseteq \mathbb{N}_0$ a fixed set.

This can be modeled as a graph $\mathbb{X}$ of the possible starting positions and an adjacency function $F$ where

$$\mathbb{X} = \mathbb{N}_0 \\ F(x) = \{x - s : s\in S\} \cap \mathbb{N}_0$$

Now, in order to find optimal strategies, we want to consider the graph's Sprague-Grundy function,

$$g(x) = mex\{g(y) : y \in F(x)\}$$

The question I'm trying to tackle is the following

Prove that if S is finite, there exists $n_0 \in \mathbb{N}_0$ such that the S-G function is periodic for $n >n_0$ .

So far I've tried to prove this by induction on $\#S$ and by contradiction, trying to see that if the S-G function is not periodic then necessarily $\#S \geq \aleph_0$, none of which were successful.

In both cases I've been fiddling with the fact that if the Sprague-Grundy function is not eventually periodic, then for any $m \in \mathbb{N}$, there exists $(a^{(m)}_n)_{n \in \mathbb{N}}$ such that $g(a^{(m)}_n) \neq g(a^{(m)}_n + m).$ If not, there would exist a period $m$ for which at a certain point $n_0$, no elements beyond it can be chosen such that the inequality holds, and $g$ would indeed be eventually periodic.

Is this the correct approach? Any ideas beyond this one? Any help is appreciated.

• What is mex function? Sep 30 '17 at 2:48
• mex is "minimal excludent", the smallest positive integer not in the set @AlexRavsky This comes from Conway's On Numbers and Games. Sep 30 '17 at 3:31

Since the set $S$ is finite, for each $x$ and $y$ we have $|\{g(y) : y \in F(x)\}|\le |S|$, so $g(x)=\operatorname{mex}\{g(y) : y \in F(x)\}\le |S|+1$. For each $x>\max S$ value of $g(x)$ is completely determined by values of $g(y)$ at the segment $[x-\max S, x-1]$. Since there are only finitely many ways to fill a discrete segment of length $\max S$ by numbers not bigger than $|S|+1$, by pigeonhole principle there exists natural $n_0$ and $t$ such that $g(n_0+i+t)=g(n_0+i)$ for each $0\le i\le |S|+1$. Then $g(n_0+i+t)=g(n_0+i)$ for each natural $i$.