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.

  • $\begingroup$ What is mex function? $\endgroup$ Sep 30 '17 at 2:48
  • 1
    $\begingroup$ mex is "minimal excludent", the smallest positive integer not in the set @AlexRavsky This comes from Conway's On Numbers and Games. $\endgroup$ 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.