Last in line

Topic

New Reply

100 people waiting to get onto the plane. You are last in line. Each person has a boarding pass with an assigned seat. The first person to board, drops his pass before he gets on and does not remember what seat that he was assigned so he randomly takes a seat. Each person boarding thereafter may or may not sit in their assigned seat. What are the odds that you will be able to sit in the seat assigned to you.

BTW, I do not know the answer, just trying to help a friend out.

Reply | Quote

Replies

It would depend on how many seats there are on the plane. Just to get the terms of the problem clear, is it equivalent to 99 people selecting seats at random, and the 100th person wondering what the probability of their allocated seat not being occupied is?

With a total of n seats available, and r passengers ahead of you, occupying seats at random, then the probability that your allocated seat will still be vacant when your turn comes is:

(n – r) / n

So if there were 120 seats total, in your case it’s (120 – 99) / 120 = 21/120 = 0.175. If there were only 100 seats total, it drops to 1/100.

Alan

Reply | Quote

And what are the chances of Allan being correct if there were 100 of these questions asked!

Reply | Quote

And what are the chances of Allan being correct if there were 100 of these questions asked!

Reply | Quote

opps, yes there are 100 seats

Reply | Quote

According to Stuart’s interpretation, which is the most likely one in reality I’d think, then the situation becomes very complex in my estimation. Despite the 3 “simple” choices for each passenger, I can’t see how he arrives at 50% as the answer. My attempts lead to tree diagrams that look like the proverbial impenetrable jungle. But Stuart has a knack for seeing the forest for the trees with such problems, so hopefully he can explain further.

Alan

Edited – Looking more closely at some possibilities, using Stuart’s assumptions, it does appear that the probability is 50% (tried cases for 4 and 8 passengers). Interestingly, the last person in the queue would either end up in their correct seat, or in the one designated to the first person in the queue, who lost their seat allocation pass, if Stuart’s “rules” are followed.

Reply | Quote

Alan,

At each point in the tree there are 3 possibilities. 2 of them (take your seat, take the seat for the missing ticket) will end the tree AND THEY ARE EQUALLY LIKELY. The other – at unknown probability, will lead to the same situation occuring again and again until one of the two equally likely events terminates the tree.

StuartR

Reply | Quote

I just think they should throw the guy out of the plane who does not have his boarding pass – and that will clear up the whole messy scenario!

Reply | Quote

I just think they should throw the guy out of the plane who does not have his boarding pass – and that will clear up the whole messy scenario!

Reply | Quote

Stuart,

I can verify exactly what you say from the sample scenarios (trees) I’ve created. I’m afraid though, that this is one of those ones I just can’t “see” (picture/ visualize) the way you obviously can. Unfortunately, this situation has now unleashed a monster, and I’m going to have to see through a formal analysis for the general case!

Just for interest, does your insightful approach also predict that the last person will end up with either their correct seat, or the allocated seat of the first person?

Alan

Reply | Quote

> does your insightful approach also predict that the last person will end up with either their correct seat, or the allocated seat of the first person
Absolutely it does.

• Each person getting on either has their own seat free, or chooses a random seat.
• If they choose a random seat then they can AT MOST displace one person from their correct seat
• If they displace someone else then they must leave your seat and the original lost ticket seat vacant
• So IF a person boarding finds their seat occupied then the choice of seats they have MUST include your seat and the seat for the original lost ticket
• This applies to all passengers as they board – right up to the last one (you) who will find either your own seat free, or the one from the lost ticket.
  [/list]StuartR

Reply | Quote

[indent]

---

This applies to all passengers as they board – right up to the last one (you) who will find either your own seat free, or the one from the lost ticket.

---

[/indent]

I don’t follow this logic.
If the 1st person to board, takes a random seat he has a 1/100 chance of taking the seat of the lost ticket person and a 1/100 chance of taking your seat. So there is possibility that he will take your seat. Let’s assume that he does.

Person2, has a 1/99 chance of taking the “lost ticket” seat, 0/99 chance of taking your seat (already taken). Let’s assume he takes the lost ticket seat.

When you come, you have no chance of getting either the lost ticket seat or your seat. There are also many other scenarios of 2 people before you taking the “2 seats” so that you would get neither.

Steve

Reply | Quote

The scenario I described said that each person took their own seat if it is available, they only take a random seat if their’s is occupied.

If person 2 takes my seat, then everyone else takes their own seat and I get the one corresponding to the lost ticket.

StuartR

Reply | Quote

My mistake, I didn’t re-read your previous post. I was thinking purely random.

Steve

Reply | Quote

My mistake, I didn’t re-read your previous post. I was thinking purely random.

Steve

Reply | Quote

The scenario I described said that each person took their own seat if it is available, they only take a random seat if their’s is occupied.

If person 2 takes my seat, then everyone else takes their own seat and I get the one corresponding to the lost ticket.

StuartR

Reply | Quote

[indent]

---

This applies to all passengers as they board – right up to the last one (you) who will find either your own seat free, or the one from the lost ticket.

---

[/indent]

I don’t follow this logic.
If the 1st person to board, takes a random seat he has a 1/100 chance of taking the seat of the lost ticket person and a 1/100 chance of taking your seat. So there is possibility that he will take your seat. Let’s assume that he does.

Person2, has a 1/99 chance of taking the “lost ticket” seat, 0/99 chance of taking your seat (already taken). Let’s assume he takes the lost ticket seat.

When you come, you have no chance of getting either the lost ticket seat or your seat. There are also many other scenarios of 2 people before you taking the “2 seats” so that you would get neither.

Steve

Reply | Quote

> does your insightful approach also predict that the last person will end up with either their correct seat, or the allocated seat of the first person
Absolutely it does.

• Each person getting on either has their own seat free, or chooses a random seat.
• If they choose a random seat then they can AT MOST displace one person from their correct seat
• If they displace someone else then they must leave your seat and the original lost ticket seat vacant
• So IF a person boarding finds their seat occupied then the choice of seats they have MUST include your seat and the seat for the original lost ticket
• This applies to all passengers as they board – right up to the last one (you) who will find either your own seat free, or the one from the lost ticket.
  [/list]StuartR

Reply | Quote

Stuart,

I can verify exactly what you say from the sample scenarios (trees) I’ve created. I’m afraid though, that this is one of those ones I just can’t “see” (picture/ visualize) the way you obviously can. Unfortunately, this situation has now unleashed a monster, and I’m going to have to see through a formal analysis for the general case!

Just for interest, does your insightful approach also predict that the last person will end up with either their correct seat, or the allocated seat of the first person?

Alan

Reply | Quote

Alan,

At each point in the tree there are 3 possibilities. 2 of them (take your seat, take the seat for the missing ticket) will end the tree AND THEY ARE EQUALLY LIKELY. The other – at unknown probability, will lead to the same situation occuring again and again until one of the two equally likely events terminates the tree.

StuartR

Reply | Quote

opps, yes there are 100 seats

Reply | Quote

It would depend on how many seats there are on the plane. Just to get the terms of the problem clear, is it equivalent to 99 people selecting seats at random, and the 100th person wondering what the probability of their allocated seat not being occupied is?

With a total of n seats available, and r passengers ahead of you, occupying seats at random, then the probability that your allocated seat will still be vacant when your turn comes is:

(n – r) / n

So if there were 120 seats total, in your case it’s (120 – 99) / 120 = 21/120 = 0.175. If there were only 100 seats total, it drops to 1/100.

Alan

Reply | Quote

Another possible interpretation…

There are 100 seats in total.
Each person occupies their allocated seat if it is free, otherwise they take a seat at random.

Analysing this for each of the remaining 98 passengers in front of you shows that if their seat is already occupied they may

1. Sit in your seat
2. Sit in the seat corresponding to the lost ticket
3. Sit in the seat of a passenger who has not yet boarded

If they choose 1. or 2. (both equally likely) then everyone boarding after them gets their allocated seat, and you have a 50% chance of getting your own seat. If they choose 3. then eventually someone else will have to choose 1. or 2.

So I reckon that on this interpretation you have exactly a 50% chance of getting your assigned seat.

StuartR

Reply | Quote

Another possible interpretation…

There are 100 seats in total.
Each person occupies their allocated seat if it is free, otherwise they take a seat at random.

Analysing this for each of the remaining 98 passengers in front of you shows that if their seat is already occupied they may

1. Sit in your seat
2. Sit in the seat corresponding to the lost ticket
3. Sit in the seat of a passenger who has not yet boarded

If they choose 1. or 2. (both equally likely) then everyone boarding after them gets their allocated seat, and you have a 50% chance of getting your own seat. If they choose 3. then eventually someone else will have to choose 1. or 2.

So I reckon that on this interpretation you have exactly a 50% chance of getting your assigned seat.

StuartR

Reply | Quote

I really liked Stuart’s answer to this. Someone else asked me this question and I got to thinking about it. As mentioned, the first passanger sits down and forces other people to randomly sit elsewhere if their seat is taken. From a probability point of view this is exactly the same as if the passanger whose seat is taken forced the first passanger to move hey, mate, you are in my seat, shove off.

In that case, we come down to the 100th passanger and the seat free is either his or the first passanger – hence a 50/50 chance.

With this approach, we can easily handle the situation that the nth passanger drops their boarding pass (same answer) or n passangers drop their boarding passes [1 / (n+1)].

If we look at the first passanger as he is pushed from seat to seat, what is the average number of times that he has to move? i think that this question might be on the tough side – i’m going to tackle it with a simulation program

Reply | Quote

Irrespective of the mathematical niceties expressed thus far, surely the problem has been overcomplicated. Doesn’t the situation boil down to the folllowing simple scenario:

Last in line boards plane
One seat available
99 seats are not assigned whereas only one is
Hence 1/100 chance that it is the assigned seat?

Isn’t this puzzle equivalent to having 100 cards spread out, face down. 99 have red spots and one has a black spot. What is the chance of picking out the card with the black spot?

Random seats and assigned seats are red herrings.

Reply | Quote

The short answer is NO. There are 100 seats assigned, not 1 but 1 of them has lost their assignment / boarding pass.

Using your card analogy, its like having 98 red cards face up and two cards face down (one red and one black). You work your way through the pile putting the red cards in one group and the black card in the other group. What is the probability that you have put the black card in the right group?

Reply | Quote

Sorry Tim, but I disagree. Chap or chapette gets onto plane. One seat available. 99 seats are assigned to others. The chance that that particular seat is his/hers is 1/100. The chance that it isn’t is 99/100.

Reply | Quote

This implies that if the chance of his/her seat is 1/100, the chance of sitting in the non-boarding pass seat is 99/100. There is no chance that the seat he/she will get is any of the others based on the puzzle conditions: people choose their own seat unless someone is in it.

I can’t see the prob of getting in the non-boarding pass seat as that high…

Steve

Reply | Quote

Did you read the part about the other passangers take their assigned seats if they can or select a random seat if their’s is taken – it isn’t in the original question but it is included in a follow-up post.

Other than actually going through the math and / or pointing you to the other posts, I don’t know how to clarify – maybe a simple example where you are the last passanger and the seats are allocated 1st passanger = seat 1, 2nd passanger = seat 2, …

Imagine we have 2 seats. First passenger gets on and randomly selects seat #1 or #2 – hence you have a 50/50 chance of getting your seat. (not the best example because both our approaches give the same answer)

Imagine we have 3 seats. First passenger gets on and takes seat 1 – hence you will get your seat 100% of the time. If the first passanger takes seat 3, then you will get your seat 0% of the time. If the first passanger takes seat 2, then the second passanger has to select a seat randomly and you have a 50/50 chance of getting your seat. So, 1/3 * 100% + 1/3 * 0% + 1/3 * 50% = 50%

Imagine we have 4 seats, First passenger gets on and takes seat 1 – hence you will get your seat 100% of the time. If the first passanger takes seat 4, then you will get your seat 0% of the time. If the first passanger takes seat 2, then the second passanger has to select a seat randomly between the 3 remaining seats. Hang on – 1 passanger selecting between 3 random seats – that is very familiar – in fact it is the same as if we had 3 seats and the passanger forgot his seat – so that answer is 50%. So, 1/4 * 100% + 1/4 * 0% + 2/4 * 50% = 50%.

I is recursive because a passanger forgetting their seat and selecting randomly is the same (from a probability point of view) as being forced to select randomly because their allocacted seat was taken.

Reply | Quote

I’ve put together a simple spreadsheet with vba that simulates the boarding of the plane. Person #1, assuming he gets kicked out of incorrect seats has to move an average of 4.1877 times. I also generated an answer for the 100th passanger getting the correct seat (50% looks ok from the simulation data).

Reply | Quote

Just got back from a few days in Lincolnshire so apologies for the delay in responding. My original responses were based on a knee-jerk reaction to a quick scan of the puzzle. I simply didn’t read the question thoroughly.
I plead tiredness and chronic stupidity in my defence. I must learn to follow my own exhortations in future to prevent embarrassment.

Reply | Quote

Don’t feel bad. Your impression and post was the same impression I had (see my earlier post) until it was explained to me that people would choose their own seat if available…

And you had to read more than the puzzle to get this. It is not clear from the puzzle as written, but came out of the discussions.

Steve

Reply | Quote

Thanks Steve. Believe me, your words make me feel a whole lot better. You ought to take up counselling, if you don’t do so already.

Reply | Quote

Out of all the possibilities when the last comes in, he will have one of 2 seats: his own, or the seat of the man with no boarding pass.

There are 2 seats he will have and he will have an equal chance of them so he has a 50% of being in his own. There is not a possibilty of another seat. (unless you can work up an example where he could get a different seat…)

You can see it by starting with 3 seats and 3 people, and work your way up. Each one has a prob of 50% of getting your own seat…

This assumes, of course, that everyone sits in the correct seat, unless someone is in it, and politely chooses another seat.

Steve

Reply | Quote

For my answer I’ll forego math and go by simple airline rules and say that if you have a boarding pass that shows your assigned seat, you’ll be able to sit in your own seat with no problems. Probability = 100% or 1 or however it is that you express probability.

Reply | Quote