Ponder This Challenge - September 2012 - Parking game

Ponder This Challenge:

Remember the June 2011 challenge? It was about parking two units long cars along the circumference of a circle with one unit long segments.

We now change this parking challenge into a two players game, where each player parks a car in turn. The first player unable to park a car (i.e., when all the remaining spaces are only one-unit-long intervals) loses.

If the size of the parking area is 11 units, the first player has a winning strategy.

Find another possible size of the parking space, N, for which the first player has a winning strategy and N consists only of the digits 0 and 1.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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.

Solvers

• Luke Pebody (09/04/2012 01:36 PM EDT)
• Jochen Voß (09/04/2012 03:05 PM EDT)
• Peter and David de Rivaz (09/04/2012 03:21 PM EDT)
• Florian Fischer (09/04/2012 03:59 PM EDT)
• Deane Stewart (09/04/2012 05:51 PM EDT)
• Tom Sirgedas (09/04/2012 06:14 PM EDT)
• Chuck Carroll (09/04/2012 08:25 PM EDT)
• Guangda Huzhang (09/05/2012 03:51 AM EDT)
• Kevin Sham (09/05/2012 04:35 AM EDT)
• Jan Fricke (09/05/2012 07:56 AM EDT)
• Septimus G. Stevens, VII (09/05/2012 02:40 PM EDT)
• Joseph DeVincentis (09/05/2012 03:22 PM EDT)
• Todd Will (09/05/2012 03:48 PM EDT)
• Leslie Cheng (09/05/2012 09:56 PM EDT)
• Alex Stangl (09/06/2012 02:07 AM EDT)
• Deron Stewart (09/06/2012 02:38 AM EDT)
• Lewei Weng (09/06/2012 03:05 AM EDT)
• Øyvind Grotmol (09/06/2012 11:01 AM EDT)
• Jamie Jorgensen (09/06/2012 05:36 PM EDT)
• Jason Lee (09/06/2012 09:26 PM EDT)
• Fletcher Dostie (09/06/2012 10:10 PM EDT)
• Shilei Zang (09/07/2012 10:00 AM EDT)
• Denys Kopiychenko (09/07/2012 11:55 AM EDT)
• Karl D'Souza (09/07/2012 02:06 PM EDT)
• Sergey Grishaev (09/09/2012 06:37 PM EDT)
• John Tromp (09/10/2012 11:43 AM EDT)
• Christian Pape (09/11/2012 08:55 AM EDT)
• Adrian Orzepowski (09/12/2012 04:32 PM EDT)
• Christian Blatter (09/13/2012 08:00 AM EDT)
• Dan Dima (09/13/2012 11:18 AM EDT)
• Thomas Mack (09/13/2012 07:28 PM EDT)
• Shouky Dan & Tamir Ganor (09/14/2012 04:38 PM EDT)
• Alex Wagner (09/14/2012 07:20 PM EDT)
• Levon Haykazyan (09/15/2012 08:47 AM EDT)
• Gale Greenlee (09/17/2012 01:05 PM EDT)
• Armin Krauss (09/17/2012 01:35 PM EDT)
• Joshua Small (09/17/2012 07:33 PM EDT)
• Albert Stadler (09/18/2012 05:02 AM EDT)
• Balakrishnan Varadarajan (09/18/2012 02:03 PM EDT)
• Taketsuna Hisaji (09/18/2012 05:06 PM EDT)
• Lorenzo Gianferrari Pini (09/19/2012 06:46 PM EDT)
• Tony Harrison (09/20/2012 01:20 PM EDT)
• Andreas Razen & Radu-Alexandru Todor (09/20/2012 02:30 PM EDT)
• Erik Hostens (09/21/2012 09:54 AM EDT)
• Rainer Rosenthal (09/22/2012 04:13 AM EDT)
• Duane A. Bailey (09/24/2012 01:00 AM EDT)
• Ehud Schreiber (09/24/2012 10:55 AM EDT)
• Stephen Locke & Phil Benamy (09/24/2012 04:55 PM EDT)
• Stephen Morris (09/26/2012 09:46 AM EDT)
• Dan Arnon (09/27/2012 10:17 PM EDT)
• Stéphane Higueret (09/29/2012 04:12 AM EDT)
• Avishalom Shalit (09/29/2012 08:26 PM EDT)
• Daniel Bitin (09/30/2012 07:31 PM EDT)