## Tuesday, June 29, 2010

### Airline passengers

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)?

1. Let's solve the problem for N passengers.

Assuming this: http://en.wikipedia.org/wiki/Cycle_notation

In every final configuration there is only one cycle (starting with 1), with the elements all ordered ascending, because when the cycle starting with 1 is closed, all the passengers simply sit down in their places.
Now in every configuration the last passenger sits in the 1st or in his place, cause if the cycle finish with N he goes to the 1st place, if the cycle finish in another number, he'll go to his place.

The total number of configurations that the passengers can assume is equal to the number of elements in the power set of S= {2,3,4,..,N}.

Proof: Every subset of S can be considered as a cycle starting by 1 and continuing with the elements of the subset, ordered ascending. This cycles are in a one-to-one correspondence with the configurations because a passenger i can't sit in a place j with j<i and when the cycle ends, all the passengers simply sit down in their places.

Hence the total configurations are 2^(N-1).

The number of configurations in which the last passenger sits in the 1st place is equal to the number of elements in the power set of {2,3,4,..,N-1}, that are the number of configurations in wich the cycle is closed by the last passenger.

Finally, the probability is 2^(N-2)/2^(N-1)=0.5