September 2012
We received a comprehensive answer from Chuck Carroll that we provide below verbatim, but before that, two comments:
- Øyvind Grotmol suggested taking 1,000 ones in a row: (10**1000-1)/9 as a solution.
- Talk about incredibly large parking lots: Luke Pebody noted that if A is any positive integer that is at least 2, B is the number you get by repeating 1 A times, C is the number you get by repeating 10 B times, and N is the number you get by repeating 1 C times, then the first player has a winning strategy for N.
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.
Additional observations:
Except for the trival case of N=2, the second player has a simple winning strategy if N is even; he simply parks each car in the spaces directly opposite the first player's placement.
This game appears to be isomorphic to Dawson's Chess (described in Sec. 4.4, game 3, of the paper linked above) with M-1 (N-3) files, with the first player of Dawson's Chess corresponding to the second player of the car-parking game. This is most apparent in the description given in the second paragraph there: a row of spaces which players take turns marking one at a time, subject to the restriction that two adjacent spaces may not be marked. The spaces in that game correspond to the lines between spaces in the car-parking game; marking a space in that game corresponds to parking a car centered on the corresponding line in our game.
For example, the case of N=1111 (spaces in the circular track), which is M=1109 (spaces in the linear track after the first move) corresponds to Dawson's Chess with 1108 files, with the first player of Dawson's Chess corresponding to the second player in the car-parking game. The Sprague-Grundy sequence for Dawson's Chess is the same as that given above, offset by one.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com