A Parking Problem

Consider a street of length L > 0. L is a real number. There are cars of unit length that come and park anywhere they will fit along the street (uniform distribution). (Assume that as long the available gap is >= 1, they can laterally slide in). This process continues until no more cars can be parked. What is the average number of cars that will be parked at the end of the process?

Source: Ravi Subramanianciting the following web locations.
http://www.dse.nl/puzzle/complex/index.html#car_parking
http://www.thewizardofodds.com/math/ (#105)

Solutions were received from several people. In general, it seems that a closed form solution for this problem is much to hard to calculate much beyond a street length of 4: 
0<=L<=1, N(L) = 0
1<=L<=2, N(L) = 1
2<=L<=3, N(L) = 1 + 2(L-2)/(L-1)
3<=L<=4, N(L) = [7L - 17 - 4ln(L-2)]/(L-1) [KD: I calculated this, and I'm open to correction.]
I think Joseph DeVincentis and Ravi Subramanian have good discussions of these results, and I think Philippe's final analysis is a good approximation for large L.

Update December 8, 1999. Julian Jamison found the following URL with additional analysis. It's very thorough: http://www.mathsoft.com/asolve/constant/renyi/renyi.html

Joseph DeVincentis: 

you need to take the integral over the two portions that
the road is divided into by the first car, which can have its left bumper
located at any position from 0 to x-1, uniformly.  I think this is what
the solution on that one site tried to do, though I didn't follow all
the math to determine if they did it correctly for the one specific road
length they tried to determine.  In any case, the integral is:

c(x) = Integral(c(y)+1+c(x-y-1),y=0..x-1)/(x-1)
     = 1 + Integral(c(y),y=0..x-1)/(x-1) + Integral(c(x-y-1),y=0..x-1)/(x-1)

But these last two integrals are the same by symmetry (the average
number of cars to the left of the first car is the same as the
average number of cars to the right of the first car), so:

c(x) = 1 + 2*Integral(c(y),y=0..x-1)/(x-1)

So, we end up with:

x     c(x)
0..1  0
1..2  1
2..3  1+2*(x-2)/(x-1) = 3-2/(x-1)
3..4  something awful, it has natural logs in it from integrating the above.

Philippe's solution may be an interesting approximation for long roads,
but it is so difficult to expand the analytical solution to more than
about 5 that it can probably only be checked by monte carlo methods.
Ravi Subramanian: [KD: I asked Ravi to help explain how the integral came to be in the solution] 
Truly the integral does not appear suddenly at 4.  All results for
L >= 1, can be expressed using the integral method.

I will call the end car that is closer to 0 as the head of the car.

0. N(L) is defined only for N >= 0.
1. It is obvious that N(L) for L< 1, N(L) = 0.
2. Now let us consider L >= 1.
    Let us consider the cases where the first car parks, such that
it head is in range (x,x+dx) where dx is infinitesimal.
    Now we have 1 car parked and 2 sections of the street of
length x and (L - 1 - x) respectively (ignoring dx).
    The probability that the first car parked as above is dx / (L
- 1), because its head could have been anywhere in (0,L-1) and we
are considereing only a segment dx long.

So we can write the contribution to N(L) as (1 + N(x) + N(L - 1 - x)) * dx / (L - 1)
Summing for all values of x in range (0, L-1) or in other words integrating, we get
N(L) = I[0, L-1, 1]dx / (L-1) + I[0, L-1, N(x)]dx / (L-1) + I[0, L-1, N(L - 1 - x)]dx / (L-1)

Let us call these terms I1, I2, I3 respectively.

I1 = I[0, L-1, 1]dx / (L-1) = (L-1) / (L-1) = 1.

Let use change of variables in I3.
Let y = (L - 1 - x)
dy = -dx.
The limits become (L-1) and 0. (lower and upper resply).
I3 = -I[L-1, 0, N(y)]dy / (L-1)
Swapping limits and removing -ve sign
I3 = I[0, L-1, N(y)]dy / (L-1)  = I[0, L-1, N(x)]dx / (L-1) = I2

so N(L) = 1 + 2 / (L - 1) * I[0, L-1, N(x)]dx

O.K.

Now let us evaluate N(L) for 1<= L < 2.
N(L) = 1 + 2 / (L - 1) * I[0, L-1, 0]dx    because N(x) = 0 for
0<=x<1.
= 1 (which is correct).

For 2<= L< 3
N(L) = 1 + 2 / (L - 1) * { I[0, 1, 0]dx + I[1, L-1, 1]dx}
= 1 + 2 / (L - 1) * {0 + L - 2}
= 1 + 2 * (L - 2) / (L - 1) (same as Shackleford's result)

For 3<= L < 4, Shackleford's solution is correct (and involves ln
as Joseph De Vincentis has pointed out)

Incidentally what I have explained here is exactly the same has
what Joseph De Vincentis has done.
Philippe Fondanaiche makes a good argument: 
I have spent a lot of time by using desperately the theory of probability in 
order to find out the general law of the intervals between two cars and their 
expectation value. As I has failed with the theory, I have succeeded to get 
an answer from my computer which, thanks to a short program using a random 
function, has given integer(3*L/4) but the computer has not demonstrated 
anything.....
Finally,I suggest this simple solution:
 Let assume that L is large enough ( at the minimum L>7) and let consider a 
car parked between the abscissa X and X+1.It is easy to check that :
  - in the interval [X+1, X+4] as well as in the interval [X-3, X], each of 
them 3 long and adjacent to the car, two cars can be parked (the probability 
of parking 3 cars being nil). If the interval are 3-epsilon long,in some 
cases one car only can be parked.
  - as the cars are fitted according to an uniform distribution,the average 
distance between 2 adjacent cars in each interval [X+1, X+4] or [X-3, X] is 
equal to 1/3.
So whatever the rank of the car in the parking, there are 3 cars in each of 
the intervals [X-3, X+1] and [X, X+4] which are 4 long.If there are k cars, 
there are k+1 intervals and the following equation gives the relationship 
between k and L : k + (k+1)/3 = L . Therefore k = (3*L-1)/4.

PS For the low values of L, it is better to consider the probabilistic model 
as developed by M.Shackleford for L=4.
Mail to Ken