Thursday, December 23, 2010

Lost Boarding Pass and Your Destiny

Many of us are traveling this Holiday time, visiting family and friends or running away from them to the mountains or remote islands. Chances are you may be reading this puzzle in the airport. Hold on tightly to your boarding pass.

In this famous puzzle adapted from Peter Winkler's book, we imagine ourselves boarding Aloha airlines airplane from Honolulu to Maui. Everyone is relaxed and happy. The first person that ascends the stairs to the plane holds his boarding pass in in his lips as both of his hands are holding two puppy cages. He smiles to the flight attendant, letting the boarding pass twirl down through the stairs and under the plane. He hesitates for a moment but then decides to perches himself into a random seat. Every next person goes to his or her assigned seat, but those who find their seat occupied politely avoid the argument by taking any random free seat on this short flight. You are the last passenger to board this fully packed 100-passenger plane. The problem is that you pleaded the Aloha ticket counter person to seat you next to this gorgeous surfer and now no longer sure both of you will get your assigned seats. What are the chances?

Image by rantingfan, distributed under CCL

Answers accepted all day long on Friday, on our Family Puzzle Marathon. They will be hidden until Saturday morning (EST) and everyone who contributed something sensible will get a puzzle point.


Fe said...

Hmmm, the 100-passenger information was tricky.
However, whether i'm the 10th or 100th or 200th passenger, the chances of getting my assigned seat will always be 50/50! Either my seat is taken or not, so the answer is 1/2.

SteveGoodman18 said...

The only way that the surfer and I will be in our assigned seats is if he correctly guessed his seat at the start, a 1/100 chance.

Now, if he sat in either his assigned seat or mine, we will still end up together, possibly in each other's assigned seats. Combining these possibilities would make it 1/50 that we sit together.

I'm quite certain that if he sits anywhere else at the start, the first person who finds themselves displaced will sit next to this surfer if he is indeed that gorgeous, so we'll keep 1/50 as our answer.

Another interesting problem is if the surfer is asked to move to a different seat anytime someone finds him parked in their seat.

Wang said...

The answer was very surprising to me: 50% chance.

Let me demonstrate with 2 and 3 seats on the plane. (ie. not quite inductive reasoning)

With 2 seats, the passenger randomly takes a seat which could be their seat or your seat. Therefore, you have a 50% chance of ending up in your seat.

With 3 seats, the possibilities are (if you imagine the seats being labeled 123 and you are in the 3rd seat)

123 , 132, 213, 231, 312, 321

Of these, the only possible ones are (given the rule that number 2 has to sit in their own seat)

123 , 213, 312, 321

132 and 231 are not possible because after passenger 1 has taken the first seat or the third seat, the 2nd passenger has to take seat 2 (their assigned seat).

You can see that of the possibilities, again, you have a 50% chance of taking your own seat.

In the same sense, you can do this for 100 seats and get the same probability.

anne-marie said...

One chance over 100.

Happy Holidays!

Maria said...

I was contemplating extending the answer time for a few more days or even a week, however I think that this is a puzzle that is almost impossible to resolve on your own. In fact, you are in danger to sink into elaborate calculations and forget all about the real pleasure of the Holidays. This is one of these puzzles that you encounter once, learn how to solve and then enjoy surprising everyone and re-telling all life long. As you see, from the two people who answered correctly above both seemed to knew the puzzle from before. Let's savour the surprisingly simple solution:

Step 1: Forget about the surfer, concentrate on getting your own seat. In fact, all that really matters in this puzzle is you and the person with the lost boarding pass. More precisely - his seat and your seat.

Step 2: If the person with the lost boarding pass takes your seat - the game is lost. Independently of all the other seating, you will not get your seat. If, on the other hand, he randomly chooses his own seat - everyone else in this plane (including you) will get their assigned seat. Remember that everyone first goes to his/her assigned seat. So far we have two outcomes, one gives you your seat with a probability 0 and another with a probability 1. There two outcomes are equally likely. However, on a large airplane it is much more likely that lost boarder will choose someone else's seat. What happens then?

Step 3: When a person whose seat was taken comes into the plane, he has no choice but to pick one of the empty seats at random. He can choose your seat, he can choose the seat of the person with the lost boarding pass or someone else's. First two cases are equally likely. He picks your seat and you have 0 chances of getting it. He picks lost boarder's seat - and everything settles leaving you with a sure probability of 1 of getting your seat. If this person picks some other seat - the whole Step 3 should be repeated with the passenger whose seat was just taken.

Whatever happens, there are always equal probabilities of you surely loosing your seat or definitely getting your seat or continuing to observe other passengers with eventually only two seats left: your seat and lost boarder's. The person ahead on your in the line again has equal chances of choosing either seat, leaving you with 50/50 chance of getting yours. So, independently of passengers' choices your chances of getting your seat are always 50%.

Step N: Remember the surfer? Similarly to your chances of getting your own seat being equal to 1/2, surfer's chances are 1/2. For this events to co-occur, we multiply their probabilities: 1/2 x 1/2 = 1/4
Here I am assuming that these events are independent. Am I right? I am not 100% sure. What do you think?

Assuming my last step is correct, we have 25% chance of both getting our assigned seats, and fascinatingly it is the same in a 2-person plane as well as a 100-person plane.

As promised, everyone who submitted a sensible solution get a puzzle point: Fe, SteveGoodman18, Wang and anne-marie.

Happy Holidays and enjoy sharing this puzzle with your family and friends.

Lynnet's mom said...

I just wanted to let you know that Lynnet, her dad, and I spent hours on this puzzle (and her younger brother even got into the game, although we had to act the puzzle out for him with Lego people). It was fun!

We went in the opposite from the correct direction, focusing more on the chain of displaced people -- it was interesting to realize that the chain was guaranteed to never branch, and that the parity-break never goes above 1 no matter how many people get dominoed into the loop. We realized that as soon as the loop closed (someone sat in the first person's seat), everyone after that (including you) was guaranteed to get their intended seat, and we were figuring we'd approach the surfer end of things later. We were trying to figure out if we could find some way to get to an expected value for the whole thing (or for the inverse of the whole thing, or the length of the loop itself). Lotta good math, branching probability trees, problem-solving technique along the way, even if we were nowhere near the right answer.

I tried to convince Lynnet to type in what we'd figured out and how we'd gotten there, but (1) she was shy about not having a neat-and-complete solution (2) we got caught up in social obligations and forgot to get back to the task before the deadline. But it was a great puzzle, and an elegant solution! Thanks!

Fe said...

Maria,with further pondering (statistically, too), the probability of 1/2 for me and 1/2 for the surfer equals 1/4 for the both of us seem a better answer. And it's because of how you re-worded Peter Winkler's puzzle.Your question was: The problem is that you pleaded the Aloha ticket counter person to seat you next to this gorgeous surfer and now no longer sure BOTH of you will get your assigned seats. What are the chances?

But after I searched further and found the book,
Winkler's question was: what is the possibility that the last passenger to board finds HIS seat occupied?
If that was the question posted then I'll stand by my original answer, 1/2.

Happy new year and keep those puzzles coming!

Maria said...

I absolutely agree with you, Fe.
It is 1/4 assuming that these events are independent.

Happy New Year to everyone!
Skipping this weekend puzzle due to vacation.
Back to posting next week.

novabona said...

The analysis that gives 1/2 probability to the LAST person boarding the plane does not immediately apply to the intermediate boarders. They have a much higher chance than 1/2 of getting their own seat.

Consider the second to passenger to board. There is only 1/100 probability that his seat is taken by the first boarder. That means if the surfer is second to board, his correct-seat probability is 0.99, not 1/2.

It' not enough for 1/2 and 1/2 to be independent events to get 1/4. You also need them both to be 1/2. And only the final passenger to board has a probability that low. Expectation for intermediate passengers is probably 0.75, giving a joint probability of something like 3/8 they will sit together as assigned.

James said...

Well the answer is 98!/100! = 1/9900.
It's required just to find the number of ways these two can be placed in their designated seats... It can be done in 98! Ways

Post a Comment

Note: Only a member of this blog may post a comment.