One more conundrum?

[lime]

Here is interesting problem I found today in the book.

There is a plane with 100 seats and the boarding is started. The first passenger in the line of 100 people comes inside the plane and sits on the random seat. Every next passenger who comes inside sits on his seat (as it marked in the ticket) if it is empty, otherwise, he sits on the random empty seat.
What is the probability that the last passenger will sit in his seat?

[zuluyankee]

Hi, just found this interesting and hopefully helpful forum!

This problem--lemme give it a shot:
consider the probability that the first 99 passengers won't sit on the 100th passenger's seat. This way I get 1/100 as the probability the 100th pax will seat on his seat.

That seems pretty high to me, though! Any flaw in the reasoning?

[lime]

The answer is certainly wrong.

How did you decide that the probability that other 99 will not seat in his seat is 1/100?

[zuluyankee]

Call the 100th pax to board A.

The prob. that the 1st pax won't sit on A's seat: 99/100;

the prob. that the 2nd pax won't sit on A's seat: 98/99, given that the 1st pax didn't;

etc. up until the 99th pax.

The product (99/100)(98/99)...(2/3)(1/2) reduces to 1/100.

I feel that it's wrong, but where?

the book = The Book (of Erdos' imagination)?

[lime]

the prob. that the 2nd pax won't sit on A's seat: 98/99, given that the 1st pax didn't

Here is the mistake.

It will be = 98/99 + (1/99)*(97/98).

[zuluyankee]

Ok, I know where the sum is coming from, but this is a typical scenario I'd always find perplexing...

If the 1st pax had sat on A's seat, then there isn't any chance (probability = 0) for A to sit on A's seat anymore, right? (And so the term added should be 0...)

So the question boils down to: what's the flaw is this very reasoning?

[mag487]

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?

[lime]

Brilliant, mag! Sorry for delay with answer. Your solution is absolutely correct!

[conrado.math]

I'm sincerely impressed by mag's reasoning. I doubt I'd ever think about solving this problem this way... Or solving at all!