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.

About these ads

February 5, 2007 - Posted by | Algebra, Group Examples, Group theory

13 Comments »

  1. Wonderful proof. But did Euclid really speak Latin?

    Comment by Astro | February 5, 2007 | Reply

  2. 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.

    Comment by Chris Hobbs | February 5, 2007 | Reply

  3. 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.

    Comment by Chris Hobbs | February 6, 2007 | Reply

  4. 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)

    Comment by John Armstrong | February 6, 2007 | Reply

  5. 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.

    Comment by Art | February 6, 2007 | Reply

  6. 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 :)

    Comment by John Armstrong | February 6, 2007 | Reply

  7. [...] original presentation and solution of the problem in “Car talk”. The problem and its solution was described also in John Amstrong’s blog “the Unapologetic Mathematician,” it [...]

    Pingback by Two Math Riddles « Combinatorics and more | October 23, 2008 | Reply

  8. [...] If you don’t see that immediately, consider how it’s really the exact same thing as how we solved the airplane seat problem almost two years ago, and Susan’s related Thanksgiving seating problem. Then each permutation [...]

    Pingback by Antisymmetric Tensors « The Unapologetic Mathematician | December 23, 2008 | Reply

  9. Doesn’t it seem like Art’s proof could be restated in group theoretic terms? Think of it this way: every possible cycle begins with 1, and can close in only two ways: by returning to 1, or — because the sequence can only increase — by reaching 100 without having returned to 1. In the latter case, the cycle must return to one after reaching 100.

    Comment by Jom | July 14, 2009 | Reply

  10. a simpler way to think about this is that 98 people are sitting where they are ‘supposed to’. There is only ever one person in a seat not matching a ticket already on the plane. People will take their seat unless otherwise occupied, and only then will they sit in an unassigned seat. So at any given time, only one seat will be occupied that does not have a corresponding ticket-holder on board.
    By the time we get to the last person, 98 people are in a place with a matching ticket-holder on the plane. So, the 99th person is either in their spot, or in a spot of someone who’s ticket is not yet on the plane (the last guy)
    So there is a 50% chance that the last guy gets his seat…no matter the number of seats

    Comment by michelle | May 9, 2010 | Reply

  11. So, michelle, any situation where there are two possibilities the probability of each is 50%?

    Comment by John Armstrong | May 9, 2010 | Reply

  12. I believe this proof is incorrect. You need a different bijection for each a_n-1, so what you have proved is that there are as many permutations ending with 100 as there are for any number 1-99, so in fact there are 99 times more permutations that don’t end in 100.

    In order for the probability to be 1/2 we also need to use the fact that if free people will sit in their own seat, which makes the problem simpler as pointed out by Art.

    Comment by Sam | February 13, 2012 | Reply

  13. To better define the bijection: If we let S be the set of allowable permutations that fix 100 and R the set of allowable permutations that don’t fix 100 then (1,100)R = S (since (1,a(1),…,a(n)) is allowable iff a(i) is strictly increasing), so the two sets have the same size.

    That still leaves you to show that the same holds for the probabilities i.e. P(S)=P(R), but this follows from the fact that P(s)=P((1,100)s) for any s in S (since it is equally likely that for s=(1,a(1),…,a(n)) the passenger a(n) chooses seat 1 or 100) which is essentially Art’s proof.

    Comment by Jason | February 24, 2012 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 392 other followers

%d bloggers like this: