A line of 100 airline passengers is waiting to board the plain. 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 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)?

First, a simulation suggests the answer is around 1/2
The only way Passenger-100 ends up without a seat is if someone randomly takes it. This happens exactly when someone doesn't randomly take the first seat. Thus, the only seats Passenger-100 can get are 1 or 100.
Suppose we have this scenerio with two passengers. The probability P[2] of the second passenger getting her seat is 1/2. Given the same scenerio with 3 passengers, the probability P[3] of the third passenger getting her seat is equal to P[first person chooses first seat] +P[first person chooses 2nd seat]*P[2]=1/3+1/3*1/2=1/2. In general, given the scenerio for n passengers, the probability P[n] of the nth passenger getting her own seat is given by:
P[1st passenger takes own seat] + Sum[P[1st passenger takes kth seat]*P[k],{k,2,n-1}]
=1/n+(1/n)*(n-2)*(1/2)=1/2
Thus, regardless of the number of passengers (greater than 1), the probability of the last passenger getting her own seat is 1/2. 

Posted by owl on 2005-08-17 19:14:32