Question:

A line of 100 airline passengers is waiting to board an airplane. 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 seat number n.

Unfortunately, the first passenger in line ignores his or her assigned seat number and picks a random seat to occupy. All the other passengers are well behaved and will go to their assigned seats unless the seats are already occupied, in which case they also will take a seat at random. What is the probability that the last (one-hundredth) passenger to board the plane will sit in his or her assigned seat?

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution: Interviewers like this puzzle because it often flows naturally from the conversation when the candidate flies in for the interview. A recruiter at Fog Creek Software recalls a candidate who answered:

This sounds like a recursive math problem, which, while not impossible, sounds like it’s not what’s called for here. So let’s simplify and see if that helps. What if there were only two seats on the airplane? Then since he can sit in only one of two seats, he has a 50 percent chance of sitting in his assigned seat. Is this a general solution?

In the case of 100 seats on the airplane, can the last guy sit in, say, seat 75? No, because otherwise, the seventy-fifth passenger would have sat in it. In fact, the one-hundredth guy can only be at seat 100 or 1. The one-hundredth guy doesn’t decide anything. He takes whatever is available. So, don’t mind him. So, there are only two possibilities, decided by guys 1 through 99. Since from everybody’s point of view, seat 1 is just like seat 100 (they just look at their own seat as special and the first guy doesn’t look at any seat as special), at the end, 1 being available must be just as likely as 100 being available.

Solution: 50 percent chance.