There is an east-west street of length L units. And we park cars of unit length along the north side until we can't place any more cars. Each car is placed randomly (uniformly).

What is the expected number of cars that can be parked (as a function of L)?
__________________________

I'll start you off...

For 0 <= L < 1, F(L) = 0
For 1 <= L < 2, F(L) = 1

Okay... now the easy ones are out of the way, can you describe the function for L>=2?

Using a basic sort of greedy algorithm, observe that for an integer length street, the minimum number of parked cars is the floor of half the street length, and the maximum is the length. So in essence, as L increases the function seems to change.

Much like the birds on a wire puzzle of a few weeks ago, I don't think a closed-form solution exists for all values of L.

Posted by Eric on 2004-07-01 14:33:15