All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Parking Cars (Posted on 2004-07-01) Difficulty: 5 of 5
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?

No Solution Yet Submitted by SilverKnight    
Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts simulation | Comment 7 of 14 |

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information