Results 1 to 15 of 25
Thread: Last in line

20041020, 22:49 #1
 Join Date
 Sep 2001
 Location
 Prescott, Arizona, USA
 Posts
 286
 Thanks
 0
 Thanked 1 Time in 1 Post
Last in line
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.Michael

20041021, 00:20 #2
 Join Date
 Nov 2001
 Location
 Melbourne, Victoria, Australia
 Posts
 5,016
 Thanks
 0
 Thanked 0 Times in 0 Posts
Re: Last in line
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

20041021, 08:45 #3
 Join Date
 Feb 2004
 Location
 Cape Town, RSA
 Posts
 3,444
 Thanks
 0
 Thanked 1 Time in 1 Post
Re: Last in line
And what are the chances of Allan being correct if there were 100 of these questions asked! <img src=/S/laugh.gif border=0 alt=laugh width=15 height=15>
Regards,
Rudi

20041021, 10:01 #4
 Join Date
 Nov 2001
 Posts
 10,550
 Thanks
 0
 Thanked 7 Times in 7 Posts
Re: Last in line
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
 <LI>Sit in your seat<LI>Sit in the seat corresponding to the lost ticket<LI>Sit in the seat of a passenger who has not yet boarded
So I reckon that on this interpretation you have exactly a 50% chance of getting your assigned seat.
StuartR

20041021, 13:50 #5
 Join Date
 Sep 2001
 Location
 Prescott, Arizona, USA
 Posts
 286
 Thanks
 0
 Thanked 1 Time in 1 Post
Re: Last in line
opps, yes there are 100 seats
Michael

20041022, 06:06 #6
 Join Date
 Nov 2001
 Location
 Melbourne, Victoria, Australia
 Posts
 5,016
 Thanks
 0
 Thanked 0 Times in 0 Posts
Re: Last in line
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. <img src=/S/smile.gif border=0 alt=smile width=15 height=15>
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.

20041022, 11:03 #7
 Join Date
 Nov 2001
 Posts
 10,550
 Thanks
 0
 Thanked 7 Times in 7 Posts
Re: Last in line
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

20041022, 11:15 #8
 Join Date
 Feb 2004
 Location
 Cape Town, RSA
 Posts
 3,444
 Thanks
 0
 Thanked 1 Time in 1 Post
Re: Last in line
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! <img src=/S/laugh.gif border=0 alt=laugh width=15 height=15>
Regards,
Rudi

20041022, 13:02 #9
 Join Date
 Nov 2001
 Location
 Melbourne, Victoria, Australia
 Posts
 5,016
 Thanks
 0
 Thanked 0 Times in 0 Posts
Re: Last in line
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

20041022, 13:46 #10
 Join Date
 Nov 2001
 Posts
 10,550
 Thanks
 0
 Thanked 7 Times in 7 Posts
Re: Last in line
> 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.
<UL><LI>Each person getting on either has their own seat free, or chooses a random seat.
<LI>If they choose a random seat then they can AT MOST displace one person from their correct seat
<LI>If they displace someone else then they must leave your seat and the original lost ticket seat vacant
<LI>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
<LI>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

20041022, 13:57 #11
 Join Date
 Jul 2002
 Location
 Pittsburgh, Pennsylvania, USA
 Posts
 11,225
 Thanks
 14
 Thanked 342 Times in 335 Posts
Re: Last in line
<hr>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.<hr>
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

20041022, 14:25 #12
 Join Date
 Nov 2001
 Posts
 10,550
 Thanks
 0
 Thanked 7 Times in 7 Posts
Re: Last in line
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

20041022, 14:42 #13
 Join Date
 Jul 2002
 Location
 Pittsburgh, Pennsylvania, USA
 Posts
 11,225
 Thanks
 14
 Thanked 342 Times in 335 Posts
Re: Last in line
My mistake, I didn't reread your previous post. I was thinking purely random.
Steve

20050311, 10:49 #14
 Join Date
 Feb 2001
 Location
 New York, New York, USA
 Posts
 768
 Thanks
 0
 Thanked 0 Times in 0 Posts
Re: Last in line
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(Location Australia, then UK, but now USA. Heart, outlook, attitude, etc always Australian)
Quote: "All Happiness is the release of internal pressure"

20050311, 20:11 #15
 Join Date
 Sep 2002
 Location
 Stafford, Staffordshire, England
 Posts
 585
 Thanks
 0
 Thanked 0 Times in 0 Posts
Re: Last in line
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.<font color=blue><font face="Script MT Bold"><big>Rob</big></font face=script></font color=blue>