The Airplane Seat solution
And now, the solution to the Airplane Seat problem.
Obviously there’s a 1% probability that the first passenger chooses his own seat, in which case the last one automatically gets his. Then there’a a 1% chance that the first chooses the second passenger’s seat, who then has a 1/99 chance of choosing her own, or a 100% chance of this all getting way too complicated.
So let’s look for something not quite so obvious. There are various ways of solving the problem, but the one I’m interested in uses the fact that what we’re really looking at is a permutation!
This also has the property that the sequence of 
Let’s say that it is. Then we have the cycle 
What if we have a cycle that doesn’t end with 100? If we write it as
Even better, if we start with any cycle, ending with 100 or not, and do both transformations we get back the exact same cycle we started with. We say that the two transformations are inverses of each other, which just means that each undoes what the other does. A fancier word for an invertible function between two sets is “bijection”.
So we’ve split all valid sequences into ones where 100 gets his own seat and ones where he doesn’t, and shown that there’s a bijection between them. That means that the two sets have the same size! So picking a sequence at random we find that in exactly half the cases 100 will get his own seat.
Like Euclid used to say, Q.E.D.
Wonderful proof. But did Euclid really speak Latin?
As I said in my comment on the original problem: “Toss a coin”. But I must admit my proof wasn’t half as nice as this one.
Actually rereading the proof here, I wonder whether there’s a missing step (I know it gives the right answer). Having shewn that 50% of the cycles end with 100 and 50% don’t, is it not also necessary to shew that each cycle is equally likely?
Just wondered.
Okay, Chris, so each cycle comes in a pair, one ending in 100 and one with 100 left off. Again, write (1 … a_{n-1} 100) for the one including 100.
Imagine walking along the construction of the cycle. When we get to a_{n-1}, she either takes seat 1, seat 100, or another open seat, all seats having equal probability. If she takes an open seat, this wouldn’t be the pair of cycles we’re talking about, so it’s either 1 or 100, each equally likely: 50%.
(note: the <sub> tags don’t seem to work in the comments, so I’ve reverted to something more TeX-like)
There is a simpler proof.
In the problem some people will sit in their own seats and others (including passenger 1) will pick a seat at random. If any “random” passenger picks seat 1, passenger 100 gets his own seat, if any random person picks seat 100, he does not. Since a passenger is equaly likely to pick seat 100 or seat 1, the chances of passenger 100 getting his own seat is 50%.
Note that a least one passenger must pick seat 1 or 100 at random. If none of the first 98 do so, then these will be the last two seats left when passenger 99 chooses, and he will be forced to choose between them.
Yes, Art, that works too. I did say that there were many alternate solutions, but the one I presented has the benefit of using the group theory I’ve been talking about recently