wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Car parking
        
(Message started by: towr on Jan 31^st, 2008, 8:39am)

Title: Car parking
Post by towr on Jan 31^st, 2008, 8:39am

You have a circular parking lot that would fit N cars, if only they would park them neatly next to each other. However, there are no individual spaces marked out for each car, so everyone just parks somewhere on the circle where there's room.

How many cars would you expect there to be parked when the lot is full?

(The usual mathematical abstractions apply: the lot is a circle with circumference N, and each car is an arc of length 1 on such a circle with, cars are placed according to a uniform distribution over the available space.
You can generalize for non-integer N, if you prefer.)

Title: Re: Car parking
Post by Joe Fendel on Jan 31^st, 2008, 9:55am

My inclination would be:

1) Yes, only work in the generalization for non-integer N.
2) Work on the problem for a linear parking lot instead, since then:
2a) The circular problem with N cars is equivalent to the 1 + linear problem with N-1 cars, since after the first car is parked that's what's left
2b) We can recurse - parking a car in a lot of size N leaves two linear lots of combined size N-1.

But I'm not sure how to work out the details of the recursion at first glance.

Title: Re: Car parking
Post by Eigenray on Jan 31^st, 2008, 5:01pm

I think if E(x) is for a linear lot of length x, then for 0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif t http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 1,

E(t) = 0
E(1+t) = 1
E(2+t) = [ 3t + 1 ] / [ 1 + t ]
E(3+t) = [ 4 + 7t - 4log(1+t) ] / [ 2 + t ]
E(4+t) = [ 11 - 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif²/3 + 16log(2) + 15t - 4(5+2log(1+t))log(2+t) + (2log(2+t))² + 8PolyLog[2,(1+t)/(2+t)] ] / [ 3 + t ]

~~[hide]Laplace[/hide] would probably work.~~ (Maybe [link=http://mathworld.wolfram.com/RenyisParkingConstants.html]not[/link].)

If we write E(x) = m(x)(x+1) - 1, i.e., F(x+1) = m(x)(x+1), where F(x) is for a circular lot of length x, then
m(1) = 0.5
m(2) = 0.67...
m(3) = 0.75
m(4) = 0.7485...
m(5) = 0.74751...
m(6) = 0.7475982...
The limiting value is actually 0.7475979202...