Postby **mag487** » Thu Aug 06, 2009 4:34 am

That's a cool problem, lime. The answer I'm getting is 1/2. Is this right?

Here is my reasoning. Assume WLOG that the seats are arranged in a line and that the first seat is on the first person's ticket, the second seat on the second person's ticket, etc. Define f(n) to be the probability that the last person ends up in his own seat (the last seat) if the problem is posed for n people, n >= 2. (So in this case, we are trying to find out the value of f(100).) We want to find a formula for f(n+1) in terms of f(2), f(3), ..., f(n). O.K., so let's suppose our line of passengers consists of n+1 people.

-If the first passenger randomly picks the first seat, then everyone will automatically end up in the right seat and so the probability that the last passenger ends up in the last seat is of course 1.

-If the first passenger randomly picks the second seat, then take out the second seat and relabel the first seat as number 2. The situation is now isomorphic to the case where there are n passengers rather than n+1, so the probability that the last passenger ends up in his seat is by definition f(n).

-If the first passenger randomly picks the third seat, then the second passenger automatically ends up in the second seat. Take out the second and third seats, and relabel the first seat as number 3. The situation is isomorphic to the case where there are n-1 passengers, so the probability that the last passenger ends up in the last seat is f(n-1).

-Repeating this reasoning, if the first passenger randomly picks the kth seat, 1 <= k <= n, the probability that the last passenger ends up in the last seat is f(n-k+2).

-If the first passenger picks the (n+1)th seat, the probability that the last person ends up in the (n+1)th seat is obviously 0.

The first person has a probability of 1/(n+1) of choosing any given seat. So we conclude that f(n+1) = 1/(n+1) + f(n)/(n+1) + f(n-1)/(n+1) + ... + f(2)/(n+1) + 0/(n+1) = (1 + f(n) + f(n-1) + ... + f(2))/(n+1).

Now, obviously f(2) = 1/2. Also, suppose further that f(3) = f(4) = ... = f(i) = 1/2 for a given integer i > 2. Then the above equation tells us that f(i+1) = (1 + f(2) + f(3) + ... + f(i))/(i+1) = (1 + (i-1)/2)/(i+1) = 1/2 * (2 + i - 1)/(1+i) = 1/2 * (i+1)/(i+1), which also equals 1/2! So this is an inductive proof that f(n) = 1/2 for each n >= 2.

Have I made any errors here?