Fog Creek Software
Discussion Board




Solution to 'crazy guy on the airplane'

First, nice puzzle. I enjoyed working this one out.

The first thing we need to do to solve this is to realise what each passenger sees when they enter the cabin. For N>=2 the Nth passenger will see seats 2 through N-1 occupied (that's no seats for N=2), and exactly one person in a seat randomly chosen from the others, i.e. from seats N through 100 and seat 1.

If that's not clear, imagine the Nth person finding their seat filled. That seat transitions from a seat randomly occupied to one that should be occupied (one of the N-2). The Nth person occupies a random seat, so there is still exactly one person occupying a randomly chosen seat. The others are in seats that SHOULD be occupied, even if the right person is not in the right seat.


So the Nth passenger's behaviour depends only on whether or not the 'random' person is occupying their seat.

For the Nth passenger let's call seats 2 through N-1 the 'correctly' occupied seats. They are all occupied. Lets call the other seats the 'remaining' seats, and note that exactly one of them will be occupied.

Let us suppose that for any passenger entering the cabin each of the 'remaining' seats is equally likely to be occupied, the probability  being 1/(102-N). We can't prove this yet, but we will.

If his seat his taken, then he takes one of the remaining (101-N) seats, at random. The chances of each remaining seat being occupied after this is [1/(101-N)]*[1/(102-N)].

If his seat is not taken then he takes his seat and the one of the 'remaining' seats that was occupied is still occupied, and because of our previous assumption, each is equally likely. (For completeness the probability is [1/(101-N)]*[1-(1/(102-N)] ). So because for each case the probability of each 'remaining' seat begin occupied was equal, the total probability of each 'remaining' seat being occupied after passenger N has sat down is still equal.

For N=2 it is obvious that our assumption about the 'remaining' seat being  randomly chosen is true (since only the crazy is in the cabin). So by induction it is true for all the following passengers too.

When passenger 100 enters, there are 2 'remaining' seats (his and seat 1). Each has the same chance of being occupied, so there is a 50% chance that he will get to sit in his correct seat.

Some interesting additional facts: the 50% is obviously not dependent on the number of people on the plane, and for N passengers and M seats the probability of the last passenger being correctly seated is (1+M-N)/(2+M-N).

Incidentally,  we should call this the Canadian version since the passengers don't like to complain. In the American version each passenger who finds his seat occupied threatens to sue the airline until the offending person is moved. :-)

For extra points: in the American version everyone gets to sit in the right place. What are the chances that the last person has to complain to achieve this?

David Clayworth
Tuesday, December 17, 2002

----------------------------------------------------------------
When passenger 100 enters, there are 2 'remaining' seats (his and seat 1). Each has the same chance of being occupied, so there is a 50% chance that he will get to sit in his correct seat.
------------------------------------------- David Clayworth


There are 100 passengers and 100 seats.  When passengers 100 enters, then there is one remaining seat.  The 100th passengers has no choice, they must take the last remaining seat (if they're Canadian or British, that is :)

Ged Byrne
Thursday, December 19, 2002

Hi Ged

I defined 'remaining seats' to be the seats excluding seats 2 through N-1 (seats 2 through N-1 will always be occupied whatever has gone on before). So when passenger 100 enters there are two 'remaining' seats, seat 1 and seat 100. One of them is occupied.

In retrospect this probably wasn't a good choice of name. 'possibly empty' seats might have been better. So passenger N would enter and see N-2 'always occupied' seats (seats 2 through N-1) and 100-(N-2) 'possibly empty' seats, with one of them occupied.

What I hoped I demonstrated was that at each stage of the process, each of the 'possibly empty' seats is equally likely to be the one occupied.

David Clayworth
Thursday, December 19, 2002

*  Recent Topics

*  Fog Creek Home