In this Riddler we are taking flight:
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?
Some weeks The Riddler is more math-intensive than others. Calculating a series of conditional probabilities involving permutations of 100 passengers seems daunting, but this week's puzzle can actually be solved with very little math at all.
Whenever I come across a puzzle with a lot of variables, I start by trying to solve a much simpler version of the problem, and hoping to find some insight that allows me to generalize to other cases. So here, I start with something like this instead:
There’s an airplane with 2 seats, and there are 2 ticketed passengers each with an assigned seat - you and one other person in front of you. It turns out that the other passenger is the worst person alive, and just sits in a random seat, without even looking at his boarding pass. What is the probability that you, the second passenger to board, finds your seat unoccupied?
It should be pretty obvious that the answer here is 1/2. The worst person alive (henceforth "WPA") either sits in your seat or he doesn't.
What if there are three seats and three passengers? That's slightly more complicated but still easy enough to enumerate all the possible outcomes:
- 1/3 of the time, WPA takes his own seat. Then the 2nd passenger takes his, and you get yours.
- 1/3 of the time, WPA takes your seat and you're SOL.
- 1/3 of the time, WPA takes the 2nd passenger's seat. Now the 2nd passenger must randomly choose a seat. Half of the time he'll take yours, and the other half he'll take WPA's assigned seat and you get yours.
Adding those all up shows that the probability you get your own seat is... 1/2. Just like the case with only two seats! Adding a third seat and passenger didn't change the answer to the problem. This isn't proof of anything but it's certainly an indication that perhaps the answer to the puzzle doesn't rely on the number of passengers at all.
In fact, with a little thought you should be able to convince yourself that:
- If any passenger randomly takes WPA's assigned seat (because their own seat had already been taken by someone else), everyone after that point will get their assigned seats, and
- The only seats that matter are WPA's and your own. If a passenger randomly takes anyone else's seat, all they've done is kicked the can further down the road.
To that second point, we saw in the 3-passenger puzzle that when WPA's seat is taken before yours, you "win." And when your seat is taken by someone else, you obviously "lose." But when WPA took someone else's seat, it just turned the 3-person puzzle into a 2-person puzzle.
And that's always what happens. Considering the original 100-passenger puzzle, imagine WPA boards the plane and takes the seat that was assigned to the 31st passenger in line. Passengers 2-30 board the plane and take their assigned seats. Passenger 31 boards and now must randomly choose a seat. This is now effectively just a 70-passenger puzzle. Passenger 31 can take WPA's seat (in which case you get your seat), he can take your seat (in which case you don't), or he could take one of the other 68 remaining seats (in which case he's passing the buck to someone else).
Say he randomly takes the seat that was assigned to the 66th passenger. Passengers 31-65 get their own seats. Passenger 66 boards the plane and we now have a 35-person puzzle. He can take WPA's seat, he can take your seat, or one of the other 33. At every step of the process, we either reduce the problem to a smaller variant (in which case we'd eventually get to the 2-person puzzle which we've already solved), or we resolve the problem. And when we resolve the problem, the chances that you'll "win" or "lose" your seat are the same.
Therefore the answer to the puzzle is 1/2 (and doesn't depend at all on the number of passengers).