There is 100 seats in a room
Thread Rating:
March 18th, 2018 at 8:43:31 PM
permalink
There is 100 seats and 100 persons in a room. Each person is assigned to a seat, ie person #1 to seat #1, etc. Everyone will try to sit in their own seat if they can, otherwise they will pick a random seat.
If the 1st person instead of sitting in his own seat, picks a random seat (his own included), what is the chance that the last person will sit in his own seat?
PS: given that it is a 1 star question, if forced to make a guess I will say either 0.5 or 0.99
If the 1st person instead of sitting in his own seat, picks a random seat (his own included), what is the chance that the last person will sit in his own seat?
PS: given that it is a 1 star question, if forced to make a guess I will say either 0.5 or 0.99
March 18th, 2018 at 9:29:44 PM
permalink
My off-the-cuff answer, bolstered by your hint about it being 1-star (presumably 'easy'...), is centered on the realization that you're actually looking at the odds that a specific chair (say, @) remains empty for the entire duration, barring the last person, which now actually makes this something like a 4th grade math problem?
Not actually sure of the correct way to represent this mathematically, but the logic runs as follows:
#1 has a 99/100 chance of leaving @ vacant.
#2 has a 98/99 chance of leaving @ vacant.
#3 has a 97/98 chance of leaving @ vacant.
etc.
The *99*/100 and the 98/*99* will cancel each other out all the way down, leaving you with 1/100, thus a 1% chance that our final individual will sit in their own seat. ...On the other hand, I also feel like I've fallen for a trap here (specifically tied to the factor that people prefer their own seats), but oh well.
Not actually sure of the correct way to represent this mathematically, but the logic runs as follows:
#1 has a 99/100 chance of leaving @ vacant.
#2 has a 98/99 chance of leaving @ vacant.
#3 has a 97/98 chance of leaving @ vacant.
etc.
The *99*/100 and the 98/*99* will cancel each other out all the way down, leaving you with 1/100, thus a 1% chance that our final individual will sit in their own seat. ...On the other hand, I also feel like I've fallen for a trap here (specifically tied to the factor that people prefer their own seats), but oh well.
March 18th, 2018 at 9:31:57 PM
permalink
If I understand this correctly, everyone picks a random seat. If that’s the case, then the answer is 1/100 or 1%.
March 18th, 2018 at 9:35:36 PM
permalink
People will sit in their own seat if available, otherwise it's random.
Which is what's giving me pause; if #1 sits in s99, then everybody sits in order, until #99, whereupon he has a 50% chance of sitting in s1 or s100...
March 18th, 2018 at 9:44:33 PM
permalink
re RS,
no, they pick their own seat if it is not taken.
no, they pick their own seat if it is not taken.
March 19th, 2018 at 12:15:49 AM
permalink
Deleted — OP is confusing. May respond later if I can figure it out.
March 19th, 2018 at 6:12:13 AM
permalink
This is one of my favorite problems but I ask it in the form of a 100-seat airplane.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 19th, 2018 at 6:15:06 AM
permalink
Quote: RSDeleted — OP is confusing. May respond later if I can figure it out.
Here is how I state it:
There is a plane with 100 seats. 100 passengers each have an assigned seat. The first passenger to enter the plane picks a random seat to sit in. The other 99 passengers, who enter one at a time, will try to sit in their assigned seat if it is empty. If it is taken, they pick a random seat among those still available.
What is the probability the last passenger to enter sits in his assigned seat?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 19th, 2018 at 7:59:11 AM
permalink
Quote: WizardHere is how I state it:
There is a plane with 100 seats. 100 passengers each have an assigned seat. The first passenger to enter the plane picks a random seat to sit in. The other 99 passengers, who enter one at a time, will try to sit in their assigned seat if it is empty. If it is taken, they pick a random seat among those still available.
What is the probability the last passenger to enter sits in his assigned seat?
I'm gonna go with 1% off the top of my head, without putting too much thought in to it.
Playing it correctly means you've already won.
March 19th, 2018 at 9:41:33 AM
permalink
Here are my thoughts, minus a calculated final answer:
For clarification number the passengers 1-100 based on the order they enter the plane. Number the seats 1-100 based on the passenger that each was originally assigned to.
There is a 1% chance that passenger 1 randomly picks seat 1 that he was assigned. Everything works fine, and passenger 100 gets his assigned seat.
There is a 1% chance that passenger 1 randomly picks seat 100, and passenger 100 will NOT get his assigned seat.
If passenger 1 picks seat 99 (1% chance), then all goes well until passenger 99 must randomly pick between the available seats 1 and 100, which means a 50% chance that passenger 100 gets his own seat.
It progressively gets more complicated. If passenger 1 picks seat 98 (again 1% chance), all goes well until passenger 98 makes a random selection between seats 1, 99, and 100. If he chooses 1, all is fine; if he chooses 100, there is failure; if he chooses 99, then passenger 99 makes a random selection between the remaining two seats. I believe this gives (1-(1/3)*(1+0+.5))=0.5 probability that neither of them sits in seat 100.
I think this leads to a summation of terms, each including a 1% chance of passenger 1 choosing seat number n, combined with a product of probabilities that passengers n through 99 sequentially do not randomly choose seat 100 if it is still available when they board.
I further think (1) that I don't know how to draw that summation equation on this forum, and (2) I am too lazy to calculate the total.
I'll take a wild guess that 98 of the 100 terms wind up with a (.01*0.5) probability with the other two being (.01*1) and (.01*0) for a grand total of 50% chance that passenger 100 gets his own seat.
There is a 1% chance that passenger 1 randomly picks seat 1 that he was assigned. Everything works fine, and passenger 100 gets his assigned seat.
There is a 1% chance that passenger 1 randomly picks seat 100, and passenger 100 will NOT get his assigned seat.
If passenger 1 picks seat 99 (1% chance), then all goes well until passenger 99 must randomly pick between the available seats 1 and 100, which means a 50% chance that passenger 100 gets his own seat.
It progressively gets more complicated. If passenger 1 picks seat 98 (again 1% chance), all goes well until passenger 98 makes a random selection between seats 1, 99, and 100. If he chooses 1, all is fine; if he chooses 100, there is failure; if he chooses 99, then passenger 99 makes a random selection between the remaining two seats. I believe this gives (1-(1/3)*(1+0+.5))=0.5 probability that neither of them sits in seat 100.
I think this leads to a summation of terms, each including a 1% chance of passenger 1 choosing seat number n, combined with a product of probabilities that passengers n through 99 sequentially do not randomly choose seat 100 if it is still available when they board.
I further think (1) that I don't know how to draw that summation equation on this forum, and (2) I am too lazy to calculate the total.
I'll take a wild guess that 98 of the 100 terms wind up with a (.01*0.5) probability with the other two being (.01*1) and (.01*0) for a grand total of 50% chance that passenger 100 gets his own seat.
March 19th, 2018 at 10:00:19 AM
permalink
Quote: MidwestAPThe probability that the seat assigned to the last person (Passenger 100) is available when he/she enters the plane (using Wiz's scenario) is 1 minus the sum of the probabilities that Passenger 100's seat is selected on any previous round (a round being a new passenger entering the plane):
Passenger 1 --> 1/100 = .001
Passenger 2 --> (1- prob of Passenger 1 already sat down in Passenger 100 seat) x (1/99) = .001
Passenger 3 -- > [1-(prob of Passenger 1 + prob Passenger 2) already sat down in Passenger 100 seat] x (1/98) = .001
Passenger 4 --> [1-(prob of Passenger 1 + prob Passenger 2+prob of Passenger 3) already sat down in Passenger 100 seat] x (1/97) = .001
.
.
.
Passenger 99 --> 1-(prob of Passenger 1 +... +prob of Passenger 98) already sat down in Passenger 100 seat] x (1/2) = .001
The sum of the probabilities that the seat is previously selected = 0.99
Therefore the chance that it is available = 1 - 0.99 = 1%
But this can't be correct, as there has to be a greater than 1% chance since if the first person entering the plane sits down in their assigned seat, then by rule, the last person will as well.
Therefore, I think we need to add in the 1% chance that Passenger 1 sits down in the correct seat, therefore the answer to the question is 2%.
But, I may be way off here.
March 19th, 2018 at 10:12:20 AM
permalink
Comments on MidwestAP's guess:
I think you are treating every passenger as if they are making a random selection. They only do that if their own seat is already occupied.Quote: MidwestAP...Passenger 2 --> (1- prob of Passenger 1 already sat down in Passenger 100 seat) x (1/99) = .001
March 19th, 2018 at 10:23:43 AM
permalink
Quote: DocComments on MidwestAP's guess:
I think you are treating every passenger as if they are making a random selection. They only do that if their own seat is already occupied.
Yes, you are correct, let me rethink this.
March 19th, 2018 at 11:05:39 AM
permalink
There's a limit to how long ago we can edit a post now? Anyhow--
Now that it's morning, I'm pretty sure that 1% is a trap answer, and the key component to that is that people favor their own seats. Now I'm leaning towards 50% based on the possible combinations when person 1 is assigned s98 or s99...
March 19th, 2018 at 11:17:26 AM
permalink
Quote: RomesI'm gonna go with 1% off the top of my head, without putting too much thought in to it.
It must be more than that. There is a 1% chance passenger 1 picks the correct seat and then everybody else will also get their correct seat. However, he could also pick the wrong seat but nobody ever picks seat 100 so passenger 100 gets his seat that way. For example, if passenger 1 picks seat 2, and passenger 2 picks seat 1, then the other 98 passengers will get the correct seat.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 19th, 2018 at 1:40:22 PM
permalink
I know some people prefer answers via proofs rather than brute force simulation, but I couldn't help myself.
I didn't spend a lot of time stepping through everything to make sure it's correct, so anyone is welcome to take a look at the code --
https://pastebin.com/uLUqdzHM
50% - 10 million simulations of the scenario came out to a probability of 0.5000151 which agrees with Doc’s hypothesis
I didn't spend a lot of time stepping through everything to make sure it's correct, so anyone is welcome to take a look at the code --
https://pastebin.com/uLUqdzHM
Last edited by: gamerfreak on Mar 19, 2018
March 19th, 2018 at 2:55:07 PM
permalink
Quote: DocHere are my thoughts, minus a calculated final answer:
For clarification number the passengers 1-100 based on the order they enter the plane. Number the seats 1-100 based on the passenger that each was originally assigned to.
There is a 1% chance that passenger 1 randomly picks seat 1 that he was assigned. Everything works fine, and passenger 100 gets his assigned seat.
There is a 1% chance that passenger 1 randomly picks seat 100, and passenger 100 will NOT get his assigned seat.
If passenger 1 picks seat 99 (1% chance), then all goes well until passenger 99 must randomly pick between the available seats 1 and 100, which means a 50% chance that passenger 100 gets his own seat.
It progressively gets more complicated. If passenger 1 picks seat 98 (again 1% chance), all goes well until passenger 98 makes a random selection between seats 1, 99, and 100. If he chooses 1, all is fine; if he chooses 100, there is failure; if he chooses 99, then passenger 99 makes a random selection between the remaining two seats. I believe this gives (1-(1/3)*(1+0+.5))=0.5 probability that neither of them sits in seat 100.
I think this leads to a summation of terms, each including a 1% chance of passenger 1 choosing seat number n, combined with a product of probabilities that passengers n through 99 sequentially do not randomly choose seat 100 if it is still available when they board.
I further think (1) that I don't know how to draw that summation equation on this forum, and (2) I am too lazy to calculate the total.
I'll take a wild guess that 98 of the 100 terms wind up with a (.01*0.5) probability with the other two being (.01*1) and (.01*0) for a grand total of 50% chance that passenger 100 gets his own seat.
I agree with Doc.
This happens on Southwest all the time.
March 19th, 2018 at 3:17:38 PM
permalink
A tricky question until you realize something:
For the parade of persons who randomly select a seat (including the first person), the question is: Will some person choose to sit in the first person's assigned seat before they choose to sit in the last person's assigned seat? Once a person does randomly select the assigned seat of the first person, then all the remaining open seats will be filled by the people who were assigned to them. This is because the act of randomly picking the assigned seat of the first person ends the need for any subsequent person to randomly select a seat.
On the other hand, if a person who is randomly selecting a seat picks the last person's assigned seat then that resolves the immediate question -the last person will not get their seat.
SO, the chance that the last person will sit in his own seat must be 0.5 -the probability that people picking at random will pick the first person's assigned seat before they pick the last person's assigned seat.
For the parade of persons who randomly select a seat (including the first person), the question is: Will some person choose to sit in the first person's assigned seat before they choose to sit in the last person's assigned seat? Once a person does randomly select the assigned seat of the first person, then all the remaining open seats will be filled by the people who were assigned to them. This is because the act of randomly picking the assigned seat of the first person ends the need for any subsequent person to randomly select a seat.
On the other hand, if a person who is randomly selecting a seat picks the last person's assigned seat then that resolves the immediate question -the last person will not get their seat.
SO, the chance that the last person will sit in his own seat must be 0.5 -the probability that people picking at random will pick the first person's assigned seat before they pick the last person's assigned seat.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
March 19th, 2018 at 4:02:43 PM
permalink
Although I didn't present the equation, calculate all of its terms, nor compute a final answer, I did make my "wild guess" as to the values of the terms and their sum. My guess is extremely close to gamefreak's gamerfreak's simulation result, so my confidence is growing. Too bad that I am too lazy to complete the intermediate steps.Quote: SOOPOOI agree with Doc.
Last edited by: Doc on Mar 19, 2018
March 19th, 2018 at 4:12:48 PM
permalink
Quote: gordonm888A tricky question until you realize something:
For the parade of persons who randomly select a seat (including the first person), the question is: Will some person choose to sit in the first person's assigned seat before they choose to sit in the last person's assigned seat? Once a person does randomly select the assigned seat of the first person, then all the remaining open seats will be filled by the people who were assigned to them. This is because the act of randomly picking the assigned seat of the first person ends the need for any subsequent person to randomly select a seat.
On the other hand, if a person who is randomly selecting a seat picks the last person's assigned seat then that resolves the immediate question -the last person will not get their seat.
SO, the chance that the last person will sit in his own seat must be 0.5 -the probability that people picking at random will pick the first person's assigned seat before they pick the last person's assigned seat.
I think this is the best description. The fact a seat is eliminated every turn doesn’t change the maffs.
One seat is “good”, one is “bad”, and every other seat acts like a “push”. Like if you have a die, if you keep re-rolling it, you have a 50% chance of rolling a 1 before a 6 (and rolling 2-5 results in a push for a re-roll). Same thing happens here.
March 19th, 2018 at 6:49:33 PM
permalink
Quote:This is one of my favorite problems but I ask it in the form of a 100-seat airplane.
LOL.
Someone translated it into a question in Chinese and I translated it back. Skipped the airplane part.
Last edited by: andysif on Mar 19, 2018
March 19th, 2018 at 6:54:26 PM
permalink
Doc,
I was thinking along the same line.
It's hard to do it starting from 100, but if you do it starting from 3, and when you are up to 4 you use the result from 3 and build it up that way, it's more manageable.
I was thinking along the same line.
It's hard to do it starting from 100, but if you do it starting from 3, and when you are up to 4 you use the result from 3 and build it up that way, it's more manageable.
March 19th, 2018 at 7:10:51 PM
permalink
This is how I handle it
Assume there is 2 person instead of 100, then the chance of the last person siting in his own seat is 0.5
if there is 3 person, then p = 1/3*100%(1st guy picked his own seat) + 1/3*0% (1st guy picked the last seat and 1/3*0.5(pick any other seat, which reverts to the situation when there is 2 person involved, ie p(2))
when there is 4 person, p = 1/4*100% + 1*4*0% + 2/4 * (p(3))
And it always turn out to be 0.5 from 2 person all the way to 100 person
if there is 3 person, then p = 1/3*100%(1st guy picked his own seat) + 1/3*0% (1st guy picked the last seat and 1/3*0.5(pick any other seat, which reverts to the situation when there is 2 person involved, ie p(2))
when there is 4 person, p = 1/4*100% + 1*4*0% + 2/4 * (p(3))
And it always turn out to be 0.5 from 2 person all the way to 100 person
January 12th, 2019 at 8:27:51 AM
permalink
I used to have this problem on my web site. It brings back happy memories.
A number of complicated or incorrect answers have been submitted but
gordonm888 has the best one. Here I state it in as few words as possible
to help with understanding.
A sits in the wrong seat, displacing B
B sits in the wrong seat displacing C
C sits in the wrong seat displacing D
This continues until a displaced person sits in A's seat,
displacing no one and everyone else sits in his own seat, or
a displaced person sits in the last person's seat,
displacing the last person.
Either event is equally likely to happen, so
The probability of the last person getting his own seat is 1/2.
A number of complicated or incorrect answers have been submitted but
gordonm888 has the best one. Here I state it in as few words as possible
to help with understanding.
A sits in the wrong seat, displacing B
B sits in the wrong seat displacing C
C sits in the wrong seat displacing D
This continues until a displaced person sits in A's seat,
displacing no one and everyone else sits in his own seat, or
a displaced person sits in the last person's seat,
displacing the last person.
Either event is equally likely to happen, so
The probability of the last person getting his own seat is 1/2.
January 12th, 2019 at 2:59:37 PM
permalink
Tend to agree with above idea
If the first person sits at seat 1 then everyone will sit at their correct place : P=1.
If the first person sits at seat 100 then there's no way :P=0.
Suppose the first person sits at place 99 then it's 50/50 whether when 99 gets to choose he sits in 1 or 100; P = 1/2
Sippose the first person sits at place 98 then when 98 gets to choose it's 1/3 he sits at 1, 1/3 he sits at 100 and 1/3 he sits at 99. Thus P = 0*1/3 + 1 *1/3 + 1/2*1/3 = 1/2.
Similarly all the probabilities are 1/2.
As has been said another way of looking at it is as each person arrives whose seat has been taken (or first time for person #1) the situarion is resolved at that moment if they pick seat 1 or seat 100, otherwise the situation is resolved later on with the same chances. Thus it is 50/50.
If the first person sits at seat 1 then everyone will sit at their correct place : P=1.
If the first person sits at seat 100 then there's no way :P=0.
Suppose the first person sits at place 99 then it's 50/50 whether when 99 gets to choose he sits in 1 or 100; P = 1/2
Sippose the first person sits at place 98 then when 98 gets to choose it's 1/3 he sits at 1, 1/3 he sits at 100 and 1/3 he sits at 99. Thus P = 0*1/3 + 1 *1/3 + 1/2*1/3 = 1/2.
Similarly all the probabilities are 1/2.
As has been said another way of looking at it is as each person arrives whose seat has been taken (or first time for person #1) the situarion is resolved at that moment if they pick seat 1 or seat 100, otherwise the situation is resolved later on with the same chances. Thus it is 50/50.
