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 probabilitythat 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!