Brain Teasers
Crazy Guy on the Plane
Probability
Probability puzzles require you to weigh all the possibilities and pick the most likely outcome.Probability
A line of 100 airline passengers is waiting to board a plane. They each hold a ticket to one of the 100 seats on that flight. (For convenience, let's say that the nth passenger in line has a ticket for the seat number n.)
Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. All of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. If it is occupied, they will then find a free seat to sit in, at random.
What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?
Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. All of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. If it is occupied, they will then find a free seat to sit in, at random.
What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?
Hint
The whole thing stops when someone else sits in Crazy Guy's seat.Answer
The whole thing stops when someone else sits in Crazy Guy's seat. The chances of that range from 1/99 (First person) to 1/1 for the last guy. So:1/99 + Summation from 98 to 2 of ( 1/ n(n+1) )
This returns 0.5 or 50%.
Also, the answer remains 50% no matter how many people are added to the line!
Hide Hint Show Hint Hide Answer Show Answer
What Next?
View a Similar Brain Teaser...
If you become a registered user you can vote on this brain teaser, keep track of which ones you have seen, and even make your own.
Solve a Puzzle
Comments
what if the crazy guy had a gun?
perhaps the man isn't 'crazy' at all -- perhaps he is fed up with being treated as cattle and is bored with the orderly way of life and wants to mix it up a bit. Also, wouldn't a flight attendant ask the crazy passenger to return to their correct seat?
Not if he had a gun.
You handle comments so well. (And for the record, I stink at probability questions--for now).
that was dumb
great puzzle. way to go!!
Good one!
this is a good riddle and your answer is not altogether unimpressive, but i'm afraid your logic is flawed. you see, you've determined that the liklihood of someone other than the 100th passenger sitting in the crazy man's seat is 50%, and it's true that once someone sits in the crazy man's seat, then the 100th passenger is guaranteed to sit in his own assigned seat. however, you don't take into account the possibility of a bumped passenger sitting in the 100th passenger's seat, thereby ruining everything. also, there's a 1/100 chance that the crazy man will sit in the 100th passenger's seat as well. you are right to have an equation with a summation as you have done, but i'm afraid it's much more complicated.
in addition to figuring out the probability of someone other than #100 sitting in the crazy man's seat, you must also factor in the chance that a passenger bumped from his/her seat will sit in passenger 100's seat. in other words, if the crazy man sits in #2's seat, then #2 has a 1/99 chance of sitting in #100's seat.
so let's figure out the liklihood of each individual passenger taking #100's seat. passenger #1 has a 1/100 chance of sitting in his own seat, enabling everyone to sit in assigned seats, and a 99/100 chance of sitting in someone else's seat. if he sits in someone else's seat, he then has two more options: sitting in #100's seat or sitting in a seat other than #100's.
so the probability of passenger 1 messing up the whole process is:
99/100 (probability that he won't sit in his own seat) * 1/99 (probability he'll ruin everything by sittin in #100's seat)
the probability of passenger 2 messing up everything is:
1/100 (probability that his seat is already taken) * 1/99 (probability he'll ruin everything by sittin in #100's seat)
so rather than:
1/99 + Summation from 98 to 2 of ( 1/ n(n+1) ) ,
it should look more like:
100-n/100 * summation from 99 to 2 of [(-1 + n)/100] * [1/(101-n)]
this gives you the final answer of rougly a 3.19% chance of #100 sitting in his or her correct seat.
in addition to figuring out the probability of someone other than #100 sitting in the crazy man's seat, you must also factor in the chance that a passenger bumped from his/her seat will sit in passenger 100's seat. in other words, if the crazy man sits in #2's seat, then #2 has a 1/99 chance of sitting in #100's seat.
so let's figure out the liklihood of each individual passenger taking #100's seat. passenger #1 has a 1/100 chance of sitting in his own seat, enabling everyone to sit in assigned seats, and a 99/100 chance of sitting in someone else's seat. if he sits in someone else's seat, he then has two more options: sitting in #100's seat or sitting in a seat other than #100's.
so the probability of passenger 1 messing up the whole process is:
99/100 (probability that he won't sit in his own seat) * 1/99 (probability he'll ruin everything by sittin in #100's seat)
the probability of passenger 2 messing up everything is:
1/100 (probability that his seat is already taken) * 1/99 (probability he'll ruin everything by sittin in #100's seat)
so rather than:
1/99 + Summation from 98 to 2 of ( 1/ n(n+1) ) ,
it should look more like:
100-n/100 * summation from 99 to 2 of [(-1 + n)/100] * [1/(101-n)]
this gives you the final answer of rougly a 3.19% chance of #100 sitting in his or her correct seat.
I agree that the initial summation is incomplete because it does not account for the times when someone else sits in passenger #100's seat, but your (daddyvwald) equation is also flawed. While it is true for #2 that the probability the crazy guy is in his seat is 1/100, and then he would have a 1/99 chance of sitting in #100's seat, this is not the case for passenger #3. For #3, one of two things has to have happened for him to be looking for another seat. Either #1 sat in his seat (1/100) or #1 sat in #2's seat and he sat in #3's seat [(1/100)*(1/99)]. Your summation assumes everyone's probability of being displaced is linear, which it is not. The answer should indeed be 50%, and can best be determined with much smaller numbers of passengers. It is trivial to see that if there are two seats on the plane, the probability of passenger 2 sitting in the right seat is 50%. With three seats, the probability of passenger 3 sitting in the right seat is the probability that the first passenger sits in the right seat plus the probability he sits in the wrong seat and it is #2's, who then sits in #1's seat. This is (1/3) + (1/3)*(1/2) = 1/2. The math gets longer for 4 seats on the plane and higher, but the answer keeps constant at 1/2.
I understood the teaser, and the answer is 50% as stated but I never understood the formula (1/99 + the Summation from 98 to 2 of (1/n(n+1))), because the probability of the first person to be seated probable is 1/100 and not 1/99 and the formula does not yield 0.5 as stated. Plus this solution doesn't appear to take into consideration that last seat could be taken by any of the crazy people(or those lost their seats) on the plane.
Let's first redefine the concept of crazy in this teaser, the crazy guy is someone who sits randomly, i.e. the first passenger is crazy, and any other passenger who finds his seat occupied becomes crazy too (notice that any crazy guy has the first seat to end the crazyness).
Let's define the function 'F', where F(N) is the solution for the "Crazy Guy On The Plane" problem for N passengers and N seats, i.e. the probability of the Nth person be seated correctly for a queue of N passengers and N seats. Note that F(1) = 1, no other choice, and F(2) = 0.5 ,only two choices.
Our goal is find F(100).
For the general case of N passengers, the first guy has the probability of (1/N) to sit in any seat, if he chooses to sit in the first seat then there is only one choice to continue and the solution would be F(1)=1, if he chooses to sit the second to last (seat no [N - 1]) then this becomes a crazy problem only for the last two passengers and has the solution F(2), and if the first guy sits in seat [N-2] this is a crazy problem for the last three with the solution F(3), so on and so forth. Each of these cases has the chance of (1/N) for happenning.
Thus F(N)=(1/N)*F(N-1)+(1/N)*F(N-2)+...+ (1/N)*F(2)+(1/N)*F(1), N>1
So N*F(N)=F(N-1)+F(N-2)+...+F(2)+F(1), N>1
the same way you find:
(N+1)*F(N+1)=F(N)+F(N-1)+...+F(2)+F(1), N>1
So (N+1)*F(N+1)=F(N)+N*F(N) , N>1
which yields F(N+1)=F(N) for each N>1
so F(100)=F(99)=...=F(2)=0.5
If the number of passengers is greater or equal to 2 then the probability of the last person to be seated in his designated seat is always 50%.
Let's define the function 'F', where F(N) is the solution for the "Crazy Guy On The Plane" problem for N passengers and N seats, i.e. the probability of the Nth person be seated correctly for a queue of N passengers and N seats. Note that F(1) = 1, no other choice, and F(2) = 0.5 ,only two choices.
Our goal is find F(100).
For the general case of N passengers, the first guy has the probability of (1/N) to sit in any seat, if he chooses to sit in the first seat then there is only one choice to continue and the solution would be F(1)=1, if he chooses to sit the second to last (seat no [N - 1]) then this becomes a crazy problem only for the last two passengers and has the solution F(2), and if the first guy sits in seat [N-2] this is a crazy problem for the last three with the solution F(3), so on and so forth. Each of these cases has the chance of (1/N) for happenning.
Thus F(N)=(1/N)*F(N-1)+(1/N)*F(N-2)+...+ (1/N)*F(2)+(1/N)*F(1), N>1
So N*F(N)=F(N-1)+F(N-2)+...+F(2)+F(1), N>1
the same way you find:
(N+1)*F(N+1)=F(N)+F(N-1)+...+F(2)+F(1), N>1
So (N+1)*F(N+1)=F(N)+N*F(N) , N>1
which yields F(N+1)=F(N) for each N>1
so F(100)=F(99)=...=F(2)=0.5
If the number of passengers is greater or equal to 2 then the probability of the last person to be seated in his designated seat is always 50%.
Well, um, that teaser was umm, simple...
... minded.
... minded.
Nice problem (took 45 mins & 2 sheets of papaer to solve ). Explanation by NomadShadow is good
Great teaser: D
Another way to think of it; there are really only two events that we care about, A: someone sitting in seat 1 (guaranteeing the last guy gets his own seat), B: someone sitting in seat 100(guaranteeing he doesn't). All other seats don't matter. Since events A and B have identical probabilities of happening each time someone chooses a seat at random. The last person will have a 50/50 chance of getting his last seat.
Another way to think of it; there are really only two events that we care about, A: someone sitting in seat 1 (guaranteeing the last guy gets his own seat), B: someone sitting in seat 100(guaranteeing he doesn't). All other seats don't matter. Since events A and B have identical probabilities of happening each time someone chooses a seat at random. The last person will have a 50/50 chance of getting his last seat.
It' a great puzzle!
For me 50% is a not a right answer. I know that is a standard answer in Internet, but I don't believe that!
The true answer is different for each airplane seating capacity.
The normal reasoning is that the 1o.passenger in 1 out of 99 seats at seat #100
The 2o passenger in 98 out of 99 seats at seat #2. (The 1o. passenger not in a seat #2) So the second passenger has 1/99 * 1/98 chance of seating at seat #100. At last, the 98o. passenger (100-2) has 1/(2*3) chance to seat at seat #100.
Summing all, it reaches 50%.
Beautiful, but it not like that! If 1o. passenger seat at #2, the 2o passenger that 1/99 of 1/99 chance to seat at #100. Second, that probabilities are not additive, because are not independent. If one passenger from 1 to N-1 seats at 100o. set, it's impossible for the No. passenger seat at seat #100.
Supposes 3 people in the airplane.
At 50% of cases, the 1o. (and crazy) passenger will choose the seat #3. That finishes the chance of 3o. passenger. At other 50% of cases, the 1o. passenger will choose the seat #2. In that case, there will be 50% chances of 2o. passenger to choose the 1o. seat, so the 3o passenger can seat in your own seat. If the 2o. passenger choose the 3o. seat, it's over. So the probability of 3o. passenger can seat in your own seat is exactly 25% (50% of 50%).
Now we face the problem with 4 seats:
The 1o. passenger in 1 out of 3 seats at 4o. seat (33%). If the 1o. passenger seats at 2o. (1/3) , the 2o. passenger has 1/3 chance to seat at 4o. seat (So 1/3*1/3 = 11,1%). At last, Let's calculate the 3o. passenger probability of seating at #4. It comes from 2 situations.
a) The 1o. passenger seats at #3 (33% chances) and the 2o. passenger seats at #2. The 3o passenger seats at #4 (33%). At sum, 33% of 33% = 11,1%
b) The 1o. passenger seats at #2 (33% chances) and the 2o. passenger seats at #3. The 3o passenger seats at #4 (33%). At sum, 33% of 50% = 11,1% (If 2o. passenger seats at #1, the 3o. passenger seat at #3 - no way!)
So the sum probabilities (#1 + #2 + #3) of seat #4 occupation is 33,3% + 33,3% = 2/3. So 4o. passenger has 33,3% chance to seat at your own seat !
Finally, I've written a Montecarlo program using Visual Basic and simulating 100,000 times. It concludes the same. For the airplanes with 100 seats, the program calculates 48,5%, almost 50%. It's easy to concludes that tends forward 50% for a high capacity airplane!
For me 50% is a not a right answer. I know that is a standard answer in Internet, but I don't believe that!
The true answer is different for each airplane seating capacity.
The normal reasoning is that the 1o.passenger in 1 out of 99 seats at seat #100
The 2o passenger in 98 out of 99 seats at seat #2. (The 1o. passenger not in a seat #2) So the second passenger has 1/99 * 1/98 chance of seating at seat #100. At last, the 98o. passenger (100-2) has 1/(2*3) chance to seat at seat #100.
Summing all, it reaches 50%.
Beautiful, but it not like that! If 1o. passenger seat at #2, the 2o passenger that 1/99 of 1/99 chance to seat at #100. Second, that probabilities are not additive, because are not independent. If one passenger from 1 to N-1 seats at 100o. set, it's impossible for the No. passenger seat at seat #100.
Supposes 3 people in the airplane.
At 50% of cases, the 1o. (and crazy) passenger will choose the seat #3. That finishes the chance of 3o. passenger. At other 50% of cases, the 1o. passenger will choose the seat #2. In that case, there will be 50% chances of 2o. passenger to choose the 1o. seat, so the 3o passenger can seat in your own seat. If the 2o. passenger choose the 3o. seat, it's over. So the probability of 3o. passenger can seat in your own seat is exactly 25% (50% of 50%).
Now we face the problem with 4 seats:
The 1o. passenger in 1 out of 3 seats at 4o. seat (33%). If the 1o. passenger seats at 2o. (1/3) , the 2o. passenger has 1/3 chance to seat at 4o. seat (So 1/3*1/3 = 11,1%). At last, Let's calculate the 3o. passenger probability of seating at #4. It comes from 2 situations.
a) The 1o. passenger seats at #3 (33% chances) and the 2o. passenger seats at #2. The 3o passenger seats at #4 (33%). At sum, 33% of 33% = 11,1%
b) The 1o. passenger seats at #2 (33% chances) and the 2o. passenger seats at #3. The 3o passenger seats at #4 (33%). At sum, 33% of 50% = 11,1% (If 2o. passenger seats at #1, the 3o. passenger seat at #3 - no way!)
So the sum probabilities (#1 + #2 + #3) of seat #4 occupation is 33,3% + 33,3% = 2/3. So 4o. passenger has 33,3% chance to seat at your own seat !
Finally, I've written a Montecarlo program using Visual Basic and simulating 100,000 times. It concludes the same. For the airplanes with 100 seats, the program calculates 48,5%, almost 50%. It's easy to concludes that tends forward 50% for a high capacity airplane!
My Montecarlo simulator program was written in VBA for Excel. The Excel native random number generator is very weak and randomness gets very
affected.
I run my program again, using a more recent random number generator (Mersenne Twister from 2002).
I've got a much more accurate. result. I've got a 49.5% chance for the 100o. passenger in a airplane with 100 seats meets your own seat free. (100,000 simulations)
affected.
I run my program again, using a more recent random number generator (Mersenne Twister from 2002).
I've got a much more accurate. result. I've got a 49.5% chance for the 100o. passenger in a airplane with 100 seats meets your own seat free. (100,000 simulations)
Wow. Thanks for putting all that work into it. That is pretty cool that you ran a computer simulation of this teaser.
Eletrojohn,
Sorry, I've had other interpretation to this problem. I've read the original question in "Car Talk" and I've finally understood that the first passanger can seat even in your own seat (by random)
In that case, the probability is always 50%, for all airplanes capacities.
It's very easy to explain.
The first passanger has 50% chance to solve OK and 50% chance to solve not OK seating at last passanger's seat. In other cases, he causes other "crash". The crashed passanger can solve the problem or causes another crash. If he solves, has 50% to solve OK seating at first passanger's seat and 50% to solve not OK. And so on.
Each crash or postpones the solution or solves 50%-50%.
My other interpretation (The first passanger always seating at other passanger's seat) leads to another problem, that is more envolved than the first one.
Now, the first passanger has 0% chance to solve OK the problem and 100% chance to solve Not OK. In other cases, he causes other "crash". The new crash is 50%-50%, like before.
So the probability that the last passanger find your seat free stays between 0% and 50%. As airplane capacity increase, more crashes and the probability stays closer 50%.
For that new problem, my Montecarlo simulations applies (After I've discovered a analytic solution and finally a general formula)
Sorry, I've had other interpretation to this problem. I've read the original question in "Car Talk" and I've finally understood that the first passanger can seat even in your own seat (by random)
In that case, the probability is always 50%, for all airplanes capacities.
It's very easy to explain.
The first passanger has 50% chance to solve OK and 50% chance to solve not OK seating at last passanger's seat. In other cases, he causes other "crash". The crashed passanger can solve the problem or causes another crash. If he solves, has 50% to solve OK seating at first passanger's seat and 50% to solve not OK. And so on.
Each crash or postpones the solution or solves 50%-50%.
My other interpretation (The first passanger always seating at other passanger's seat) leads to another problem, that is more envolved than the first one.
Now, the first passanger has 0% chance to solve OK the problem and 100% chance to solve Not OK. In other cases, he causes other "crash". The new crash is 50%-50%, like before.
So the probability that the last passanger find your seat free stays between 0% and 50%. As airplane capacity increase, more crashes and the probability stays closer 50%.
For that new problem, my Montecarlo simulations applies (After I've discovered a analytic solution and finally a general formula)
Thanks. It is good to know my original answer is right.
Jul 05, 2008
you guys are using selective reasoning to produce the answer as 50%
with 2 people, the probability is 50%. 3 people it falls to 40% (not 50% as someone has falsely 'proved'), at 4 people it continues to fall to 31.25%.
It doesnt remain at 50%. Each displaced person has a chance to either A)sit in the 100th seat or B) not sit in crazy guys seat. chances favour A at which point another person faces the same fate. one must also consider situations in which one displaced person will sit in
there are more variables involved than those you are recognising.many of you have oversimplified the problem, which is why you keep getting 50%.
with 2 people, the probability is 50%. 3 people it falls to 40% (not 50% as someone has falsely 'proved'), at 4 people it continues to fall to 31.25%.
It doesnt remain at 50%. Each displaced person has a chance to either A)sit in the 100th seat or B) not sit in crazy guys seat. chances favour A at which point another person faces the same fate. one must also consider situations in which one displaced person will sit in
there are more variables involved than those you are recognising.many of you have oversimplified the problem, which is why you keep getting 50%.
"Each displaced person has a chance to either A)sit in the 100th seat or B) not sit in crazy guys seat. chances favour A at which point another person faces the same fate."
You do understand that the chance for A and B are not equal (until you get down to only two seats).
You do understand that the chance for A and B are not equal (until you get down to only two seats).
The correct answer is 49.5%.
Answer of 50% only true if crazy passenger is guarenteed NOT to sit in seat 100. If he never chooses 100 then you can conclude as Dedrik did above:
"Another way to think of it; there are really only two events that we care about, A: someone sitting in seat 1 (guaranteeing the last guy gets his own seat), B: someone sitting in seat 100(guaranteeing he doesn't). All other seats don't matter. Since events A and B have identical probabilities of happening each time someone chooses a seat at random. The last person will have a 50/50 chance of getting his last seat."
But this ignores the possibility of crazy guy sitting in seat 100 in the first place. Take the example of 3 passengers again. Crazy guy wont sit in seat 1, so he chooses either seat 2 or 3. If he sits in 3, the last passenger has already lost his seat. In fact this will happen half the time. The other half the time, crazy sits in seat 2. The second passenger then could sit in 1or 3. So the last passenger only gets his seat 1/2 of 1/2 of the time or 25% (.5*.5=.25).
Now going back to the case of 100 passengers. Remember Dedrik's theory still holds true if crazy picks any seat other than seat 100 (and seat 1 of course). Each passenger who sees their seat occupied has a an equal chance of choosing seat 1 or 100 and resolving the 100th passenger's fate. So simply apply the same math for 100 passengers: Last passenger gets his seat 1/2 the time when crazy does NOT sit in seat 100, or
1/2 * 98/99
or .5 * .98... = .4949...
or 49.5%
Which by the way, is confirmed by pbuchsbaum, who wrote:
"I run my program again, using a more recent random number generator (Mersenne Twister from 2002).
I've got a much more accurate. result. I've got a 49.5% chance for the 100o. passenger in a airplane with 100 seats meets your own seat free. (100,000 simulations)"
So stated, of the times crazy guy chooses seats 2 thru 99 and avoids seat 100, the 100th passenger gets his seat half the time. 98/99 * 1/2 = 49.5%
One other note. I'm assuming this number approaches 50% as number of passengers approaches infinity, but I'll leave that for someone else to show.
Answer of 50% only true if crazy passenger is guarenteed NOT to sit in seat 100. If he never chooses 100 then you can conclude as Dedrik did above:
"Another way to think of it; there are really only two events that we care about, A: someone sitting in seat 1 (guaranteeing the last guy gets his own seat), B: someone sitting in seat 100(guaranteeing he doesn't). All other seats don't matter. Since events A and B have identical probabilities of happening each time someone chooses a seat at random. The last person will have a 50/50 chance of getting his last seat."
But this ignores the possibility of crazy guy sitting in seat 100 in the first place. Take the example of 3 passengers again. Crazy guy wont sit in seat 1, so he chooses either seat 2 or 3. If he sits in 3, the last passenger has already lost his seat. In fact this will happen half the time. The other half the time, crazy sits in seat 2. The second passenger then could sit in 1or 3. So the last passenger only gets his seat 1/2 of 1/2 of the time or 25% (.5*.5=.25).
Now going back to the case of 100 passengers. Remember Dedrik's theory still holds true if crazy picks any seat other than seat 100 (and seat 1 of course). Each passenger who sees their seat occupied has a an equal chance of choosing seat 1 or 100 and resolving the 100th passenger's fate. So simply apply the same math for 100 passengers: Last passenger gets his seat 1/2 the time when crazy does NOT sit in seat 100, or
1/2 * 98/99
or .5 * .98... = .4949...
or 49.5%
Which by the way, is confirmed by pbuchsbaum, who wrote:
"I run my program again, using a more recent random number generator (Mersenne Twister from 2002).
I've got a much more accurate. result. I've got a 49.5% chance for the 100o. passenger in a airplane with 100 seats meets your own seat free. (100,000 simulations)"
So stated, of the times crazy guy chooses seats 2 thru 99 and avoids seat 100, the 100th passenger gets his seat half the time. 98/99 * 1/2 = 49.5%
One other note. I'm assuming this number approaches 50% as number of passengers approaches infinity, but I'll leave that for someone else to show.
One more thought.
The formula for finding this answer for any number of passengers and seats n, seams to be:
1/2 * n-2/n-1
which holds true for the most extreme case of two passengers and two seats.
1/2 * 2-2/2-1
or 1/2 * 0/1 = 0
because if there are only two seats, crazy guy will always sit in seat 2 and therefore the last passenger NEVER gets his assigned seat.
The formula for finding this answer for any number of passengers and seats n, seams to be:
1/2 * n-2/n-1
which holds true for the most extreme case of two passengers and two seats.
1/2 * 2-2/2-1
or 1/2 * 0/1 = 0
because if there are only two seats, crazy guy will always sit in seat 2 and therefore the last passenger NEVER gets his assigned seat.
Some clarifications:
I should have writen the formula with parenthesise(sp).
1/2 * (n-2)/(n-1) = probability of last passenger getting his assigned seat.
n = number passengers and seats
There are 99 possible seat choices for crazy guy (2 thru 100) and 98 of those leave the 100th passenger with the 50-50 shot of getting his seat (2 thru 99). The last passenger looses his seat immediately in the 1 out of 99 chance crazy guy picks seat 100. So for 100 passengers and seats:.
1/2 * (n-2)/(n-1)
1/2 * (100-2)/(100-1)
1/2 * 98/99
.5 * .9898...= .4949...= 49.5%
Also examples of 4 passegers were cited above. The correct solution in that case would be:
1/2 * (n-2)/(n-1)
1/2 * (4-2)/(4-1)
1/2 * 2/3 = 1/3 chance of 4th(last) passenger getting his assigned seat
I should have writen the formula with parenthesise(sp).
1/2 * (n-2)/(n-1) = probability of last passenger getting his assigned seat.
n = number passengers and seats
There are 99 possible seat choices for crazy guy (2 thru 100) and 98 of those leave the 100th passenger with the 50-50 shot of getting his seat (2 thru 99). The last passenger looses his seat immediately in the 1 out of 99 chance crazy guy picks seat 100. So for 100 passengers and seats:.
1/2 * (n-2)/(n-1)
1/2 * (100-2)/(100-1)
1/2 * 98/99
.5 * .9898...= .4949...= 49.5%
Also examples of 4 passegers were cited above. The correct solution in that case would be:
1/2 * (n-2)/(n-1)
1/2 * (4-2)/(4-1)
1/2 * 2/3 = 1/3 chance of 4th(last) passenger getting his assigned seat
The answer is definitely 50%.
The crazy passenger will either choose seat 1 (allowing everyone else, including the 100th passenger, to get their proper seats), or some higher-numbered seat, seat k. The next k-2 passengers will get their proper seats, but passenger k will have to choose a random seat. Again, passenger k will either sit in seat 1, allowing any remaining passengers to board the proper seats, or in a higher-numbered seat, which we'll call seat j, and all the passengers through passenger j will get their proper seats, until passenger j is forced to take a random seat. And so on.
This will continue until either seat 1 is filled (ending the randomness and giving passenger 100 the correct seat) or seat 100 is filled (forcing passenger 100 to sit in seat 1). Since every randomly-seated passenger is just as likely to choose seat 1 as to choose seat 100, there is a 50% chance that seat 1 will get occupied before seat 100.
I don't see where the above commenter gets an answer of 40% for 3 seats. The crazy passenger is equally likely to do any of the following:
a) sit in seat 1. Passenger 2 will get seat 2, and passenger 3 will get seat 3. (100% chance of passenger 3 getting seat 3)
b) sit in seat 3. Passenger 2 will get seat 2, but passenger 3 will have to take seat 1. (0% chance of passenger 3 getting seat 3)
b) sit in seat 2. Passenger 2 will be forced to randomly choose seat 1 or seat 3, and passenger 3 will have to take the remaining seat. (50% chance of passenger 3 getting seat 3)
Since all three events are equally likely, we average the probabilities to get an overall 50% chance of passenger 3 getting seat 3. The same applies for any number of seats.
The crazy passenger will either choose seat 1 (allowing everyone else, including the 100th passenger, to get their proper seats), or some higher-numbered seat, seat k. The next k-2 passengers will get their proper seats, but passenger k will have to choose a random seat. Again, passenger k will either sit in seat 1, allowing any remaining passengers to board the proper seats, or in a higher-numbered seat, which we'll call seat j, and all the passengers through passenger j will get their proper seats, until passenger j is forced to take a random seat. And so on.
This will continue until either seat 1 is filled (ending the randomness and giving passenger 100 the correct seat) or seat 100 is filled (forcing passenger 100 to sit in seat 1). Since every randomly-seated passenger is just as likely to choose seat 1 as to choose seat 100, there is a 50% chance that seat 1 will get occupied before seat 100.
I don't see where the above commenter gets an answer of 40% for 3 seats. The crazy passenger is equally likely to do any of the following:
a) sit in seat 1. Passenger 2 will get seat 2, and passenger 3 will get seat 3. (100% chance of passenger 3 getting seat 3)
b) sit in seat 3. Passenger 2 will get seat 2, but passenger 3 will have to take seat 1. (0% chance of passenger 3 getting seat 3)
b) sit in seat 2. Passenger 2 will be forced to randomly choose seat 1 or seat 3, and passenger 3 will have to take the remaining seat. (50% chance of passenger 3 getting seat 3)
Since all three events are equally likely, we average the probabilities to get an overall 50% chance of passenger 3 getting seat 3. The same applies for any number of seats.
Aha. Now I see where SOME of the confusion lies. I assumed that the crazy guy has a 1% chance of choosing any seat (including his original seat 1). If we instead assume that the crazy guy never sits in seat 1, but has a 1 in 99 chance of choosing any of the other seats, then the answer is 49/99 (98/99 chance that the crazy guy doesn't choose seat 100, multiplied by the 1/2 answer derived above). That's close to the 49.5% derived from the Monte Carlo simulation. So the answer depends on whether "crazy" means "randomly chooses a seat from 1 through 100" or "randomly chooses a seat from 2 through 100". o.o
Nice puzzle. I got a couple minutes into setting up the problem when I got the same insight Dedrik states: the outcome is determined only when someone sits in either seat 1 or seat 100, therefore the probability must be 50% since the probability of either of these events occurring is the same.
Jun 24, 2009
Ahh.. took me sometime to understand why its 50%. Heres a program written in java which verifies the claim. Here it is, if you want to verify it.
http://cs.unm.edu/~ravi/PlaneSeating.zip
http://cs.unm.edu/~ravi/PlaneSeating.zip
For those who don't believe it's 50%, you can use induction to verify it is 50%.
If we're additionally given the assumption the crazy guy can't sit in his own seat, then the probability becomes (n-2) / (n-1) * 1/2. In the case of n = 100, this is 98/99 * 1/2 = 49/99 = 49.4949494949%
If we're additionally given the assumption the crazy guy can't sit in his own seat, then the probability becomes (n-2) / (n-1) * 1/2. In the case of n = 100, this is 98/99 * 1/2 = 49/99 = 49.4949494949%
Sep 25, 2010
50 percent is wrong.Crazy has only a 1/100 chance of getting into the right seat, they dont based on odds.With every passenger that gets on the 100th passengers odds go down.The odds are only 50 percent up until the 51st passenger is seated. If crazy is in the 51st passenger seat then by the 74 passenger there are 25 people in the wrong seat. By the time passenger 100 gets to a seat 25 are in the wrong seat and 74 are in the right seat , at best there is roughly a 1 in 4 chance that the 100th passenger could be in the right seat.If crazy displaces any passenger 1 thru 50 it means they in turn will displace more passengers and the odds get worse When crazy takes the first seat the chances of them taking passenger100 seats is 99 to 1 against So the odds of the 100th passenger getting into the right seat can not be 50 percent because there is only one seat left that means that last fiftyfifty chance is passenger 98 because thats the last chance for crazy to be in the right seat or not.
May 20, 2011
I agree that the logic if flawed. I solved the problem on my blog. Basically, you need to compute the probability that the last guy won't get the seat. I also did a montecarlo simulation for the number of seats varying from 3 to 50. You can find the solution here http://tiny.cc/wl186
@ranabasheer: Nice rigorous approach on your blog. Also, completely unnecessary and wrong.
The problem with your solution is that you solved a different problem.
The crazy guy simply ignores his ticket--he doesn't deliberately choose a wrong seat. The crazy guy is not guaranteed to take the wrong seat; he can also take his own seat. Your solution is based on a different scenario where he can't take his own seat.
The problem with your solution is that you solved a different problem.
The crazy guy simply ignores his ticket--he doesn't deliberately choose a wrong seat. The crazy guy is not guaranteed to take the wrong seat; he can also take his own seat. Your solution is based on a different scenario where he can't take his own seat.
Easy way to understand:
1. 1/100 chance the crazy guy sits at his seat.
2. 1/100 chance the crazy guy sits at seat 100
3. 98/100 chance the crazy guy sits else where. Then, the chance of someone sit at seat 1 (the passenger 100 will have his seat) and at seat 100 (the passenger 100 will not have his seat) are equivalent.
=> chance = 1/100 + 98/100*1/2=1/2
1. 1/100 chance the crazy guy sits at his seat.
2. 1/100 chance the crazy guy sits at seat 100
3. 98/100 chance the crazy guy sits else where. Then, the chance of someone sit at seat 1 (the passenger 100 will have his seat) and at seat 100 (the passenger 100 will not have his seat) are equivalent.
=> chance = 1/100 + 98/100*1/2=1/2
Is everyone not going about this a long way?
Here is a much simpler solution;
All that we really care about is the probability of the 100th person finding their seat empty. This means that we can change how we look at the problem...
Imagine that the passengers instead make the crazy guy move from their seat. He then randomly chooses another seat.
This will keep happening until the crazy guy either sits in his own seat, or sits in the 100th seat. Both of these events share equal probability.
Therefore our answer is 0.5 (50%)
Here is a much simpler solution;
All that we really care about is the probability of the 100th person finding their seat empty. This means that we can change how we look at the problem...
Imagine that the passengers instead make the crazy guy move from their seat. He then randomly chooses another seat.
This will keep happening until the crazy guy either sits in his own seat, or sits in the 100th seat. Both of these events share equal probability.
Therefore our answer is 0.5 (50%)
Answer: The conditional probability as per the given conditions is 1/2=0.5, i.e., the puzzle has only two options in the end after all the iterations between the first(#1 here) and the penultimate seat(#99 here):-
Anyone one of them for sure sat in either the last seat(#100 here), in which case we lose, or the first seat(#1 here), in which case we win.
However, if the first crazy guy cannot sit in his own seat (ignores his seat), then for a plane of 'n' seats, the probability that the last guy will sit in his seat = (n-1)/2n
Anyone one of them for sure sat in either the last seat(#100 here), in which case we lose, or the first seat(#1 here), in which case we win.
However, if the first crazy guy cannot sit in his own seat (ignores his seat), then for a plane of 'n' seats, the probability that the last guy will sit in his seat = (n-1)/2n
......(n-2)/2(n-1)
To post a comment, please create an account and sign in.
Follow Braingle!