Holiday Puzzles

Following are a couple of related puzzles, motivated by this holiday season:

1. You are standing at the very end of a line of 100 holiday travelers (you and 99 others) waiting to board an airplane.  Each passenger in line has a boarding pass assigning him or her to one of the 100 seats on the airplane.  However, the first person in line is rather confused, and so instead of sitting in her assigned seat, she boards the airplane and simply selects a seat at random (possibly her own).  As each subsequent passenger boards the airplane, he sits in his assigned seat if it is empty, or selects an empty seat at random if it is not.  What is the probability you, the last person to board, will be able to sit in your assigned seat?

2. Preparing to return home after the holiday, you find yourself once again last in a line of 100 travelers waiting to board an airplane.  This time, it is not just the first person in line who is confused; after a stressful holiday with their families, now every person in line is not just confused but deranged.  That is, each passenger in turn boards the airplane and selects a seat at random from all currently empty seats, excluding their own.  What is the probability that you, the last person to board, will be forced to sit in your assigned seat?

The first problem is an oldie but a goodie.  I like it because it can be approached in several different ways.  It is easy to simulate using a computer, which quickly leads to conjecture at the solution.  Given the conjecture, the proof is a nice application of mathematical induction.  But there are also nice symmetry arguments via which the problem may be solved more directly.

The second problem is more difficult, and is the real motivation for this post.  Solutions to both are welcome in the comments– until then, consider in what other way(s) this second problem might arise in relation to the holidays?

This entry was posted in Uncategorized. Bookmark the permalink.

6 Responses to Holiday Puzzles

  1. Christopher Wellons says:

    I wrote a simulation for problem 1 before reading any further, only to see you mention using a simulation. I’m still thinking on the second problem. I’m guessing that the same problem might arise for Secret Santa — people don’t want their own gifts.

  2. Peter C says:

    I like the first problem, that’s pitched at about my level of difficulty and has a neat ‘insight’. I solved it by starting a probability tree and then jumping to the solution from there.

    The second problem is a bit tougher! At first I thought “ah that’s easy – the first person can choose from 99 seats (not his own) so there is a 98/99 probability he sits in your seat, then it’s 97/98 for the second person etc.”

    Then I realised that the first person may well sit in the second person’s seat. If he does that, then the second person actually has 99 seats he can choose from, not 98. In fact, if the first guy doesn’t sit in your seat, then he is definitely sitting in someone else’s seat. Short of building a horrendous probability tree, I’m stumped!

    • Thanks for reading– I also like the “Aha!” in the first problem. You’re right, the second problem is not nearly as well behaved. I will follow up next week with more details.

  3. Jawak says:

    For #2.
    Let f(x) be the number of ways to have x people all sitting in the wrong seat.
    It can be shown that f(x) = (x-1)(f(x-1)+f(x-2))

    I think the answer is f(99)/f(100), the number of ways to have everyone but the last guy in the wrong seat divided by the number of ways to have everyone in the wrong seat.
    The following mathematica code can be used to compute that quotient:
    f[1] = 0;
    f[2] = 1;
    f[x_] := f[x] = (x – 1) (f[x – 1] + f[x – 2])
    f[99]/f[100]
    N[f[99]/f[100], 10]*100

    It turns out the quotient is 343327959841638047651959775267761420323657838053757849835434002826851807933276324327913964298509889902373459201557839848280014864125740605537568541370698786 / 34332795984163804765195977526776142032365783805375784983543400282685180793327632432791396429850988990237345920155783984828001486412574060553756854137069878601

    or expressed as a decimal, 1.000000000%.

    This seems to be in line with my simulations. This is the output from the simulations program:
    Simulations: 1000000
    Total: 9858 out of: 1000000
    0.9858%

    I’m not sure if the mathematical method is right, but it’s pretty close to what I got with the simulations.

    • “I think the answer is f(99)/f(100), the number of ways to have everyone but the last guy in the wrong seat divided by the number of ways to have everyone in the wrong seat.”

      This is a good approximation. An even better approximation– and perhaps the solution that you intended?– is f(99)/(f(100) + f(99)), the number of final assignments with all but the last person in the wrong seat, divided by the total number of final outcomes, which includes both the assignments with everyone in the wrong seat as well as those with all but the last person in the wrong seat.

      The problem, however, is that both of these answers assume that each of those final outcomes is equally likely, which they are not. To see this, consider scaling the problem down to just 3 passengers and 3 seats, where the solution can be worked out by hand. In this case, the right answer is 1/4; your solution gives 1/2, while the above approximation is 1/3.

      I plan to post a solution shortly…

  4. Pingback: Secret Santa Revisited | Possibly Wrong

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