Here's a good puzzle, sure stumps me: ( borrowed from cartalk.com)

RAY: You're one of a hundred people standing in line to get onto an airplane

that has 100 seats. There's a seat for every person who's in line, and each of

you has a boarding pass for your assigned a seat. The first person to walk onto

the plane drops his boarding pass and, instead of picking it up, decides, "I'm

just going to sit anyplace." He takes a seat at random.

Now, every other passenger will take either his assigned seat or, if that seat

is taken, that passenger will take any seat at random.

TOM: I've been on that flight!

RAY: Because you are such a kind, generous, and accommodating person, you are

the last passenger to walk onto the plane. Obviously, there's going to be one

seat left, because everyone else is sitting in his correct seat, or not.

The question is: What are the chances that you get to sit in your assigned seat?

To Prove: For any number of people n>=2, the chance of the final passenger getting his assigned seat is 50%

n=2:

The first passenger can choose either his own seat or that of the final passenger, with an equal 50% chance.

Since the first passenger has a 50% chance of taking his assigned seat, the final passenger will have a 50% chance of getting his assigned seat.

n->n+1:

Assume that for n passengers, the chance of the final passenger choosing his assigned seat is 50%.

For n+1:

The first passenger can choose from any of n+1 seats: his own, the final passenger's, and the n-1 other seats. Probability of the first passenger choosing:

His own: 1/(n+1)

Final Passenger's: 1/(n+1)

Other passenger's: (n-1)/(n+1)

If the first passenger sits in one of the other seats, then the problem reduces to the one with n passengers: n seats remainings, n remaining passengers, and one passenger (displaced by the first passenger) having to choose a seat at random.

So the chance of the final passenger sitting in his own seat

= 1/(n+1) + 50% * (n-1)/(n+1) = 1/2

So n implies n+1. QED