Hi gauravk.newton,

More generally, let's say P(n) is the probability that the last passenger gets his desired seat on an n-seat airplane. Working out P(n) for a few small values of n, we begin to suspect P(n) = 1/2 for all . Let's see if we can give a proof by induction on n.

The case n=2 is easy. The first passenger chooses seat 1 with probability 1/2, in which case passenger 2 gets his desired seat. Otherwise passenger 1 chooses seat 2 and passenger 2 is unhappy. So P(2) = 1/2.

Now assume that P(n) = 1 for all n such that , for some . Suppose we have a k+1 - seat airplane.

With probability 1/(k+1), the first passenger picks seat 1 and everyone (including the last passenger) gets his desired seat.

Also with probability 1/(k+1), the first pasenger picks seat k+1 and the last passenger does not get his desired seat.

With probability (k-1)/(k+1), the first passenger picks seat number s, where . Then passengers 2, 3, ..., s-1 will all take their desired seats and passenger s will make a random choice from the remaining k-s+2 seats. This is just like the original problem, where passenge s now takes the place of passenger 1 and the plane contains k-s+2 seats. By the inductive hypothesis, the probability that the last passenger will get his desired seat is 1/2.

[Edit: No, this part isn't quite right-- let me work on it and get back to you later. It's too late at night to work on it now.]

So .

This completes the proof.