Ponder This Challenge - June 2011 - Parking density

Ponder This Challenge:

The winner of the IBM Global Entrepreneur of the Year contest for 2010 was Streetline (see here details and a great six-minute pitch on their innovative parking system), so we decided to focus this month's challenge on parking.

This challenge is based on a puzzle we heard from Yaniv Shmueli, who heard it himself a few years ago.

Let's assume that cars have a length of two units and that they are parked along the circumference of a circle whose length is 100 units, which is marked as 100 segments, each one exactly one unit long.

A car can park on any two adjacent free segments (i.e., it does not need any extra maneuvering space).

Our question is as follows: Let's assume that we start with an empty circle. We add one car at a time, and each car parks in a random free space (aligned to a unit length), till no such place exists. What is the expected number of cars that can park along that 100-unit-long circle?

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

  The first car can park in any spot, transforming the 100-unit-long circle into a 98-unit-long segment. Denote by f(n) the expected number of cars that can park in a segment of n units.

  f(0) = f(1) = 0, since there is not enough space for a 2-unit-long car and
  f(n+1) = 1 + {2\over n}\sum_{i=0}^{n-1} f(i).

  Many of you just wrote a simple program to compute f(98), which is approximately 42.23; some of you used generating function methods to compute the answer; and a few of you gave the *exact* solution:

  699873064207163672981688052775691404824955584422721836264226250973752499660
  28469857171531088252341276109306476631593119274564 / 1618831092881708654907243444916671169624056573581564142797360830774247469534
  546482996222387966854760679126713275909423828125 = 43.233235838169....

  Many of you noticed that f(n) is very close to (n/2)(1-1/e^2)-1/e^2, and one of you even programmed it as a game (link resides outside of ibm.com).

  Joe Riel even waited till the end of June and posted a solution (link resides outside of ibm.com).

  Arthur Breitman was the first to send us a closed formula, but we choose to quote Michael Brand's proof for it:

  f(n) = 0.5*(n-(n-2)*(-2)^(n-3)/(n-3)!-n \sum_{k=0}^{n-4} (-2)^k/k!)

  His proof: Instead of counting parked cars, one can just as easily calculate the expected number of free parking spaces at the end of the process.
  For each parking space, we calculate the probability for it to remain empty.
  We then sum all probabilities to arrive at the expectation.
  The probability for a parking space with x free parking spaces to its left and y free parking spaces to its right to remain empty can be described by the following 2D-recursive formula: p(x,y)=(\sum_{i=0}^{x-2} p(i,y) + \sum_{i=0}^{y-2} p(x,i))/(x+y). (To derive this formula, consider what happens after the first car parks inside this free interval.)
  The 2D recursion can be solved more simply using a regular 1D recursion if one takes into account that the probabilities relating to the free parking spaces to the left are independent from those relating to the parking spaces on the right.
  The solution is p(x,y)=D_x D_y, where D_k=\sum_{i=0}^{k} (-1)^i / i!, and from it the formula above can be derived directly.

  However, we received the best solution from Austin Shapiro, who referenced an old paper (link resides outside of ibm.com) and sent us an elegant and concise original proof, which we enclose here as is (in his perfect handwriting):

  Austin Shapiro Solution (184KB)

  Notes on the continuous version of this problem can be seen here (link resides outside of ibm.com).

Solvers

• Dan Dima (05/31/2011 03:21 PM EDT)
• Chase Albert (05/31/2011 03:34 PM EDT)
• David Friedman (05/31/2011 04:22 PM EDT)
• Bill Baker (05/31/2011 05:30 PM EDT)
• Bryan Wolf (05/31/2011 05:32 PM EDT)
• Jon Evans (05/31/2011 05:39 PM EDT)
• John T. Robinson (05/31/2011 06:04 PM EDT)
• Matt Dobrin (05/31/2011 06:31 PM EDT)
• Mark Perkins (05/31/2011 08:34 PM EDT)
• Shilei Zang (05/31/2011 09:48 PM EDT)
• Leif Jensen (06/01/2011 01:03 AM EDT)
• Andrea Andenna (06/01/2011 01:03 AM EDT)
• Jonathan Campbell (06/01/2011 02:56 AM EDT)
• Ted Hench (06/01/2011 03:21 AM EDT)
• Bi Suzhi (06/01/2011 03:43 AM EDT)
• Utkarsh Upadhyay (06/01/2011 07:32 AM EDT)
• Florian Fischer (06/01/2011 09:49 AM EDT)
• Arthur Breitman (06/01/2011 11:12 AM EDT)
• Vladimir Sedach (06/01/2011 11:46 AM EDT)
• Daniel Zev (06/01/2011 12:09 AM EDT)
• Nick Vigo & Kipp Johnson (06/01/2011 12:15 PM EDT)
• Eric R. Farmer (06/01/2011 12:43 PM EDT)
• Donald T. Dodson (06/01/2011 01:23 PM EDT)
• Joseph DeVincentis (06/01/2011 01:43 PM EDT)
• Jochen Voß (06/01/2011 02:21 PM EDT)
• Danny Leshem (06/01/2011 03:06 PM EDT)
• John Tromp (06/01/2011 03:48 PM EDT)
• Álvaro Begué (06/01/2011 04:31 PM EDT)
• Hamidreza Bidar (06/01/2011 05:48 PM EDT)
• Vignesh Sethuraman (06/01/2011 08:55 PM EDT)
• Harald van Dijk (06/01/2011 09:43 PM EDT)
• Phil Benamy (06/01/2011 10:00 PM EDT)
• Jing-yu Cui (06/01/2011 11:25 PM EDT)
• Brian Bitto (06/02/2011 12:26 AM EDT)
• James Dow Allen (06/02/2011 01:27 AM EDT)
• Piet Orye (06/02/2011 05:11 AM EDT)
• Alex Krusz (06/02/2011 06:19 AM EDT)
• Donald Laackman (06/02/2011 06:45 AM EDT)
• Jan Fricke (06/02/2011 07:36 AM EDT)
• Chen Wei (06/02/2011 09:09 AM EDT)
• Christian Blatter (06/02/2011 09:15 AM EDT)
• Bob Frank (06/02/2011 09:45 AM EDT)
• Josh Small (06/02/2011 09:58 AM EDT)
• Ariel Landau (06/02/2011 05:33 PM EDT)
• Jörg Härterich (06/02/2011 06:47 PM EDT)
• Ernest Zeidman (06/02/2011 07:33 PM EDT)
• Austin Shapiro (06/02/2011 08:54 PM EDT)
• aman_cc (06/03/2011 06:10 AM EDT)
• Pengyu Chen (06/03/2011 11:01 AM EDT)
• Owen Wright (06/03/2011 05:01 PM EDT)
• Wenxun Huang (06/03/2011 08:28 PM EDT)
• Sriram Sankaranarayanan (06/03/2011 08:51 PM EDT)
• Nick McGrath (06/04/2011 01:00 AM EDT)
• Clive Tong (06/04/2011 01:08 PM EDT)
• Motty Porat (06/04/2011 04:50 PM EDT)
• Karthik Kalyanam (06/04/2011 05:08 PM EDT)
• Jason Crease (06/04/2011 05:29 PM EDT)
• Sylvain Becker (06/04/2011 05:51 PM EDT)
• Anthony Helmstetter (06/04/2011 06:39 PM EDT)
• Siddharth S (06/05/2011 03:58 AM EDT)
• Amos Guler (06/05/2011 03:59 AM EDT)
• Vijay Comsci (06/05/2011 05:02 AM EDT)
• Or Zuk (06/05/2011 09:31 AM EDT)
• Thijmen Krebs (06/05/2011 04:29 PM EDT)
• Mark Mixer (06/05/2011 04:51 PM EDT)
• Sergei Agievich (06/05/2011 06:24 PM EDT)
• Blacklight (06/05/2011 11:20 PM EDT)
• Robert C. Sarvis (06/05/2011 11:41 PM EDT)
• Maris Van Sprang (06/06/2011 04:45 AM EDT)
• Lu Wang (06/06/2011 11:51 AM EDT)
• Daniel Bitin (06/06/2011 01:59 PM EDT)
• Ryan Manuel (06/06/2011 04:46 PM EDT)
• Ian Smith (06/06/2011 05:55 PM EDT)
• Joseph Bonneau (06/06/2011 07:40 PM EDT)
• Jon Namnath (06/06/2011 08:35 PM EDT)
• John Snyder (06/06/2011 11:59 PM EDT)
• Kiyoto Tamura (06/07/2011 01:21 AM EDT)
• Michael Brand (06/07/2011 0600 AM EDT)
• John Schanck (06/07/2011 04:28 PM EDT)
• Teemu Stenhammar (06/07/2011 05:28 PM EDT)
• Joe Riel (06/07/2011 09:09 PM EDT)
• Liubing Yu (06/08/2011 06:08 AM EDT)
• Mehmet Sariyuce & Umut Uludag (06/08/2011 09:00 AM EDT)
• George Savvas (06/09/2011 12:12 AM EDT)
• William Heller (06/09/2011 01:48 AM EDT)
• Serge Thill (06/09/2011 11:53 AM EDT)
• Evert van Dijken (06/10/2011 04:24 AM EDT)
• Guoxin Zhang (06/10/2011 01:33 PM EDT)
• Balakrishnan V (06/11/2011 03:21 PM EDT)
• Jeff Steele (06/11/2011 08:02 PM EDT)
• Anoop Ghanwani (06/12/2011 03:27 AM EDT)
• Joseph Calzaretta (06/12/2011 10:14 PM EDT)
• Yaniv Meoded (06/13/2011 06:12 AM EDT)
• Sandeep Rathour (06/13/2011 08:31 AM EDT)
• Miss Shawn Simpson (06/13/2011 02:11 PM EDT)
• Algirdas Rašcius (06/13/2011 05:39 PM EDT)
• Miguel Cuartas Hernández (06/15/2011 03:59 AM EDT)
• Joseph Manger (06/16/2011 08:28 AM EDT)
• Jonathan Fader (06/16/2011 10:46 AM EDT)
• Ariel Flat (06/16/2011 01:45 PM EDT)
• Sam Vercauteren (06/16/2011 09:06 PM EDT)
• Chris Hills (06/16/2011 09:17 PM EDT)
• John G Fletcher (06/17/2011 01:52 AM EDT)
• Kaverappa O T (06/17/2011 06:09 AM EDT)
• Daniel Jaouen (06/19/2011 03:14 AM EDT)
• Gale Greenlee (06/20/2011 01:10 PM EDT)
• Ilya Khivrich (06/20/2011 06:29 PM EDT)
• Andrew Buchanan (06/21/2011 02:31 PM EDT)
• Charles Ward (06/22/2011 02:08 PM EDT)
• Soumitra Pal (06/22/2011 03:59 AM EDT)
• Yifei Wu (06/22/2011 04:36 PM EDT)
• Reiner Martin (06/24/2011 06:25 AM EDT)
• Daniel Camero (06/24/2011 11:16 AM EDT)
• Gil Dollberg (06/24/2011 04:35 PM EDT)
• Ante Kovacic (06/24/2011 06:25 PM EDT)
• Frederik Kaster (06/25/2011 11:33 AM EDT)
• Yuyuan Ouyang (06/25/2011 04:09 PM EDT)
• Taher Jamshidi (06/26/2011 12:10 PM EDT)
• Li Xu (06/27/2011 05:43 AM EDT)
• Ashray Urs (06/27/2011 03:19 PM EDT)
• Mauro Bampo (06/28/2011 02:26 AM EDT)
• Albert Stadler (06/28/2011 12:52 PM EDT)
• Rob Pratt (06/28/2011 05:48 PM EDT)
• Chris Shannon (06/28/2011 08:33 PM EDT)
• Robert Buckley (06/29/2011 01:13 PM EDT)
• Jintao Yin (06/30/2011 02:31 AM EDT)
• David Tam (06/30/2011 02:53 AM EDT)
• Franza Cavalcante Jr (06/30/2011 06:20 PM EDT)
• Rogerio Ponce da Silva (07/01/2011 05:04 AM EDT)
• Hakan Summakoglu (07/01/2011 03:17 PM EDT)
• Ehud Schreiber (07/03/2011 09:05 AM EDT)
• Aviv Nisgav (07/06/2011 06:24 AM EDT)