45 of 100: Plane Passenger Shuffle

I'm trying to figure out a good way to explain this.

I started by recognizing that with 2 people, the probability is $\frac{1}{2}$ that the last person gets his seat.

When there are 3 people, we can think about the possibilities for what the first person does: He could sit in his own seat with probability $\frac{1}{3}$ He could sit in seat 2, leaving the scenario as if there were only 2 people. This has a probability of $\frac{1}{3}$ . Multiply this by the probability of the second person leaving the correct seat: $\frac{1}{2}*\frac{1}{3}=\frac{1}{6}$ He could sit in seat 3, guaranteeing failure.

This gives a total probability of $\frac{1}{3}+\frac{1}{6}=\frac{1}{2}$

It seems that the answer is always $\frac{1}{2}$ , though 2 steps is not enough to prove it.

What it boils down to is that for $n$ people I can use all the probabilities before it to calculate the probability.

Let's assume that the probability for any number of people less than n is always $\frac{1}{2}$ .

So, with n people this becomes:

$\frac{1}{n}+\frac{1}{n}*\frac{1}{2}*(n-2)$ #The $n-2$ is because there are $n-2$ sizes smaller than $n$ that we need to worry about.

$\frac{1}{n}+\frac{1}{2n}*(n-2)$

$\frac{1}{n}+\frac{1}{2}-\frac{1}{n}$

$\frac{1}{2}$

This proof by induction shows that it is always a 50% chance that the last person gets his own seat.

Let $p(n)$ be the probability that $n$ th persons seat is taken ( $n>1$ ).

$p(2)$ : Probability that 1st person took 2nd persons seat = $\frac{1}{100}$ .

$p(3)$ : Probability that 1st person took it + Probability that 1st person took 2nd persons seat and 2nd person took it = $\frac{1}{100}+\frac{1}{100}\times \frac{1}{99}=\frac{1}{99}$ .

$\dots$

We claim that $p(k)$ = $\frac{1}{100-(k-2)}$ .

Probability that ( $k+1$ )th persons seat is taken will be $p(k)+p(k) \frac{1}{100-(k-1)}=\frac{1}{100-(k-1)}$ .

Thus by induction $p(k)$ = $\frac{1}{100-(k-2)}$ and $p(100)=\frac{1}{2}$ .

There is a nice way to look at this; when the first passenger wants to sit there are 2 possibilities; whether his seat is taken or not & the same happens to the hundredth passenger so the possibility of sitting in his own seat is $\frac{1}{2}$

Two observations (which each take a little thinking in their own right, and someone should probably confirm):

1. The last passenger must either get his own seat, or the first passenger's (originally-assigned) seat.

2. If a seating arrangement can occur by the rules of this puzzle, then so can the seating arrangement you obtain by swapping the first and last passengers.

With those two observations, there is a bijection between (a) the seating arrangements in which the last passenger gets his own seat, and (b) those in which he does not.

Consider a slightly different wording of the problem: when someone enters the plane, and their seat is already taken, they ask the person in their seat to move to a new, random seat. This has the same implications for the last person to come in whether their seat is taken or not, as whenever a person comes in and their seat is taken, the same thing happens - a new random seat gets occupied.

Now, it is clear to see that the first person to come in is the only one who will be taking up new positions - everyone else just asks them to move, and sits in their original seat. What are the possibilities when the last passenger enters the plane? - His seat is occupied by the 1st passenger (or any passenger in the original problem) - The 1st passenger is seating in their own seat (or any passenger in the original problem) Hence, there are only 2 possible outcomes.

Assuming a uniform distribution is used whenever the 1st person has to move (as we are never actually told that the distribution is uniform - so in reality the answer should be "Not enough information"), this means that whenever the 1st person moves, the probability of them sitting in the last person's seat is the same as the probability of them sitting in the seat that they should be sat in. If they do not sit in one of these 2 seats, then they will simply move again later before the last passenger arrives in the plane, and the same situation will occur. If they sit in either their own or the last person's seat, then no more moving occurs until the last person arrives (and this will eventually happen), and we arrive at the final situation.

Hence, as the probability of them sitting in their own seat is the same as them sitting in the last person's seat, and at some point they must end up in one of them, the probability of the last person finding their seat unoccupied is $\frac{1}{2}$ .

The first passenger can sit

• on his own seat, in which case all following passengers (including the last) take their own seat

• on the last seat, in which case the last passenger ends up with the wrong seat

• on any other seat, in which the problem is postponed.

Any passenger who finds his seat taken has similar choices; instead of sitting in his own seat, he would sit on the one seat that remained unoccupied earlier.

The first two choices have equal probability, giving an overall probability $P = \boxed{1/2}$ . Postponing does not change the odds, because eventually a decision will be made with $P = 1/2$ .

There are 100 seats and so the first passenger takes a random seat. The solving procedure is as follows. Every person sits is their seat if it is right. One person must have another person in their seat at one point, so we set him/her aside. Do this procedure until up to the 99th passenger. Now there are two people left, the 100th passenger, and the passenger who was supposed to seat in the seat the the first passenger took. There are two seats left as well, the first and the hundredth seat. The probability is therefore 1/2.

There is a simple way of dealing with the problem.
Suppose the seat earmarked for 1st passenger is no.1 and he occupies seat meant for passenger no.N. Then the problem begins only when Nth passenger enters in, and the problem gets translated as if the Nth passenger is the 1st passenger with total passengers (100 - N) +1,instead of 100 and seat no.1 earmarked for him but he has lost his seat number and has to choose any seat at random out of seat no 1and the remaining (100 - N) seats and so on.
Since N can be any number and the problem gets translated and re-stated as if beginning with Nth passenger as the first passenger who does not know his seat number and applies to the reduced numbers of passengers and seats only, the answer for 100 would be same as the answer for 2. If there were just two passengers, the probability of second passenger getting correct seat would be 1/2 and same applies when passengers are 100. So, the answer is 1/2.

The first person has $\frac 1{100}$ chance of taking the correct seat by accident and leaving all remaining seats in order.

So there is $\frac{99}{100}$ chance that the second person is walking into a plane in which the first took a wrong seat.

If this is the case, the second person has a $\frac1{99}$ chance of accidentally taking the one seat that the first one was assigned to.

So the probability that after the second person is seated, all seats are in order is

$\frac 1{100}+\frac{99}{100}\times\frac{1}{99}=\frac{99+1}{100\times99}=\frac1{99}$

And the probability that there is one seat wrong is $\frac{98}{99}$

The situation would therefore be exactly the same as if there were only $99$ people boarding a plane with $99$ seats and the first person had taken a seat arbitrarily.

The same calculation could be done over and over again until the last person is boarding the plane and all is as if there were just $2$ people total and the first has taken a seat arbitrarily.

The probability of the second one taking the correct seat is then $\frac12$ .

So the overall probability of the last person getting the correct seat is $\boxed{\frac12}$

We can generalize. Say there are n seats on the plane, and n passengers. It is easier to focus on the probability that the m th passenger will lose his assigned seat. This probability is equal to the sum of the probabilities that his seat has already been taken by the m - 1 passengers who boarded before him. He therefore has the same chance of losing his assigned seat as that of the passenger immediately before him, with the addition of the chance that the passenger immediately before him lost her seat and sat in his. If the probability that the passenger immediately before him lost her assigned seat is p , then the probability that the m th passenger loses his seat is p + $\frac{p}{n - m + 2}$ . This is because the passenger immediately before him has n - m + 2 seats left to choose from.

Now, the probability that the second passenger to board loses his assigned seat is always $\frac{1}{n}$ , because the first passenger to board chose randomly from n seats. This, combined with the information above, is enough to show that the probability that the third passenger loses her assigned seat is $\frac{1}{n - 1}$ , and, in general, that the probability that the m th passenger loses his assigned seat is $\frac{1}{n - m + 2}$ . Therefore, the probability that the last, or n th, passenger to board will lose his assigned seat is $\frac{1}{n - n + 2}$ , or $\frac{1}{2}$ .

I like this one. Sounds difficult, but is very simple if you spot the trick. Well, maybe not so simple to explain...

I'll re-number the seats so that the first passenger's allocated seat is 1, the 2nd one's is 2, ...; generally the n-th passenger's allocated seat is n. (Of course, the 1st one doesn't know where to sit so he has to choose at random.)

Initially, both seats, 1 and 100 are unoccupied. Whenever a passenger 2-99 has their seat available, it doesn't change the situation seats 1 and 100. It only matters whenever a passenger makes a random choice.

Whenever a passenger makes a random choice, he can take a seat 1 or 100 with the same probability, or take a seat with another number k; in that case the passengers up to k (if any) will sit on their allocated seats and k-th passenger will make a random choice. Once a passenger up to 99 chooses either 1 or 100 the outcome (whether the 100th passenger will get his own seat) is decided.

That is a special example of a funny coin, the probability for heads (1) and tails (100) is the same, but there is the third possible outcome, the coin landing on its side, the probability of which varies (in some random way) with each toss (and is guaranteed to become zero after finite number of tosses). If the coin lands on its side you toss again (and again until that doesn't happen).

Each passenger up to 99 that makes a random choice, is equivalent of such a coin. If that passenger is 99, the probability of the coin landing on its side is 0 (heads 0.5, tails 0.5 - ordinary fair coin). For passenger number 91 the probability of heads would be 0.1, tails 0.1 and landing on its side 0.8. But the exact probabilities don't matter, as long as the probability for heads and tails are equal.

Imagine the repeated coin toss as described (until it lands on heads or tails rather than on its side) and you want to know the probability of heads. If you calculate the probability step by step, you always add the same amount to both probabilities, heads or tails. So at the end they are going to be the same, so half each (as one of these two will definitely happen eventually).

There is a quite simple way to solve this question; in this solution, I'll address the process of finding the seat as a "game". The game is a "success" if the last passenger is able to find his/her seat, and a "failure" if he/she is not.

Let's look at the first passenger. Since he/she picks a seat at random, there is an equal probability that he/she will pick his/her own seat (which leads to direct success) and that he/she will pick the last passenger's seat (which leads to direct failure). Thus, the probability of success, when compared to that of failure, is $\frac{1}{2}$ .

In other cases, the first passenger will select a random seat. Say this is the seat of the $n$ th passenger. Then, all passengers from the second to $(n-1)$ th are able to find their own seat.

When the $n$ th passenger enters, he/she will find his/her seat taken, and do one of the following: (a.) randomly select the first passenger's seat, which leads to a direct success (b.) randomly select the last passenger's seat, which leads to a direct failure (c.) randomly select another seat; say this is the $k$ th passenger's seat

Note that (a.) and (b.) have the same probability.

Again, all passengers until the $k$ th are able to find their own seat.

When the $k$ th passenger enters, the (a.), (b.), and (c.) step is repeated. Note that the probability of success and failure compared to each other remains as $\frac{1}{2}$ throughout.

Finally, when the last passenger enters, and if the game has not ended, he/she is left with two choices: (a.) and (b.)

Therefore, the answer is $\frac{1}{2}$ .

This is how I figured it out at first.

Start with two persons (A & B) and 2 seats (1 & 2). Assume that A is assigned to seat 1 and B to seat 2. Then there will be a chance of $\frac{1}{2}$ that A takes seat 1. In that case B, the last passenger, takes seat 2, their assigned seat. If A takes seat 2 then B will not end up in their assigned seat. So the probability the last passenger ends up in their assigned seat is $\frac{1}{2}$ .

Now three persons (A, B & C) and three seats (1, 2 & 3). Assume that A is assigned to seat 1, B to seat 2 and C to seat 3. Then there will be a chance of $\frac{1}{3}$ that A takes the right seat and then B & C will automatically have their right seats as well. So in this situation the probability the last passenger ends up in their assigned seat is $\frac{1}{3}$ . But what if A takes seat 2? Then B can't take their assigned seat. So B can take seat 1 and C will end up in their assigned seat. The chance this will happen is $\frac{1}{3}\times\frac{1}{2}=\frac{1}{6}$ . B also can take seat 3 but then C will not end up in their assigned seat. Neither will this happen if A takes seat 3. So the probability the last passenger ends up in their assigned seat is $\frac{1}{3}+\frac{1}{6}=\frac{1}{2}$ .

Just in case: four persons (A, B, C & D) and four seats (1, 2, 3 & 4). Again A is assigned to seat 1, B to seat 2 and so on. Then there will be a chance of $\frac{1}{4}$ that A takes the right seat and then B, C & D will automatically have their right seats as well. So in this situation the probability the last passenger ends up in their assigned seat is $\frac{1}{4}$ . A also can take seat 2. In that case B has a problem. If B takes seat 1 then C will end up in seat 3 and D in seat 4 and everything's fine. The chance is $\frac{1}{4}\times\frac{1}{3}=\frac{1}{12}$ . If A takes seat 2 and B takes seat 3 then C has a problem. If C takes seat 1 then D will end up in seat 4 and that's fine again. The chance is $\frac{1}{4}\times\frac{1}{3}\times\frac{1}{2}=\frac{1}{24}$ . Finally A also can take seat 3. Again C has a problem then (because B has their assigned seat). With a chance of $\frac{1}{2}$ C takes seat 1 and D will end up fine. So the chance of this happening is $\frac{1}{4}\times\frac{1}{2}=\frac{1}{8}$ . The probability the last passenger ends up in their assigned seat is $\frac{1}{4}+\frac{1}{12}+\frac{1}{24}+\frac{1}{8}=\frac{1}{2}$ .

No matter how many persons there will be, the probability the last passenger will end up in their assigned seat will always be $\frac{1}{2}$ .

Every person taking a seat has three options:

• guarantee failure by sitting in the last passenger's seat
• guarantee success by sitting in a success seat
• deferring the decision to another passenger

Since the two cases that guarantee success and failure have equal probability, they balance out. In the defer case, we recursively know that the next passenger's success and failure options will balance also, and so on. There will result an equal number of opportunities for the last passenger's seat to be ruined, as there are opportunities for his seat to be guaranteed. 50% .

The first passenger has a $\frac{1}{n}$ (where n is number of passengers) probability of sitting in the correct seat, in which case the final passenger will also sit in the correct seat.

The first passenger also has a $\frac{1}{n}$ chance of sitting in the final passengers seat, in which case the final passenger can't sit in the correct seat.

The only other option is to sit in neither of those two seats - a probability of $\frac{n-2}{n}$ . If this happens, the final passenger has a $\frac{1}{2}$ chance of sitting in the right seat in each of these cases (proved through induction), so the probability is $\frac{n-2}{2n}$ .

Thus total probability is $\frac{1}{n}$ + $\frac{n-2}{2n}$ which simplifies to $\frac{1}{2}$

We will show that when the 100th person enters the plane only either seat 1 or seat 100 isvacant Only 2 situations are possible following a series of displacements 1) Passenger 1goes to K,K goes to M,M goes to T and so on back to 1with the rest of the passengers in their designated seats 2)Passenger 1goes to K,K goes to M, M goes to T and so on until somebody goes to seat 100 leaving the rest of the passengers in their designated seats and seat 1vacant when the 100th passenger boards the plane Either situation contains an equal number of possible displacements so the probability of seat 1 being vacant equals the probability of seat 100 being vacant giving the answer = 0.5

If we start with a plane that holds only two passengers, we can see that the chances of the last passenger ending up in the correct seat are 1/2, as the two possible outcome are:

1) Passenger 1 picks his correct seat, leaving Passenger 2 to take his seat, OR 2) Passenger 1 takes Passenger 2's seat, leaving Passenger 2 to take Passenger 1's seat

If we were to write out all the possible combinations for a plane of three passengers, we would actually see that there are four possible outcomes, two of which are favorable.

(If the correct order of passengers is 1, 2, 3 the ways they could end up sitting are:) (1, 2, 3) (2, 1, 3) (3, 1, 2) (3, 2, 1) We have to keep in mind the fact that if a passenger's rightful seat is available they will take it, as we determine possible outcomes.

As you can see, two of these four situations, or 1/2, are favorable. We can use this method for four, five, etc., passengers. For four passengers, the odds are 4/8 ( I'll let you write them out ), For five passengers the odds are 8/16. It's a cool pattern that presumably leads us to the conclusion that no matter how many passengers there are, the odds will always simplify to be 1/2

Let P(n) be the probability that the last passenger take the correct seat, for n > 2.

For n = 2, the first passenger either take the correct seat or the seat of last passenger: P(2) = $\frac{1}{2}$ * 1 + $\frac{1}{2}$ * 0 = $\frac{1}{2}$

For n = 3, the first passenger may take the correct seat, the seat of last passenger, or the remaining seat, which reduces the question to the case of n = 2:

P(3) = $\frac{1}{3}$ * 1 + $\frac{1}{3}$ * 0 + $\frac{1}{3}$ * P(2)

Similarly, P(4) = $\frac{1}{4}$ * 1 + $\frac{1}{4}$ * 0 + $\frac{2}{4}$ * P(3)

In general, P(n) = $\frac{1}{n}$ * 1 + $\frac{1}{n}$ * 0 + $\frac{n - 2}{n}$ * P(n - 1)

Solve the equation for smaller values suggests P(n) \equiv $\frac{1}{2}$ , which can be proven by mathematical induction.

Monte Carlo Simulation - http://www.codeskulptor.org/#user43 6worWKljj9 7.py

Let "seat k" and "passenger k", k=1,2,3, ..., refer to the original boarding pass assignments with the passengers in line order. Say in general there are n seats/passengers (the n=100 given is not important).

Then under the revised seating scheme:

seat 2 can only get passengers 1 or 2 (for if passenger 1 does not get the seat, then passenger 2 does);

seat 3 can only get passengers 1, 2, or 3 (for if passengers 1 or 2 do not get the seat, then passenger 3 does);

etc.;

seat n-1 can only get passengers 1, 2, ..., or n-1 (for if passengers 1 to n-2 do not get the seat, then passenger n-1 does).

In summary, we see that seats 2 to n-1 can not get passenger n. In other words, passenger n only has seats 1 or n available. It remains to show that these two options are equally likely to occur. For this, there is a nice symmetry. Suppose passenger n is in seat 1 and passenger k is in seat n. If passenger k had randomly chosen seat 1 instead, then passenger n is forced to seat n, and it is easy to see that the seatings of no other passengers would be affected. And vice versa. QED

Note: on Air Canada there are n seats and n+N passengers, for N unbounded, which makes the problem trickier.

Since someone might have to be displaced by the boarding pass loss, all (even the lost bp who could actually choose his assigned seat) have a 50/50 chance of choosing the correct seat.

As the last passenger there are only two seats that you could possibly sit in: your own seat or the seat that the first passenger was supposed to sit in. Every other seat would have been occupied by its assigned passenger if it had been empty when that passenger boarded.

When the first passenger boards the probability that he sits in either of these two seats is the same. Likewise for every other passenger that has to pick a random seat. Therefore at the end each of these two seats is equally likely to be unoccupied and there is a probability of 1/2 that the final passenger ends up in their assigned seat.

First, let's number each seat according to the position in line of the passenger assigned to that seat.

Now we can make a very helpful observation:

When the $k^{th}$ passenger enters the plane, there can be at most one empty seat numbered $< k$ .

Proof: Clearly true for $k=1$ . Assume true for passenger $k-1$ . When passenger $k-1$ enters, either their seat is empty or it is filled. If empty, passenger $k-1$ must sit there and preserves the claim for passenger $k$ . If not, passenger $k-1$ may sit in the empty seat numbered $< k-1$ if there is one, or must sit in a seat numbered $> k-1$ . Either way, the claim is preserved for passenger $k$ .

So now consider these two possibilities for passenger $k < 100$ :

1. There are no empty seats numbered $< k$ when they enter. Since there are $k-1$ seated passengers occupying the first $k-1$ seats, all seats numbered $\geq k$ must be empty. Passenger $k$ and all following passengers will occupy their correct seats. These passengers have no choice at all.

2. There is an empty seat numbered $< k$ . Passenger $k$ has $100-k$ possible choices:

   • Sit in that empty seat;
   • Sit in seat 100;
   • Sit in some seat in the range $[k, 100)$ .

The first choice guarantees that passenger $100$ will end up in seat $100$ . The second choice guarantees that they will not. Every other choice does nothing to alter the likeliness of either outcome.

Since the passenger in case 1 is forced, they do not branch the event space. In case 2, assuming they randomly choose among available seats, they guarantee success or failure with equal probability, or they make a choice that will lead to some later passenger facing case #2.

In all scenarios, there is some "deciding" passenger - the one who either sits in seat 100 or takes the seat that causes all seats $\leq k$ to be filled. And that passenger has an equal likelihood of doing one of those two things. Therefore, the final passenger will be in their proper seat with probability $\boxed{\frac{1}{2}}$ .

The answer is $\frac{1}{2}$ .

Let A and B be the seats of the first and last passengers respectively. First notice that if a passenger ever sits in A, then the passengers who have entered the plane so far will be sitting in a permutation of their assigned seats. This implies that passengers who subsequently board the plane sit in their correct seats. Thus the last open seat is either A or B and the last passenger to board the plane sits in either A or B.

Therefore the passengers sitting in A and B at the end of this process must be the last passenger and another passenger P. When the passenger P boarded the plane, he or she was either the first passenger or had been assigned an occupied seat. In either case, the probability that P sat in A is the same as the probability P sat in B since A and B must both be empty at that time. If P sat in A then the last passenger ended up sitting in B and the resulting configuration of passengers sitting in the $100$ seats is the same as if P had sat in B except for the fact that the passengers in A and B are swapped. Therefore these two configurations occur with the same probability and exactly one of them has the last passenger in her seat B. This implies that the final configurations of passengers can be paired such that the two configurations in any pair occur with the same probability and exactly one has the last passenger in her seat. This implies that the probability that the last passenger is in her seat is $1/2$ .

Let's examine the situation for every incoming passenger. For clarity's sake, we'll call the first passenger's designated seat seat#1, second passenger's seat seat#2 and so on. (Also, the "they" used in this solution is singular "they".)

The first person doesn't know his seat. The probability of his taking the seat#1 and seat#100 is equal. If he chooses one of these options, the fate of the last passenger is decided. It's because the first person choosing seat#1 means everyone will sit in their designated seat including the last person. If the first person chooses seat#100, the last person won't get to sit in their seat. So, for these two options, the last person has equal probabilities of getting his designated seat. Otherwise, we move to the next step.

Any passenger that comes after the first person has to deal with two conditions- whether their seat is taken or not. If not taken, they occupy the designated seat. If taken, it's because the first person didn't occupy their or the last person's seat (seat#1 and seat#100). So, they will also get to choose between seat#1 and seat#100. If they take the seat#1, everyone following them will get to sit in their designated seats including the last person. If they occupy the seat#100, then the last person won't get his seat. But, if they don't take seat#1 or seat#100, the dilemma just get passed on.

The crucial part is that the choice of the seat#1 and seat#100 comes simultaneously and choosing a single one of them seals the fate of the last person. Therefore, the probability of the last person getting their seat is one-half.

I will try to explain why the two events of whether last person will get his seat or not at the end are equally likely. For this let's number the seats and the corresponding passenger from 1 to 100 and without loss of generality we can assume that passengers come in order from 1 to 100 to occupy the seat. Now 1st person can occupy any seat which can be that of his or some other passenger. Suppose he occupies $i$ th seat, then as the process continues , everyone will get his seat till the $i$ th person. Now again this $i$ th person has choice of either 1st seat or any seat numbered > $i$ .Hence we can see that if someone in the middle of this process takes 1st seat ,then last person will get his seat and if no one takes this seat, then last person will get the 1st seat. Also we need to observe that at any point of time the probability of getting the 1st seat and last seat occupied is same. Hence it is equally likely that the seat remaining at the end can be 1st seat or 100th(last) seat. Hence the probability is 1/2.

এইটা হবার এবং না হবার সম্ভাবনা সমান। একজন ব্যাক্তি এসে তার আসন না পেলে সে অন্য আসনে বসবে। সুতরাং, ১০০ তম ব্যাক্তির জন্য বরাদ্দকৃত আসনটা হয় তার নিজের, না হয় অন্য কারো। সুতরাং, সম্ভাবনাটা ১/২।

The last man in the line have 2 possibility either his sit is taken or not.

So every person in the line except the first one is 0.5