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 only increases. We need the probability that is not 100.
Let’s say that it is. Then we have the cycle . We can stick the transposition after it to give . This is a valid cycle that doesn’t end with 100.
What if we have a cycle that doesn’t end with 100? If we write it as we can again stick the transposition after it. Now this gives , which does end with 100.
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.