[Guest]

A man is getting on a plane when he loses his boarding pass. Unsure where to sit, he picks a random seat. afterwards, each passenger that gets on sits in his assigned seat if it is available or a random seat if it is not. If there are a total of N seats and N passengers, what is the probability that the last passenger to get on the plane will sit in the correct seat?

[Guest]

1/N.. I guess this is the possibility that the first passenger will pick the last passengers seat as the random seat. So all others will sit on their own seat and the last one will sit on the first person's seat.

[Guest]

100% ... if the first man is in any of the others' seats, he will be asked to move until he ultimately is seated correctly.

[peace*out]

100% ... if the first man is in any of the others' seats, he will be asked to move until he ultimately is seated correctly.

not necessarily (i think)

there will be two seats left (him, and the other passenger)...

so would that be 50%??

or are you asking whether he would NEVER get asked to move??

[Guest]

...each passenger that gets on sits in his assigned seat if it is available or a random seat if it is not.

[bonanova]

All that matters is this:

Does someone sit in Paul's seat before Peter boards?

If so, Peter gets his seat. Otherwise he get's Paul's seat.

Those are the only places Peter can sit.

The answer is independent of N.

You can work it out for small values of N - it's always 1/2.

[pdqkemp]

All that matters is this:

Does someone sit in Paul's seat before Peter boards?

If so, Peter gets his seat. Otherwise he get's Paul's seat.

Those are the only places Peter can sit.

The answer is independent of N.

You can work it out for small values of N - it's always 1/2.

For very small values, like N = 2 and N = 3 I can fully understand why it would be 1/2. As soon as N becomes higher than that, wouldn't the probability start falling?

Just imagine N = 4. The first man does NOT sit in his seat because he lost his pass. (He had a 1/4 chance of NOT sitting in his seat in the first place.) Now Passenger #2 has a 1/3 chance it was his seat that was just taken, and if it WAS taken, he has a 1/3 chance of sitting in the final passenger's seat, a 1/3 chance of sitting in the first man's seat, and a 1/3 chance that he'll sit in Passenger #3's seat.

Then Passenger #3 comes on. Now IF either the first man OR Passenger #2 took his seat, he has a 1/2 chance of taking the final passenger's seat.

I'm sure I'm missing something in my logic. It seems to me that the more passenger's there are on the plane, the lower the probability that the last man's seat would be available.

Can you help me understand more clearly why I'm wrong?

Edited February 6, 2011 by pdqkemp

[Guest]

passenger 1. a 1/5 chance of taking the last passengers seat.

(he can potentially sit in his own seat, as he picks one at random.)

passenger 2. a 1/4 *1/5 chance of taking the last passengers seat.

passenger 3. a 1/3 *1/4 *1/5 +1/3 *1/5 chance of taking the last passengers seat.

passenger 4. a 1/2 *1/3 *1/4 *1/5 +1/2 *1/5 +1/2 *1/4 *1/5 chance of taking the last passenger's seat.

therefore for passenger 5, he has a

1/2 *1/3 *1/4 *1/5 +1/2 *1/5 +1/2 *1/4 *1/5 +1/3 *1/4 *1/5 +1/3 *1/5 +1/4 *1/5 +1/5 =

1/120 +1/10 +1/40 +1/60 +1/15 +1/20 +1/5 =

1/120 +12/120 +3/120 +2/120 +8/120 +10/120 +24/120 =

60/120 =

1/2 chance of sitting in the wrong seat.

[Guest]

edit: didn't get it in time

passenger 1. a 1/5 chance of taking the last passengers seat.

(he can potentially sit in his own seat, as he picks one at random.)

passenger 2. a 1/4 *1/5 chance of taking the last passengers seat.

passenger 3. a 1/3 *1/4 *1/5 +1/3 *1/5 chance of taking the last passengers seat.

passenger 4. a 1/2 *1/3 *1/4 *1/5 +1/2 *1/3 *1/5 +1/2 *1/5 +1/2 *1/4 *1/5 chance of taking the last passenger's seat.

therefore for passenger 5, he has a

1/2 *1/3 *1/4 *1/5 +1/2 *1/3 *1/5 +1/2 *1/5 +1/2 *1/4 *1/5 +1/3 *1/4 *1/5 +1/3 *1/5 +1/4 *1/5 +1/5 =

1/120 +1/10 +1/30 +1/40 +1/60 +1/15 +1/20 +1/5 =

1/120 +12/120 4/120 +3/120 +2/120 +8/120 +10/120 +24/120 =

64/120 = 8/15

.533 chance of sitting in the wrong seat.

[Guest]

All that matters is this:

Does someone sit in Paul's seat before Peter boards?

If so, Peter gets his seat. Otherwise he get's Paul's seat.

Those are the only places Peter can sit.

The answer is independent of N.

You can work it out for small values of N - it's always 1/2.

Excellent job Bonanova! very nicely done!

although the last guy's name was actually Jeff.

Edited February 6, 2011 by magician

[bonanova]

For very small values, like N = 2 and N = 3 I can fully understand why it would be 1/2. As soon as N becomes higher than that, wouldn't the probability start falling?

Just imagine N = 4. The first man does NOT sit in his seat because he lost his pass. (He had a 1/4 chance of NOT sitting in his seat in the first place.) Now Passenger #2 has a 1/3 chance it was his seat that was just taken, and if it WAS taken, he has a 1/3 chance of sitting in the final passenger's seat, a 1/3 chance of sitting in the first man's seat, and a 1/3 chance that he'll sit in Passenger #3's seat.

Then Passenger #3 comes on. Now IF either the first man OR Passenger #2 took his seat, he has a 1/2 chance of taking the final passenger's seat.

I'm sure I'm missing something in my logic. It seems to me that the more passenger's there are on the plane, the lower the probability that the last man's seat would be available.

Can you help me understand more clearly why I'm wrong?

If Paul sits in his own seat, then everyone does. Clearly, that becomes more and more unlikely [p=1/N] as N increases.

But if at any time someone sits in Paul's seat [doesn't have to be Paul himself] then the situation fixes itself and everyone after that gets his own seat. This gives you more chances. Here's how that might work out.

Let's say Paul doesn't sit in his own seat, instead, he sits in Andy's seat. All the passengers that board after Paul and before Andy get to sit in their own seats. But now Andy boards. He can't sit in his own seat, Paul is in it. Well, he might sit in Paul's seat, and if he does, then everyone after Andy, including Peter, gets his own seat.

Let's say that when Andy boards, there are M<N empty seats. Clearly we have the whole problem starting over again - a passenger boards [that's Andy] and, if he sits in a certain seat [this time it's Paul's seat, not his own, but that doesn't matter] then everyone after him gets his own seat. But now the probability has improved from 1/N to 1/M.

The whole scenario plays out again, but now with smaller numbers. If Andy doesn't sit in Paul's seat, but rather sits in Bob's seat, then every passenger between Andy and Bob gets his own seat. But now Bob boards, and the number of empty seats is P<M<N. If Bob sits in Paul's seat then everything is OK again. And the probability of that has improved to 1/P. And we see what happens when P gets down to 2.

[bonanova]

There is a succession of passengers, beginning with Paul, whose choice of seat is not guided by a boarding pass. Either the pass is misplaced, as in Paul's case, or someone [that would be Paul, or the one in whose seat Paul sat, or ... etc.] has already taken the passenger's seat. The other passengers all take their own seats.

In the exceptional cases, however, there are exactly two events that will seal the final result right then and there. Moreover, these are the only events that affect the outcome.

.

1. The passenger chooses Paul's seat.

2. The passenger chooses Peter's seat.

.

In the first case, Peter will get his own seat. In the second case, he will not.

The only thing to understand, therefore, is that these two events have exactly the same probability, namely p=1/Q, where Q is the number of empty seats at the time the choice is made. They are unlikely choices at the start, where the number of seats to choose from is large, and they become more likely as the plane fills up. But they are the only choices that matter, and they are, always, equally likely.

The chance that Peter gets his own seat is thus inescapably 1/2.

[pdqkemp]

There is a succession of passengers, beginning with Paul, whose choice of seat is not guided by a boarding pass. Either the pass is misplaced, as in Paul's case, or someone [that would be Paul, or the one in whose seat Paul sat, or ... etc.] has already taken the passenger's seat. The other passengers all take their own seats.

In the exceptional cases, however, there are exactly two events that will seal the final result right then and there. Moreover, these are the only events that affect the outcome.

.

1. The passenger chooses Paul's seat.

2. The passenger chooses Peter's seat.

.

In the first case, Peter will get his own seat. In the second case, he will not.

The only thing to understand, therefore, is that these two events have exactly the same probability, namely p=1/Q, where Q is the number of empty seats at the time the choice is made. They are unlikely choices at the start, where the number of seats to choose from is large, and they become more likely as the plane fills up. But they are the only choices that matter, and they are, always, equally likely.

The chance that Peter gets his own seat is thus inescapably 1/2.

Thank you VERY much! This explanation was a very clear way to illustrate the concept. I appreciate the extra time you gave here! Thanks again!

[Guest]

There is a succession of passengers, beginning with Paul, whose choice of seat is not guided by a boarding pass. Either the pass is misplaced, as in Paul's case, or someone [that would be Paul, or the one in whose seat Paul sat, or ... etc.] has already taken the passenger's seat. The other passengers all take their own seats.

In the exceptional cases, however, there are exactly two events that will seal the final result right then and there. Moreover, these are the only events that affect the outcome.

.

1. The passenger chooses Paul's seat.

2. The passenger chooses Peter's seat.

.

In the first case, Peter will get his own seat. In the second case, he will not.

The only thing to understand, therefore, is that these two events have exactly the same probability, namely p=1/Q, where Q is the number of empty seats at the time the choice is made. They are unlikely choices at the start, where the number of seats to choose from is large, and they become more likely as the plane fills up. But they are the only choices that matter, and they are, always, equally likely.

The chance that Peter gets his own seat is thus inescapably 1/2.

Actually, i don't think the problem is this simple.

A passenger will need to chose a new seat ONLY if his seat is taken, and that results in a different probability then 1/Q. It's actually 1/N * P, where N is number of remaining seats at the moment he has to board, and P is the probability that his seat will be taken.

If N, the number of remaining seats is easy to compute, P however is not.

Let's try an example to be more clear:

passenger 1 boards, takes a random seat. 1/N probability that he will sit in his own seat and the problem is solved from the start. (n-1) / n is the probability he will not.

Passenger 2 boards. there is a 1/N probability that his seat is taken, so he will need to randomly chose another from the remaining N-1 . He has a 1/ (N-1) probability to sit in passenger 1s sear and the problem is again solved ( with the probablity of 1/( N(N-1) ). and there is a probability of (N-2)/ (N-1) that he will chose a wrong seat and pass the problem on the number 3 ( final probability being (N-2)/( N(N-1) ).

And so on for 3,4,5 etc , with the numbers becoming more and more complicated as we go along.

One way i see this problem, since probability is additive is like this:

The probability for the Nth passenger to sit in his sear is the sum of:

P(1)+ P(2) + P(3) + .... + P (N-1), where

P(i) is the probability that the seating problem will get solved in i steps.

P(1) means passenger 1 takes his seat from the start, which is 1/N. all other passengers will then sit in their seats.

P(2) means passenger 1 takes a wrong seat and ONLY one passenger needs to relocate, and chooses passenger 1's seat.

p(3) means 3 passengers exchange seats and solve the wrong seating.

p(4) means 4 passengers exchange seats and solve the problem.

..............

P(N-1) means all passengers before the last guy exchange seats and solve the problem, right before number N takes his seat.

Now, this sum might end up being 1/2, but i am reluctant to accept that result without a solid mathematical proof to it.

[bonanova]

Actually, i don't think the problem is this simple.

Actually, it is that simple.

Again, let Paul be the first passenger to board and Peter be the last passenger to board.

When Peter boards, at least one of his or Paul's seat is taken.

Possibly by Paul, who blindly choose from all the seats [which includes Peter's and Paul's]

Otherwise by a passenger who finds his seat occupied and chooses at random from the empty seats [which include Peter's and Paul's]

Thus Peter's or Pauls' seat with equal probability has become occupied by the time Peter boards.

So when Peter enters, his sits, with equal probability, in either Paul's seat, or his own.

You can reason why it could not be any other seat.