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?
The following program simulates 2000 trials of each of various lengths of curb, and displays the average number of cars fitted at that length.
The program maintains an array of available stretches of points at which the front of a newly arriving car can be placed. Initially there is just one stretch of L - 1 units at which the front of a car may be placed. (I've used the variable n rather than L.) When a car takes a spot it divides one stretch into two. In the normal circumstance the total available length decreases by 2: one unit in the portion between the front of the car and the beginning of the stretch, as no car front can any longer be in that portion even though the new car is not there, as the back would extend into the car. And the other unit is taken from the new stretch between the front of the arriving car and the end of the original stretch--this is occupied by the car itself.
The sequence of the stretches available at a given time does not matter, so an array is used rather than a linked list, so that when a segment disappears (such as a 2-unit stretch in which the front of a car is at .7) the last other segment can be brought back into the emptied slot, and contiguousness is maintained.
RANDOMIZE TIMER
DEFDBL A-Z
FOR n = 5 TO 100 STEP 5
trials = 0
numCars = 0
FOR tr = 1 TO 2000
REDIM spaceLoc(200), spaceAmt(200)
numSpaces = 1: totSpace = n - 1
spaceLoc(1) = 0: spaceAmt(1) = n - 1
'spaceLoc is the loc avalable for the Front of the car
DO
newCar = RND(1) * totSpace
covered = 0
done = 0
FOR sb = 1 TO numSpaces
IF covered + spaceAmt(sb) >= newCar THEN
done = 1
newSpace1 = newCar - covered - 1 ' this 1 is for the new buffer zone
newSpace2 = covered + spaceAmt(sb) - newCar - 1 'this 1 is for the car itself
IF newSpace1 > 0 THEN
savSpace = spaceAmt(sb)
spaceAmt(sb) = newSpace1
IF newSpace2 > 0 THEN
numSpaces = numSpaces + 1
spaceAmt(numSpaces) = newSpace2
spaceLoc(numSpaces) = newCar + 1
totSpace = totSpace - 2
ELSE
totSpace = totSpace - 1 - (savSpace + covered - newCar)
END IF
ELSE
IF newSpace2 >= 0 THEN
spaceAmt(sb) = newSpace2
spaceLoc(sb) = newCar + 1
totSpace = totSpace - (newCar - covered) - 1
ELSE
totSpace = totSpace - spaceAmt(sb)
IF numSpaces > sb THEN
spaceAmt(sb) = spaceAmt(numSpaces)
spaceLoc(sb) = spaceLoc(numSpaces)
ELSE
spaceAmt(sb) = 0
END IF
numSpaces = numSpaces - 1
END IF
END IF
EXIT FOR
END IF
covered = covered + spaceAmt(sb)
sb = sb + 1
NEXT sb
IF done THEN numCars = numCars + 1
LOOP UNTIL totSpace <= 0 OR numSpaces = 0
trials = trials + 1
NEXT tr
PRINT n, numCars / trials
NEXT n
The results for various lengths are the following average number of cars fitting:
5 3.4925
10 7.251
15 10.9605
20 14.7155
25 18.4145
30 22.14
35 25.9195
40 29.7045
45 33.3655
50 37.1205
55 40.818
60 44.6445
65 48.317
70 52.0545
75 55.8365
80 59.6075
85 63.3095
90 67.069
95 70.85599999999999
100 74.54949999999999
Toward the end of this series, 10 extra units seems to allow 7.5 additional cars, so possibly the average number of cars approaches 75% of the length of the curb as that length increases without limit. Small lengths are heavily affected by border problems:
1.75 1
2 1
2.25 1.3968
2.5 1.6682
2.75 1.85695
3 2
3.25 2.1572
3.5 2.348
3.75 2.55295
4 2.7395
4.25 2.92565
4.5 3.10855
4.75 3.2963
5 3.4826
5.25 3.67105
5.5 3.86305
5.75 4.04105
6 4.2331
6.25 4.42145
6.5 4.6023
6.75 4.8001
7 4.97775
7.25 5.1708
7.5 5.35325
7.75 5.5425
8 5.7282
8.25 5.9148
8.5 6.10445
8.75 6.28905
9 6.4756
9.25 6.65775
9.5 6.85385
9.75 7.0278
10 7.22715
10.25 7.41315
I would suggest the accuracy is good only to two positions after the decimal, rather than what might be implied by the precision shown.
In this run, each length shows the average of 20,000 trials, rather than 2,000.
|
|
Posted by Charlie
on 2004-07-02 00:16:28 |
simulation
