Crazy Guy On The Airplane

Crazy Guy On The Airplane

A line of 100 airline passengers is waiting to board a plane. they each hold a ticket to one of the 100 seats on that flight. (for convenience, let's say that the nth passenger in line has a ticket for the seat number n.)

Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. all of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. if it is occupied, they will then find a free seat to sit in, at random.

What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

Solution

The first guy might chose his own seat (1/100) or the 100th person's seat (1/100). These cases have equal probability, and whatever happens the rest of the way won't matter.

The interesting cases are when he picks some seat that's neither his own or #100. Now, when the next guy comes in, he'll pick either his unoccupied seat or a random seat. What he does depends on the first guy, but after he's done we have the same problem from the start minus 1 person. To spell it out, if his seat is unoccupied, he takes it, and the crazy guy is still occupying someone else's seat. Effectively now we're down to 99 seats since 1 seat has been properly taken. The other case is if his seat is occupied, and he'll pick the crazy guy's seat (1/99) or the #100's seat (1/99) with equal probability, the uninteresting cases. The rest of the time, he picks some other seat. Notice that this again reduces the size of the problem by 1--there's only one wrongly occupied seat.

There's always a maximum of 1 wrongly occupied seat, so the problem is recursive (in a backward sense). The base case is 2, and the probability is 1/2 either way and thus there's a 1/2 chance for the last guy to take his own seat.

Graphically, the "search path" is:

{1/100 or 1/100} or {
{1/99 or 1/99} or {
{1/98 or 1/98} or {
...
}}}

I suppose it's much clearer this way. Just keep in mind the statement before "or" happens P=2/100 of the time and P=98/100 for the statement after "or", not that it matters in this problem.