# 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?

LVL 22
###### Who is Participating?

Commented:
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

Commented:
50%
0

Commented:
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

Commented:
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

Commented:
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

Commented:
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

Commented:
Typo on last line above.  It should read
p<N> = 1/[N - (N-2)] = 1/2
0

Author Commented:
Wow!  So many correct answers, all gotten to in different ways, I'm impressed, pts to follow...
0

Commented:
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

Commented:
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

Commented:

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

Commented:
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

Commented:
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

Commented:
Thanks lemmeC,

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

0

Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.