grg99
asked on
The airplane seat puzzle
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?
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?
50%
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.
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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.
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.
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
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
Typo on last line above. It should read
p<N> = 1/[N - (N-2)] = 1/2
p<N> = 1/[N - (N-2)] = 1/2
ASKER
Wow! So many correct answers, all gotten to in different ways, I'm impressed, pts to follow...
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
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%
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%
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?
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?
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.
In view of this I am sceptical of the solution being 50% with one hundred passengers. There are of course factorial 100 possibilities.
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.
> 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.
Thanks lemmeC,
That makes it a lot clearer (for me) than wandering through a pile of p<n>'s
That makes it a lot clearer (for me) than wandering through a pile of p<n>'s
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.