Archive for June, 2014

The subtraction game

June 26, 2014

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