IBM Ponder This June 2011 Parking Expected Capacity
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?
Spent a day working on a recursive solution in matlab that only worked well for small values of n (number of parking spaces). Ended up only calculating it for 30 parking spaces and using linear regression to extrapolate. The trend is surprisingly linear.
Anyone got an elegant solution?Puzzle Source : IBM