## The subtraction game

In the subtraction game, two players start with a pile of chips and they alternate taking away any number $s_i$ (from a previously fixed set $S = \{s_1, \ldots, s_t\}$ of positive integers) of chips from the pile. If you can’t make a move anymore, because there are less chips left than the smallest member of $S$, you lose. This game has been solved in the case $|S| = 2$, but thus far hasn’t been solved in general when $|S| > 2$, although some partial results are known. For example, it is known that for any set $S$ there exists an $m$ such that for large enough $n$, if you start with $n$ chips, the question if this game is a win for Player $1$ only depends on $n \pmod m$. That is, the sequence of $n$ such that Player $1$ wins if the starting pile consists of $n$ chips, is ultimately periodic. I think I found the period and the corresponding nimvalues (http://en.wikipedia.org/wiki/Nim-sequence) of the periodic parts, assuming $S = \{1, a, b\}$. No explanation or anything, just stating what I think are the correct values. Maybe I’ll explain what the hell I’m talking about in a future post. Maybe not 😉

Let $b = c*(a+1) + k$, where $c \ge 1$ and $0 \le k \le a$. Then the periodic part of the nimsequence is as follows:

$01$, if

$a$ is odd
$b$ is odd

$(01)^{b/2} (23)^{(a-1)/2} 2$, if

– $a$ is odd
$b$ is even

Notice: thus far we’ve handled all cases with $a$ odd. This was known before, check for example http://arxiv.org/pdf/1202.2986.pdf.

$(012)^c 3$, if

$a = 2$
$k = 0$

$(01)^{a/2} 2$, if

$a$ is even
$k \in \{1, a\}$

$((01)^{a/2} 2)^{c+1} (32)^{(k-1)/2}$, if

$a$ is even
$k$ is odd
$1 < k < a$

Note: now we handled all cases with $a$ even and $k$ odd.

$((01)^{a/2} 2)^c (01)^{a/2-1}2$, if

$a \ge 4$ is even
$k = a - 2$

Note: and now we’re also done with $k \ge a - 2$.

$(01)^{a/2} (23)^{a/2}$, if

$a$ is even
$k = 0$
$c = 1$

$(01012)^{c-1} (012)^2$, if

$a = 4$
$k = 0$
$c > 1$

And now we’re also completely done with $a = 4$. All that’s left now is the case $a \ge 6$ even and $k < a-2$ even, where if $k = 0$, $c > 1$. We will split this case in three: either $k$ exactly equals $a - 2c - 2$, or $k > a - 2c - 2$, or $k < a - 2c - 2$, and in this last case we have to distinguish between $k = 0$ or $k > 0$. Here goes.

$2(01)^{a/2-1}$, if

$a \ge 6$ is even
$k$ is even
$k = a - 2c - 2$

$2(01)^{a/2-1} (2 (01)^{a/2})^{c - a/2 + k/2 + 1} (2(01)^{a/2 - 1})^{a/2 - k/2 - 1}$, if

$a \ge 6$ is even
$k$ is even
$a - 2c - 2 < k < a - 2$

$(23)^{a/2-c-1} 2(01)^c (2 (01)^{a/2 -1})^c 2(01)^c$, if

$a$ is even
$k = 0$
$k < a - 2c - 2$
$c > 1$
– Using the fact that $k = 0$, these last two assumptions can be written as: $1 < c < a/2 - 1$

$(23)^{a/2 - k/2 - c - 1} 2 (01)^{k/2 + c} (2 (01)^{a/2 - 1})^{c} 2 (01)^{k/2 + c}$, if

$a$ is even
$k$ is even
$0 < k < a - 2c - 2$