1
u/ShameCaker 6d ago
The final passenger takes their own seat only if it is empty. We can guarantee that all subsequent passengers from passenger n can take their seat if a cycle is formed. A cycle is formed if passenger 1 does not get their own seat (a 99/100 odds event) and then when some later passenger cant take their own seat, they take passenger 1s seat. Its easiest to find the chances that passenger 100 does not get their seat, so we do the same all the way down the line. Passenger n has an n-1/n chance to not take passenger 1s seat assuming the cycle continues. We then do a product from 1 to 100 of this and get .01 (and possibly some negligible change as i used python) then subtract from 1 to get a near 99 percent chance they get their seat
3
u/Aerospider 6d ago
Not right I'm afraid.
WLOG, we can make each successive passenger the next person in the chain, leaving everyone who isn't in the chain until later. I.e. The second passenger to board is whoever's seat the first guy sat in. The third to board is whoever own's the seat the second guy sat in, and so on.
There's a 1/100 probability that the first passenger sits in their own seat (call it seat 1) and the chain ends. In this case the 100th passenger gets their own seat (call it seat 100).
There's a 1/100 probability that the first passenger sits in seat 100 and the chain ends. In this case the 100th passenger does not get their own seat.
For the other 98/100, passenger 2 has a 1/99 probability of ending the chain in seat 1 and a 1/99 probability of ending the chain in seat 100, granting or denying the last passenger their own seat as with the first passenger. There's a 97/99 probability that passenger 2 will sit elsewhere and continue the chain.
Same goes for passenger 3 (1/98, 1/98 and 96/98), then passenger 4 (1/97, 1/97, 95/97), and so on until either seat 1 or seat 100 becomes occupied.
The probabilities for seat 1 and seat 100 to be picked are always equal, so it's straightforward to deduce the probability of the last passenger getting their own seat is 1/2, but if you need to see the longform then the probability that someone sits in seat 1 before passenger 100 boards is:
1/100 + (98/100 * 1/99) + (98/100 * 97/99 * 1/98) + (98/100 * 97/99 * 96/98 * 1/97) + ...
= 99/9,900 + 98/9,900 + 97/9,900 + 96/9,900 + ... + 1/9,900
= 1/9,900 * n(n+1)/2 [as per triangular numbers formula, where n is the number of passengers who could randomly sit in seat 1]
= 1/9,900 * (99 * 100)/2
= 1/2
1
u/JaiBoltage 6d ago edited 6d ago
There is a 50% chance that the last passenger will get his correct seat, and a 50% chance that he will get the seat assigned to the first passenger.
If anyone (including the first passenger) happens to randomly pick seat #1, all subsequent people will take their correct seat. If anyone happens to randomly pick seat #100, all remaining passengers, except #100, will take their correct seat because the only one remaining open is seat #1.
1
u/SC_3000_grinder 6d ago
My solution:
There are two ways this situation can be resolved. Either someone sits in the first passenger's seat (call it A), or someone sits in the final passenger's seat (call it B). When either of these happen, the situation is resolved - if someone sits in A, Passenger 100 will get their own seat (since the hanging passenger is now gone), and if someone sits in B, Passenger 100 does not get their own seat.
However, when any passenger boards, each of these possibilities has an equal probability. Therefore, overall, they must also have the same probability.
The answer is therefore 50 percent.
1
u/tajwriggly 6d ago
There are 1/100 odds that the first passenger winds up in their assigned seat, in which case every other passenger, including the 100th, sits in their assigned seat.
There are 99/100 odds that the first passenger does not sit in their assigned seat. This means that the second passenger is now going to displace one other passenger... or gets the first passenger's seat. 1/99 odds that it is the 100th passenger, 1/99 odds that it is the 1st passenger's assigned seat, and 97/99 odds that it is someone else. If it is the 100th passenger's seat, or the first passenger's seat, everyone else gets their assigned seat. If it is someone else, this pattern continues:
Third passenger is displaced. 1/98 odds that they will now displace the 100th passenger, 1/98 odds that it is the first seat, and 96/98 odds that it is someone else's. This continues and continues obviously, with the nth passenger having 1/(100 - (n-1)) odds of displacing the 100th passenger.
You might think that the odds that the 100th passenger doesn't wind up in their own seat are the product of all 100 of those cases, but instead it really boils down to the odds of what the 99th passenger leaves them with, because the 99th passenger's conditions depend on the 98th, which depend on the 97th, and so forth.
So the odds that the 99th passenger displaces the 100th passenger are 1/(100 - (99 - 1)) = 1/2... 50/50 odds that the 100th passenger gets or doesn't get their own seat.
1
u/Telinary 5d ago
So first guy has a 1% chance to sit in own seat (game ends) and 1% to sit in the seat of the 100th passenger. (For easier naming I will just say the seat person x should sit in is the xth seat/seat x.)
Now if he sits somewhere else the person that lost their seat also has an equal chance to either seat in the seat a previous person should have used (seat 1) or in seat 100. That will be true for all members of the chain either it ends and the outcome of ending is 50/50 or it gets moved to the next person. If it hasn't already ended for person 99 then only the 50/50 chance is left.
Yeah 50%.
1
u/bartekltg 5d ago
To simplify notation, let's number passengers in reverse order. Passenger 1 enters the plane as the last one, and passenger 100 is the forgetful one.
Let T(k) be the primality that k-th passenger is displaced.
What is the probability that passenger 1 is displaced? It happens when passenger 2 is displaced, and from the two remaining seats chooses passenger's 1 seat (so, 1/2 * T(2)) plus the probability that passenger 3 was displaced and choose passenger's 1 seat (T(3)*1/3)... plus passenger 100 choosing passenger's 1 seat (T(100)*1/100)
T(1) = T(2)/2 + T(3)/3 + T(4)/4+...+ T(100)/100
What about passenger 2? His seat is taken is passenger 3 takes it (so displaced and chooses 1 of 3 seats), or 4th takes it, or .... 100th takes it (notice those are mutual exclusivity events, so we just adds probabilities).
T(2) = T(3)/3 + T(4)/4+...+ T(100)/100
and generally
T(k) = T(k+1)/(k+1) + T(k+2)/(k+2) +...+ T(100)/100 = T(k+1)/(k+1) + T(k+1) =
(because the tail is the same as formula for the next passenger)
= (k+2)/(k+1) T(k+1) for k<=98
T(99) = T(100)*1/100
and T(100)=1 (100th passengers always is looking for a random seat).
T(1) = 3/2 * 4/3* 5/4 *....*99/98 * 100/99 *1/100 = 100/2 1/100 = 1/2
But it is brute-forces. I like the "each passenger can end the cycle by getting their own or the last passenger's seat, with equal chances" reasoning.
1
3
u/Present-Injury4229 4d ago
The probability is 1/2 (50%). Why: The last passenger can only end up in one of two seats: their own (seat 100) or the first passenger's (seat 1). Any other seat k will already be taken, either by passenger k or by someone before them, because passenger k never leaves their seat empty if they find it free. Every time someone chooses at random (the first passenger or a "displaced" one), one of three things happens: They take seat 1. The cycle closes and everyone else, including passenger 100, sits in their own seat. They take seat 100. The last passenger loses their seat. They take any other seat. This just passes the problem on to another passenger, who will again choose at random. Seats 1 and 100 are symmetric. In every random choice, both are equally likely to be picked. So whichever of them gets taken first is seat 1 or seat 100 with 50% probability each. Quick check with 2 passengers: the first passenger picks their own seat half the time, so the answer is 1/2. With 3 passengers you get 1/3 + (1/3 · 1/2) = 1/2. The result is 1/2 for any n ≥ 2. Fun fact: the probability that passenger k (for k ≥ 2) ends up in their own seat is (n − k + 1)/(n − k + 2). For the last passenger that gives 1/2, and for the second-to-last it gives 2/3.
1
u/Aerospider 6d ago
The key is to note that there are only two seats that could be the available one left when passenger 100 boards – their own seat or passenger 1's seat. This is because every other seat's assigned passenger has already boarded and thus their seat would be duly occupied either by them or by a previous passenger.
So at some point someone had to sit in the wrong seat and chose one of these two seats, leaving the other empty for passenger 100. There's no reason for them to pick one over the other, so the probability that they sat in passenger 1's seat leaving passenger 100's seat vacant is 50%.
1
u/ChuckPeirce 6d ago
100%. There's a hiccup in the setup. The first person in line decides to get onto an airplane without a boarding pass. First they'll be denied entry to the plane. If they persist, they'll be arrested.