October 8, 2015

I was on a bumpy flight 2 days ago when visiting our company's Colorado site. I remembered that there was a very interesting question about taking the seats on a plane. To be honest, I don't like the underlying intuition provided HERE. I am trying to give a mathematical solution and proof in this article.

Let me rephrase this question first. There are a 100 people in line to board a plane that has 100 seats. The first person has lost his boarding pass so he decides to take a random seat out of 100. After him, every person that boards the plane will either take his/her designated seat (if the seat is available), or take a random seat (if his/her seat is already taken). What is the probability that the last person that boards will end up in his/her designated seat?

I don't believe intuition since it can be wrong. I am dumb so I choose to start with 2 persons and 2 seats (case N = 2). To me, this is proved to be quite a successful strategy for so many interviews. Let us denote the event that the last person gets his/her designated seat as A. Apparently:

For N = 3, there are 3 seats: seat 1, seat 2, and seat 3. If the first person gets his designated seat (with probability 1/3), then the other 2 guys will both get their seats. If the first person chooses seat 2 (with probability 1/3), the other 2 persons have to repeat case N = 2. If the first person chooses seat 3, the last person is never going to get his/her designated seat. We have

Here we can guess the final answer is 1/2. This can be easily proved by induction on N. If we guess

Then we have