The 538 Riddler: Air Travel Nightmare

So last week’s Riddler was a good news/bad news situation. The bad news is that I was wrong, although I did illustrate the correct answer in a follow-up post. The good news is that I still managed to get a shout-out from Ollie in this week’s Riddler, even earning the honorary title of FotR, which I hope means Friend of the Riddler.

Anyway, this week’s Riddler concerns the worst person alive and a full airplane.

There’s an airplane with 100 seats, and there are 100 ticketed passengers each with an assigned seat. They line up to board in some random order. However, the first person to board is the worst person alive, and just sits in a random seat, without even looking at his boarding pass. Each subsequent passenger sits in his or her own assigned seat if it’s empty, but sits in a random open seat if the assigned seat is occupied. What is the probability that you, the hundredth passenger to board, finds your seat unoccupied?

So the answer is 1/2, half, 50%, however you want to say it. And this is true for the last passenger no matter how many passengers are on a (full) plane. I actually worked this out before writing any code (but don’t worry, I still wrote the code!) It’s trivial to show for the case where there are only two passengers: there are two seats, and the person in front of you is the worst person alive. He either takes his seat, or yours, randomly. Fifty percent, done.

For three people (1. Worst Person Alive, 2. Rando Calrissian, and 3. You) and three seats, we can still do it in our heads. WPA takes one of three seats, so right away you have a 1/3 chance of not getting your seat. But there is also a 1/3 chance that he takes Rando’s seat, in which case Rando will randomly take one of the two remaining seats, yours or WPA’s assigned seat. One-third times one-half is 1/6, so there is a 1/6 chance you will find Rando sitting in your seat, and a 1/3 chance WPA will be sitting there. So 1/3 + 1/6 = 1/2. Boom, done.

Once I saw that the probability remained at 50% for three passengers, I suspected that it would be 50% for any number of passengers. I wrote a Monte Carlo to show that.

// AirplaneSeating.cpp : Defines the entry point for the console application.
// www.somedisagree.com, Jon Wiesman

#include "stdafx.h"
#include <vector>

#define SEAT_COUNT 100
#define EVIL_COUNT 1
#define AVAILABLE -1

class Plane
{
    std::vector<int>    m_seats;
    int                 m_available;

public:
    Plane(int seats)
    {
        m_seats.resize(seats);
        for(int i = 0; i < seats; i++)
            m_seats[i] = AVAILABLE;
        m_available = seats;
    }

    void    ClaimSeat(int seat, int passenger) 
    {
        m_seats[seat] = passenger;
        m_available--;
    }

    int     FindUnclaimedSeat() const
    {
        if(m_available == 0)
            return -1;
        int nth = rand() % m_available;

        int empty = 0;
        for(size_t i = 0; i < m_seats.size(); i++)
        {
            if(IsSeatAvailable(i))
            {
                empty++;
                if(empty > nth)
                    return i;
            }
        }
        return -1;
    }

    bool    IsSeatAvailable(size_t seat) const
    {
        return (seat >= 0 && seat < m_seats.size() && m_seats[seat] == AVAILABLE);
    }

    void    GetSeat(int passenger, bool evil)
    {
        if(evil || !IsSeatAvailable(passenger))
        {
            int seat = FindUnclaimedSeat();
            ClaimSeat(seat, passenger);
        }
        else
        {
            ClaimSeat(passenger, passenger);
        }
    }

    void    SimulateBoarding(size_t evilCount)
    {
        for(size_t i = 0; i < m_seats.size(); i++)
        {
            GetSeat(i, (i < evilCount));
        }
    }

    void    CompileStats(std::vector<int> &stats, int &wrongSeats)
    {
        for(size_t i = 0; i < m_seats.size(); i++)
        {
            if(m_seats[i] == i)
                stats[i]++;
            else
                wrongSeats++;
        }
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    std::vector<int> stats;
    int wrongSeats = 0;
    stats.resize(SEAT_COUNT);

    int trials = 100000;

    for(int i = 0; i < trials; i++)
    {
        Plane plane(SEAT_COUNT);

        plane.SimulateBoarding(EVIL_COUNT);
        plane.CompileStats(stats, wrongSeats);
    }

    printf("After %d trials with %d evil passengers:\n", trials, EVIL_COUNT);
    for(int i = 0; i < SEAT_COUNT; i++)
    {
        printf("Passenger %d seated properly %.2f%% of time\n", i, 100.0 * (double)stats[i]/(double)trials);
    }
    printf("Average of %.2f wrongfully seated passengers\n", (double)wrongSeats / (double)trials);

	return 0;
}

 

This code (download) is pretty simple. The Plane class keeps an array of seats and who (which passenger) is seated in each seat. It also keeps the number of empty seats at any time to make it easier to quickly choose a random seat. (For the purpose of this simulation it was convenient to say that the passenger index and seat assignment are the same.)

The constructor initializes the seat array to all available and sets the available count to the seat count. SimulateBoarding tells each passenger to find a seat. Finding a seat is easy. If you’re not evil and your seat is available, sit down. Otherwise, find a random available seat. Either way, call ClaimSeat to sit down and decrease the available member variable. A CompileStats function will increment the number of correct passenger-seat assignments and keep a running count of wrong ones. Finally we run this simulation 100,000 times and print out the results.

After 100000 trials with 1 evil passengers:
Passenger 0 seated properly 1.00% of time
Passenger 1 seated properly 99.03% of time
Passenger 2 seated properly 99.00% of time
Passenger 3 seated properly 99.00% of time
Passenger 4 seated properly 99.01% of time
Passenger 5 seated properly 98.93% of time
Passenger 6 seated properly 98.97% of time
Passenger 7 seated properly 98.95% of time
Passenger 8 seated properly 98.92% of time
Passenger 9 seated properly 98.98% of time
Passenger 10 seated properly 98.87% of time
.....
Passenger 90 seated properly 90.86% of time
Passenger 91 seated properly 90.03% of time
Passenger 92 seated properly 88.83% of time
Passenger 93 seated properly 87.42% of time
Passenger 94 seated properly 85.39% of time
Passenger 95 seated properly 83.11% of time
Passenger 96 seated properly 79.98% of time
Passenger 97 seated properly 74.74% of time
Passenger 98 seated properly 66.45% of time
Passenger 99 seated properly 49.95% of time
Average of 5.19 wrongfully seated passengers

So I ran this code really just to confirm that my guess of 50% would be correct. However, I saw something which kind of jogged my memory. The average number of wrongfully seated passengers out of 100 was 5.19. This was the average number of traffic jams with 100 cars from two weeks ago! (The exclamation point at the end of the last sentence might be the nerdiest exclamation point ever.) It turns out that the number of wrongfully seated passengers follows a Harmonic Series.

What this means is that the odds of anyone getting a wrong seat follows this pattern, starting from the last passenger to board: 1/2 + 1/3 + 1/4 + … You can see from the output that the chances of each passenger not getting their seat is indeed following that pattern, with a little Monte Carlo variance thrown in.

“But wait,” you say, probably not, but let’s pretend you do, “a Harmonic Series starts with one and you don’t have a one in there.” Oh but I do. But it comes at the end. Remember that in our simulation, Worst Person Alive boards first and therefore has a 99/100 chance of sitting in the wrong seat. The next person to board, let’s call him Rando Paul, has a 1/100 chance of finding WPA in  his seat. 99/100 + 1/100 = 1. The next person then has a 1/99 chance and on down to 1/2 for the last passenger. So the average number of wrongly seated passengers for N passengers with the Worst Person Alive seating first boils down to 1 + 1/2 + 1/3 + … + 1 / (N – 1).

Traffic jams and airline travel: unexpected sources of harmony. Thanks for reading!

 

Author: Wiesman

Husband, father, video game developer, liberal, and perpetual Underdog.

Disagree?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s