Let's see if you anons are smart. It is actually a nice puzzle:
A flight is taking off soon, and there are 100 assigned seats, and the passengers enter in order of their seat #.
Passenger X loses their ticket and sits in a random seat.
What's the probability that the 100th person will be seated at their assigned seat?
Note: a passenger will always sit in their assigned seat unless it is taken. If their seat is taken, they will sit in a random seat.
Passenger X sits in a random seat. There's a chance that the 100th person won't have their seat.
Another issue is passenger X takes passenger's 60th seat, and passenger 60 sits on the 100th spot.
98 will will find their seats correctly, the seat the lost ticket person chose is one of two left. Either he is in the right seat or the wrong seat making the 100th person 50% likely to be in the right seat.
Here's my solution :
This problem consists in finding the number of sorted cyclic permutations not involving the last passenger, and the number of total possible sorted cyclic permutations of a set of 100 integers.
If passenger 1 takes passenger 20's seat, passenger 20 can't take any of the seats below 20 except passenger 1's seat. If he does, it closes the cycle, and leaves the other passengers undisturbed, because passengers 2... up to 19 can seat in their own seats, which are available when they arrive, and same for passengers above 21. If passenger 20 takes passenger 25's seat, then it's the same problem, with the start of the cycle being 1->20->25, until the cycle is closed (when one guy takes number 1 seat). So the cyclic permutations are sorted.
A sorted cyclic permutation is something written as (1,3,8,24) and means that passenger 1 takes passenger 3's seat, passenger 3 takes passenger 8's seat, etc (1->3->8->24->1)
There are 2^(n-1) sorted cyclic permutations of a set of n integers.
So the probability is 2^98/2^99 = 1/2
Ya man, nicely done.
Another way to look at it is this:
Let's say person #5 loses their ticket and sits in a spot that is not seat 5 or seat 100.
Because they enter in order of their assigned seats, person #100 will never sit in seats 1-4 or 6 to 99, because that passenger would take up that spot.
Therefore, passenger 100 will either sit in their assigned seat OR the Xth seat.
1 / 2 = 50%
Dude, the chances two things of chances n% and m% will both happen are (m%)(n%). Its (1%)(2%)..., which is 100! with each term divided by 100. Putting it togethher, his chance of being in that seat is (100!)/(100^100).
Actually, the answer is 100%
>the passengers enter in order of their seat #.
>Passenger X loses their ticket and sits in a random seat.
How does passenger X know when to enter the plane if they're entering based on ticket number? Not knowing their number they would wait until the end and then enter last, as the 100th passenger, and sit in the only assigned seat not taken which would be their own (wherever it was exactly).
Try doing it with smaller seats (4)
Possible combinations (1st person loses seat):
4/8 = 50%
Don't it for N # of seat
Seats for any passenger and you'll always come up with 50%
I get where your coming from, and this was something I had to wrap around as well.
The passengers who know their seating will always try and find their own seat, therefore their probabilities are dynamic and dependent on a random choice of their predecessors.
The passengers are the ones choosing the door, but 99 out of 100 come in knowing what door to open, but some come in to find out that someone else has already opened the door and taken their car.
These are invalid. For example, if #1 takes 3rd seat, then #2 will take his own seat. So 3,1,2,4 is impossible.
If I use sorted cycles, here are the combinations I get (1st person loses seat) :
As said before, the last guy will always sit in his own seat, or in the #1 seat.
It still makes 50%
Account for all of them.
So far it starts with a 1 in 100 probability that everyone will get their seat, since if the last person to board loses their ticket, then they are guaranteed to get their seat.
THEN you have to account for the additional probability that, should another person try to "randomly" sit that they would get their OWN seat. Seat holder 99 would have a 1:2 chance of his own. Seat holder 98 would have 1:3 and so on.
Once those are calculated and properly combined you would have the final probability that, seat holder "X," losing their ticket and randomly seated, that all people would get their seat, should seat holder "X" be any seat number.
Yeah but when does passenger X enter the plane? If he loses his ticket he doesn't know when to enter. If he loses his ticket after entering the plane he just needs to sit at the lowest available seat.
Indeed. If X=51, then the first 50 passengers get in their own seats whatever X does. So it's like solving the same problem with only 50 possible seats. It doesn't change the outcome (as long as X isn't 100).
That's not how the puzzle is defined, but ya that would be the most logical solution if these passengers were smart.
If their seat is taken, they find a random seat. So for X they're just so confused and just sit where they want (which is random)
Person #1 chooses their seat first. They can sit wherever. Person 2 will sit next, so if seat 2 is open they will only sit there, otherwise they will sit randomly.... Good on for 3,4,5,...etc
Those combinations are valid
That doesn't answer my question though. When does passenger X enter the plane? On the turn he would have if he had his ticket? Or randomly? Because then there are actually two random variables, when the passenger enters the plane and what ticket he had.
Sorry. Passenger x enters in the Xth position (when they are supposed to).
So passenger 6 is the 6th person to enter regardless if they lose their ticket or not.
Best just to take x=1 and assume they are the first on the plane. You come up with the same answer anyways
Not only do you have one person losing their seat, X, it causes a random uproar of other people randomly choosing seats. Seems like place 100 is a strategic seat, since seat 1 seems different from seat 100. I assume people cant take a seat once it goes down. Is this over one flight or infinite?
>98 will will find their seats correctly
Not necessarily. If X occupies the next passenger's seat, the next passenger must also occupie another random seat, which unless he occupies X's seat will trigger another person to occupy another random seat and so on.
I did 100*100 cases, that nicely fit in a 100x100 matrix.
Row index i is the position of the lost passenger in the line that enters the plane. If he enters the plane first, i = 1. If he enters the plane last, i = 100.
The column index j is the actual seat number of the lost passenger.
For i = 1, the passenger finds all the seats free and has a 1 in 100 chance to find his seat.
For i = 2, if his seat number j = 1, the passenger will find the first seat empty and the second one full, he will then know with absolute certainty that his actual seat is the first one. So the probability that he finds his seat is 1, for i,j = 2,1.
For all the following j, the probability he finds his seat is 1 in 99.
For the following rows, the same pattern applies.
Probability 1 for i < j, 1/(100 - i) for i ≥ j.
We can also realize that the sum of the i ≥ j part of a row is equal to 1 (100*1/100, 99*1/99, etc.)
So the sum of all the column gives the 1 to 100 vector, which sum gives 100*99/2.
Since the seat number and the order in the line are independent for the lost passenger, the probability of a single case (one matrix coefficient) is 1/10000.
By summing all the coeffs and dividing by 10000 we then get:
99/200 = 49.5%