100 sequential parking spaces

Question

I just came up across this question in the mathematics stack exchange site and found it quite interesting:

100 autonomous robotic vehicles enter a warehouse in random order to park. Inside the warehouse, there are 100 sequential parking spaces enumerated from 1 to 100. Each vehicle has an assigned number where it will attempt to park. However, there is an error in the programming such that if a vehicle finds its path to the assigned parking spot blocked by an already-parked robot, the robot will immediately park in the spot before it. For example, if vehicle 50 parks in spot 50 but vehicle 75 is immediately behind it, vehicle 75 will park in spot 49. Also, if vehicle 1 parks in spot 1, every robot behind it will be blocked from entering the warehouse at all. The vehicles do not have the ability to maneuver around already-parked vehicles.

What is the most likely number of robots that will be parked in the warehouse at the end of the routine?

Answer 1

I decided to brute force the problem by writing a quick program.

using System;
using System.Collections.Generic;
using System.Linq;

public class Test
{
    static readonly int NUMROBOTS = 100;
    static readonly int ITERATIONS = 1000000;
    static Random rng = new Random();

    int FindParking()
    {
        int free = NUMROBOTS; // # of largest free spot
        int count = 0; // Number of robots parked

        var robots = Enumerable.Range(1, NUMROBOTS).ToList();
        // Shuffle list
        int n = robots.Count;
        while (n > 1)
        {  
            n--;  
            int k = rng.Next(n + 1);  
            int value = robots[k];  
            robots[k] = robots[n];  
            robots[n] = value;  
        }

        while (free > 1)
        {
            if (free > robots[count])
                free = robots[count]; // Robot found its spot
            else
                free--;               // Spot is filled
            count++;
        }
        return count;
    }


    public static void Main()
    {
        var p = new Test();
        int total = 0;
        for (int i = 0; i < ITERATIONS; i++)
        {
            total += p.FindParking();
        }
        Console.WriteLine("Average robots parked: {0} ({1} iterations)", (decimal)total / ITERATIONS, ITERATIONS);
    }
}

Average robots parked: 11.920253 (1000000 iterations)

I'd like to see the math for this, though.

Answer 2

I would guess around 18 cars. If we assume that average placement of a car in the empty lot is 1/2 way up, then we can make some assumptions as to where the cars are placed and how many are placed ahead of it.

• First car is at 50. (1)
• Next car is at 25, but before that car parks, there is a 50% chance (repeating) that a car is at 50+ and so is placed right after the 50. That averages out to 1 extra car. (3)
• The next car is at 12, but before it parks this time there's a 75% chance of a car at 25+. That averages out to 3 extra cars. (7)
• Here's where it gets a little tricky. You have ~7/8 chance of the next car being above 12, but there are only 12 places left. You could do the math to get an average of 8 cars in this scenario, which puts you down to spot 4 (15)
• At that point, you have 3 spots left, but a really high chance of picking a car ahead of 3. So, we can just say they're fully filled (18)