## Thursday, June 12, 2014

### Problem

People are waiting in line to board a 100-seat airplane. Steve is the first person in the line. He gets on the plane but suddenly can't remember what his seat number is, so he picks a seat at random. After that, each person who gets on the plane sits in their assigned seat if it's available, otherwise they will choose an open seat at random to sit in.
The flight is full and you are last in line. What is the probability that you get to sit in your assigned seat

### Solution

There is a 1/2 chance that you'll get to sit in your assigned seat.

We first make two observations:

1. If any of the first 99 people sit in your seat, you WILL NOT get to sit in your own seat.

2. If any of the first 99 people sit in Steve's seat, you WILL get to sit in your seat. To see why, let's say, for the sake of example, that Steve sat in A's seat, then A sat in B's seat, then B sat in C's seat, and finally, C was the person who sat in Steve's seat. We can see that this forms a sort of loop in which every person who didn't sit in their own seat is actually sitting in the seat of the next person in the loop. This loop will always be formed when a person finally sits in Steve's seat (and if Steve sits in his own seat, we would consider this to be a loop of length 1), and so after that point, everybody gets to sit in their own seat.

Based on these observations, we know that the instant that a passenger sits in either Steve's seat or your seat, the game for you is "over", and it is fully decided if you will be sitting in your seat or not.

Our final observation is that for each of the first 99 people, it is EQUALLY LIKELY that they will sit in Steve's seat or your seat. For example, consider Steve himself. There is a 1/100 chance that he will sit in his own seat, and a 1/100 chance that he'll sit in your seat. Consider any other person who has been displaced from their own seat and thus must choose a seat at random...if there are N seats left, then there is a 1/N chance that they'll sit in Steve's seat, and a 1/N chance that they'll sit in your seat.

So because there is always an equal chance of a person sitting in your seat or Steve's seat (and one of these situations is guaranteed to happen within the first 99 people), then there is an equal chance that you will or will not get your seat. So the chance you get to sit in your seat is 50%.