Solved

The airplane seat puzzle

Posted on 2004-10-06
15
2,040 Views
Last Modified: 2011-09-20
Here's a good puzzle, sure stumps me:  ( borrowed from cartalk.com)


RAY: You're one of a hundred people standing in line to get onto an airplane
that has 100 seats. There's a seat for every person who's in line, and each of
you has a boarding pass for your assigned a seat. The first person to walk onto
the plane drops his boarding pass and, instead of picking it up, decides, "I'm
just going to sit anyplace." He takes a seat at random.

Now, every other passenger will take either his assigned seat or, if that seat
is taken, that passenger will take any seat at random.

TOM: I've been on that flight!

RAY: Because you are such a kind, generous, and accommodating person, you are
the last passenger to walk onto the plane. Obviously, there's going to be one
seat left, because everyone else is sitting in his correct seat, or not.

The question is: What are the chances that you get to sit in your assigned seat?

0
Comment
Question by:grg99
  • 4
  • 4
  • 4
  • +2
15 Comments
 
LVL 5

Expert Comment

by:lemmeC
Comment Utility
50%
0
 
LVL 17
Comment Utility
I'm not sure that the chances are much greater than 50%.

It's the chances of 1 of 99 people picking up the first person's assigned seat at random.

If that assigned seat hadn't been selected by the time it got to the 99th person, the chances of them picking that seat (and leaving your's vacant) is 1 in 2 or 50%.

The chances of the 99th person having this choice are dependant on the choice of the 98th person which was a 1/3 chance of picking the original seat. 1/3 * 1/2

Chances of the 98th person having a choice were 1/4. so (1/2 * 1/3 * 1/4)

etc.

When I multiplied it all out I got a figure of 1/(1.0609* 10^ -160)

I think you, as the last person to board, would be almost guaranteed to have your assigned seat.
0
 
LVL 5

Accepted Solution

by:
lemmeC earned 250 total points
Comment Utility
Proof by Induction:

To Prove: For any number of people n>=2, the chance of the final passenger getting his assigned seat is 50%

n=2:
The first passenger can choose either his own seat or that of the final passenger, with an equal 50% chance.
Since the first passenger has a 50% chance of taking his assigned seat, the final passenger will have a 50% chance of getting his assigned seat.

n->n+1:
Assume that for n passengers, the chance of the final passenger choosing his assigned seat is 50%.

For n+1:
The first passenger can choose  from any of n+1 seats: his own, the final passenger's, and the n-1 other seats. Probability of the first passenger choosing:
His own: 1/(n+1)
Final Passenger's: 1/(n+1)
Other passenger's: (n-1)/(n+1)

If the first passenger sits in one of the other seats, then the problem reduces to the one with n passengers: n seats remainings, n remaining passengers, and one passenger (displaced by the first passenger) having to choose a seat at random.

So the chance of the final passenger sitting in his own seat
= 1/(n+1) + 50% * (n-1)/(n+1) = 1/2

So n implies n+1. QED
0
 
LVL 7

Assisted Solution

by:wytcom
wytcom earned 250 total points
Comment Utility
p<n> = probability that nth persons seat is taken

p<1> = 0
p<2> = prob that 1st person took the seat
   = 1/100
p<3> = prob that 1st took it, or 1st took 2nd's then 2nd took it
   = 1/100 + p2*1/99
   = p2*(100/99)
   = 1/99
...
p<n> = 1/[100 - (n - 2)]

p<100> = 1/2
0
 
LVL 17
Comment Utility
I said I wasn't sure.

I'm still not. I'm sure that you're both right as it looks like you know what you are talking about (and I did find and answer via google that said 50%, but it didn't offer any explanation).

Can't quite follow your math I'm afraid, but after some painfull typing up of outcomes starting with two seats and up to four seats, 50% does appear quite possible.
0
 
LVL 7

Expert Comment

by:wytcom
Comment Utility
Even if it is not the first person that loses their boarding pass and takes a random seat, we still get a 50% probability that the last person's seat is taken.  This is true for any number of total seats:

mth person loses boarding pass and takes random seat
Any person whose seat is taken takes random seat

p<n> = prob that nth persons seat is taken

p<1> = 0
p<2> = 0
...
p<m> = 0
p<m+1> = prob that mth person took this seat
       = 1/[N-(m-1)]
p<m+2> = prob that mth person took this seat or (m+1)th person's seat
taken and he took it
       = 1/[N-(m-1)] + p<m+1>*1/(N-m)
       = 1/(N-m)
...
p<m+n> = 1/[N - (m+n-2)]

p<N> = 1/[N - )N-2)] = 1/2
0
 
LVL 7

Expert Comment

by:wytcom
Comment Utility
Typo on last line above.  It should read
p<N> = 1/[N - (N-2)] = 1/2
0
What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

 
LVL 22

Author Comment

by:grg99
Comment Utility
Wow!  So many correct answers, all gotten to in different ways, I'm impressed, pts to follow...
0
 
LVL 7

Expert Comment

by:wytcom
Comment Utility
Thanks grg99.  This problem is interesting because it seems complex but has such a simple answer that applies regardless of which passenger takes the wrong seat or what the count of total passengers is.  I suspect there is an even simpler way to look at this (than the one I presented here) that matches the simplicity of the result.  (I confess that I haven't digested LemmeC's solution - perhaps his is the simple one.)  Kind regards, Wytcom
0
 
LVL 5

Expert Comment

by:lemmeC
Comment Utility
Got this from http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=2206

Any passenger who chooses a seat at random has an equal chance of choosing the seat of passenger 1 or 100. If they choose 1, then all remaining passengers can sit in their own seat. If they choose 100, then the last passenger will not be able to sit in their assigned seat. Any OTHER choice (one of the other open seats) simply defers the decision to a later point in time, where THAT deposed passenger will have to make the same random choice.

Chance: 50%
0
 
LVL 17
Comment Utility
Still reading and re-reading the thread in the link you provided lemmeC -  I'm sure there's the answer there, I just haven't had the time to follow it through properly.

I mentioned this puzzle to my ten year old son who added a new complication. "What if there's a family of four who all want to sit together?" I'm not even going to attempt this, but I wonder if someone else might. It could be made more like the real world, where the family could split into two groups of two - one parent with each child. Of course families with young children ususlly board first so perhaps four people get displaced. Does this affect the probabilities of the last person getting his own seat?
0
 

Expert Comment

by:Lengore
Comment Utility
I tried the simple case of four passengers in an aircraft with four seats.  Trying all possible cases (there are 4 for the first passenger, 12 for the second passenger and 24 possibilities for the third and forth passengers) I found that the fourth passenger would get his allocated seat in 6 cases out of 24 i.e. 25%.

In view of this I am sceptical of the solution being 50% with one hundred passengers. There are of course factorial 100 possibilities.
0
 
LVL 5

Expert Comment

by:lemmeC
Comment Utility
Lengore,

> There are of course factorial 100 possibilities
This would have been true if each of the passengers would have chosen his seat completely at random. In that case, the probability of the last passenger getting his correct seat would be 1/n when there are n passengers.

However, the condition states "Now, every other passenger will take either his assigned seat or, if that seat
is taken, that passenger will take any seat at random."
Only the first passenger chooses his seat at random. So, the set of valid possibilities is a subset of n!.

In case of 4 passengers, with seats 1, 2, 3 and 4 allotted to P1, P2, P3 and P4 respectively,

1     2     3     4     Validity
P1    P2    P3    P4    Valid
P1    P2    P4    P3    Invalid
P1    P3    P2    P4    Invalid
P1    P3    P4    P2    Invalid
P1    P4    P3    P2    Invalid
P1    P4    P2    P3    Invalid
P2    P1    P3    P4    Valid
P2    P1    P4    P3    Invalid
P2    P3    P4    P1    Invalid
P2    P3    P1    P4    Invalid
P2    P4    P1    P3    Invalid
P2    P4    P3    P1    Invalid
P3    P1    P2    P4    Valid
P3    P1    P4    P2    Invalid
P3    P2    P1    P4    Valid
P3    P2    P4    P1    Invalid
P3    P4    P1    P2    Invalid
P3    P4    P2    P1    Invalid
P4    P1    P2    P3    Valid
P4    P1    P3    P2    Valid
P4    P2    P1    P3    Valid
P4    P2    P3    P1    Valid
P4    P3    P1    P2    Invalid
P4    P3    P2    P1    Invalid

There are 8 valid combinations, and P4 gets his seat in 4 of these combinations.

Irrespective of the number of passengers, the last passenger would have a choice of 2 seats: The seat allotted to the first passenger and The seat allotted to him.
0
 
LVL 17
Comment Utility
Thanks lemmeC,

That makes it a lot clearer (for me) than wandering through a pile of p<n>'s

0
 

Expert Comment

by:Lengore
Comment Utility
My thanks too lemmeC. I realised late last night that I had misinterpreted the question and a quick re-analysis of the problem with a small number of seats shows that for 3, 4 or 5 seats the answer is always 50%. I was planning to post again but your very patient explanation beat me to the post.
0

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

Suggested Solutions

This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
This video discusses moving either the default database or any database to a new volume.
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now