IBM Research | Ponder This | September 2012 solutions

# Ponder This

## September 2012

<<August September October>>

We received a comprehensive answer from Chuck Carroll that we provide below verbatim, but before that, two comments:

Here's Chuck's solution:

The first player has only a single initial move, breaking the circle of N spaces into a linear path of N-2 spaces.

Since all further moves will create only additional linear segments, let us define M=N-2 and analyze the game in terms of linear segments.

The game can be analyzed in terms of the Sprague-Grundy function - see http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf (PDF, 348KB), especially Chapters 3 and 4, for details.

Let F(m) be the Sprague-Grundy function for a single length of m spaces, and let F(m1, m2, m3, ...) be the Sprague-Grundy function for a set of lengths of spaces of length m1, m2, m3, ...

The Sprague-Grundy function for a set of lengths is equal to the bitwise-XOR (represented here as ^) of the Sprague-Grundy functions of the individual lengths, i.e., F(m1, m2, m3, ...) = F(m1) ^ F(m2) ^ F(m3) ...

The Sprague-Grundy function for a single length of track is defined to be 0 for positions with no further moves possible (m=0 or m=1); for other values, it is defined as the smallest non-negative integer that is not among the set of (mex) the Sprague-Grundy functions of all possible positions following the next move, i.e., F(m) = mex {F(m-2),F(1)^F(m-3),F(2)^F(m-4), ...}

For example, given F(1) through F(10), we can calculate:

F(12) = mex{F(10),F(1)^F(9),F(2)^F(8),F(3)^F(7),F(4)^F(6),F(5)^F(5)}
= mex{1,0^0,1^1,1^1,1^2,1^1}
= mex{1,0,0,0,3,0}
= 2

Additionally, the Sprague-Grundy function is zero if the game is lost by the player with the next move, and non-zero if it is won by the player with the next move, with ideal play. Therefore., a player should leave a position with a Sprague-Grundy function zero if possible.

Values of F(m) for m=0 to 86:
m F(m)
-- ----
0    0
1    0
2    1
3    1
4    2
5    0
6    3
7    1
8    1
9    0
10    3
11    3
12    2
13    2
14    4
15    0
16    5
17    2
18    2
19    3
20    3
21    0
22    1
23    1
24    3
25    0
26    2
27    1
28    1
29    0
30    4
31    5
32    2
33    7
34    4
35    0
36    1
37    1
38    2
39    0
40    3
41    1
42    1
43    0
44    3
45    3
46    2
47    2
48    4
49    4
50    5
51    5
52    2
53    3
54    3
55    0
56    1
57    1
58    3
59    0
60    2
61    1
62    1
63    0
64    4
65    5
66    3
67    7
68    4
69    8
70    1
71    1
72    2
73    0
74    3
75    1
76    1
77    0
78    3
79    3
80    2
81    2
82    4
83    4
84    5
85    5
86    9

After this point, F(m) repeats with period 34, e.g., F(87)=F(53); F(88)=F(54)...

Thus, values that are won for the first player include those where M is congruent to 5, 9, 21, 25, or 29 mod 34. Since N=M+2, values of N congruent to 7, 11, 23, 27, or 31 mod 34 are won for the first player. (In addition, non-repeating values of N won for the first player are 2, 3, 17, and 37.)

Values of N that meet this criterion, and for which N consists only of the digits 0 and 1, include 1111, 11111, 100001, 101011, 110001, and 111101.