The Unapologetic Mathematician

Mathematics for the interested outsider

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!

(1\,a_2\,a_3\,...\,a_n)

This also has the property that the sequence of a_i only increases. We need the probability that a_n is not 100.

Let’s say that it is. Then we have the cycle (1\,a_2\,a_3\,...\,a_{n-1}\,100). We can stick the transposition (a_{n-1}\,100) after it to give (1\,a_2\,a_3\,...\,a_{n-1}). 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 (1\,a_2\,a_3\,...\,a_{n-1}) we can again stick the transposition (a_{n-1}\,100) after it. Now this gives (1\,a_2\,a_3\,...\,a_{n-1}\,100), 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.

February 5, 2007 Posted by | Algebra, Group Examples, Group theory | 13 Comments

New invariant?

Tonight a new paper showed up on the arXiv: “A polynomial invariant of finite quandles”. Of course, this leads to an invariant of knots and links. As soon as I get my current plate cleared I’ll be turning to this one to see how it behaves under quandle morphisms. The more invariants I bring into my program, the better.

February 5, 2007 Posted by | Uncategorized | Leave a comment