One hundred people line up to board an airplane

[Gavran]

[P. Winkler] One hundred people line up to board an airplane. Each has a boarding pass with an assigned seat. However, the first person to board has lost his boarding pass and takes a random seat. After that, each person takes the assigned seat if it is unoccupied, and one of the unoccupied seats at random otherwise. What is the probability that the last person to board gets to sit in his assigned seat?

For the simplest case when there are only two passengers, the solution is P₂=1/2.
This is the case when the first passenger between two seats chooses their own seat.

For the case when there are three passengers, the solution is P₃=1/3+1/3P₂=1/3(1+1/2)=1/2.
This is the case when the first passenger between three seats chooses their own seat or when the first passenger between three seats chooses the second passenger seat.

For the case when there are four passengers, the solution is P₄=1/4+1/4P₃+1/4P₂=1/4(1+2/2)=1/2.
This is the case when the first passenger between four seats chooses their own seat or when the first passenger between four seats chooses the second passenger seat or when the first passenger between four seats chooses the third passenger seat.

For the case when there are five passengers, the solution is P₅=1/5+1/5P₄+1/5P₃+1/5P₂=1/5(1+3/2)=1/2.
This is the case when the first passenger between five seats chooses their own seat or when the first passenger between five seats chooses the second passenger seat or when the first passenger between five seats chooses the third passenger seat or when the first passenger between five seats chooses the fourth passenger seat.

Clearly, for the case when there are n passengers, the solution is P_n=1/n+1/nP_n-1+...+1/nP₃+1/nP₂=1/n(1+(n-2)/2)=1/2.

For one hundred passengers, the answer is 1/2.

 

[PeroK]

Challenge Post in thread 'Math Challenge - November 2019'

Dec 9, 2019

Thanks fresh_42, for reviewing my answer! I am not as strong on intuitive thinking as other people on this forum and will need to think a lot more to find a simpler approach that doesn't use Bayes' theorem. Since you mentioned that my previous answer was close, I make one more attempt at solving the problem and along the same lines as before. Smith will definitely have the choice of 50 seats if he is the 1st passenger to board, so I guess it should be assumed that Smith is NOT the last passenger to board, either because it is a trivial case and there is no choice to be made, or because...

• PeroK

• 

 

[JimWhoKnew]

[P. Winkler] One hundred people line up to board an airplane. Each has a boarding pass with an assigned seat. However, the first person to board has lost his boarding pass and takes a random seat. After that, each person takes the assigned seat if it is unoccupied, and one of the unoccupied seats at random otherwise. What is the probability that the last person to board gets to sit in his assigned seat?

For the simplest case when there are only two passengers, the solution is P₂=1/2.
This is the case when the first passenger between two seats chooses their own seat.

For the case when there are three passengers, the solution is P₃=1/3+1/3P₂=1/3(1+1/2)=1/2.
This is the case when the first passenger between three seats chooses their own seat or when the first passenger between three seats chooses the second passenger seat.

For the case when there are four passengers, the solution is P₄=1/4+1/4P₃+1/4P₂=1/4(1+2/2)=1/2.
This is the case when the first passenger between four seats chooses their own seat or when the first passenger between four seats chooses the second passenger seat or when the first passenger between four seats chooses the third passenger seat.

For the case when there are five passengers, the solution is P₅=1/5+1/5P₄+1/5P₃+1/5P₂=1/5(1+3/2)=1/2.
This is the case when the first passenger between five seats chooses their own seat or when the first passenger between five seats chooses the second passenger seat or when the first passenger between five seats chooses the third passenger seat or when the first passenger between five seats chooses the fourth passenger seat.

Clearly, for the case when there are n passengers, the solution is P_n=1/n+1/nP_n-1+...+1/nP₃+1/nP₂=1/n(1+(n-2)/2)=1/2.

For one hundred passengers, the answer is 1/2.

Considering small numbers is always a good strategy when you can't figure out the idea without it.

In this problem there is an easier approach:

Spoiler

The outcome is determined once seat #1 or seat #100 are occupied. Until then, they have equal probability to become occupied at every single "round". So the probability is a trivial 1/2.
[\SPOILER]

 

[PeroK]

Considering small numbers is always a good strategy when you can't figure out the idea without it.

In this problem there is an easier approach:

Spoiler

The outcome is determined once seat #1 or seat #100 are occupied. Until then, they have equal probability to become occupied at every single "round". So the probability is a trivial 1/2.
[\SPOILER]

That seems like a post-hoc solution to me. Once you know the answer, you can just say "it's trivial". The same approach to a problem where the answer is not 1/2 could easily go wrong. As it often does.

A claim that two things are equally likely needs to be backed up by some sort of calculation/analysis.

 

[Hornbein]

Hah! I flat out guessed 1/2.

 

[JimWhoKnew]

That seems like a post-hoc solution to me.

The approach I've described in 3 is how I solved this puzzle when I've first heard it about a decade ago. After that, I've checked that my solution works for small numbers, by calculations similar to OP's.

Once you know the answer, you can just say "it's trivial".

That's what I said. If you get the idea described in #3, the rest becomes trivial. Nowhere have I said that thinking of this idea is trivial. The explanation in #3 is certainly much shorter than the one provided by OP.

The same approach to a problem where the answer is not 1/2 could easily go wrong. As it often does.

I explicitly wrote "In this problem there is an easier approach". By "easier" I meant "shorter explanation" (and from my personal point of view also "easier to follow"), not necessarily "easy to think of".

I certainly didn't claim that the described approach is applicable in general to all conceivable puzzles.

A claim that two things are equally likely needs to be backed up by some sort of calculation/analysis.

When OP writes "... one of the unoccupied seats at random", it implies a uniform distribution of probability. Oddly, you didn't comment OP about it for using it in the provided solution.

When the $n^{th}~$ passenger comes up, $~1\le n\le 99~$, if both seats #1 and #100 are still vacant, the probability to sit in #1 (assuming uniform distribution) is $~1/(101-n)~$, and so is the probability to sit in #100 (or in any other specific vacant seat). Does this meet your "needs to be backed up by some sort of calculation/analysis" requirement? Do we really need this trivial calculation to deduce the equality (symmetry of the problem!) and hence the final answer?

 

[PeroK]

I certainly didn't claim that the described approach is applicable in general to all conceivable puzzles.

That's not what I meant. There are lots of examples (e.g. Monty Hall), where the intuitive "it must be 1/2" argument is wrong. It's difficult/impossible to distinguish between a correct "it must be 1/2" and an incorrect "it must be 1/2".

If you say "trivially, it must be 1/2" in this case, then it's difficult to argue with someone who says "trivially, it must be 1/2" in the Monty Hall problem.

When OP writes "... one of the unoccupied seats at random", it implies a uniform distribution of probability. Oddly, you didn't comment OP about it for using it in the provided solution.

I didn't look at the OP's solution.

When the $n^{th}~$ passenger comes up, $~1\le n\le 99~$, if both seats #1 and #100 are still vacant, the probability to sit in #1 (assuming uniform distribution) is $~1/(101-n)~$, and so is the probability to sit in #100 (or in any other specific vacant seat). Does this meet your "needs to be backed up by some sort of calculation/analysis" requirement? Do we really need this trivial calculation to deduce the equality (symmetry of the problem!) and hence the final answer?

The key point is that the process of passengers boarding the plane and taking their own seat or seats 1 or 100 does not break the symmetry. You needed something to justify that.

 

[Gavran]

Considering small numbers is always a good strategy when you can't figure out the idea without it.

I have found the problem from the initial post online and there is also a solution to the problem.

Look at the situation when the k’th passenger enters. Neither of the previous passengers showed any preference for the k’th seat vs. the seat of the first passenger. This in particular is true when k = n. But the n’th passenger can only occupy his seat or the first passenger’s seat. Therefore the probability is 1/2.

To me, this solution seems to be incomplete, making it difficult to understand. This is why I offer the solution in the initial post, which I believe is easy to understand.

 

[JimWhoKnew]

I have found the problem from the initial post online and there is also a solution to the problem.

Look at the situation when the k’th passenger enters. Neither of the previous passengers showed any preference for the k’th seat vs. the seat of the first passenger. This in particular is true when k = n. But the n’th passenger can only occupy his seat or the first passenger’s seat. Therefore the probability is 1/2.

To me, this solution seems to be incomplete, making it difficult to understand. This is why I offer the solution in the initial post, which I believe is easy to understand.

When I wrote "Considering small numbers is always a good strategy when you can't figure out the idea without it", I didn't mean it is a bad strategy in other cases.

It seems that the quoted solution from the initial post online is similar to mine. But I also find the description unconvincing and hard to understand. So I'll rewrite my approach in a more detailed way, hoping it is clearer (please let me know):

Spoiler

We number the seats according to the number of the passenger who was supposed to sit in them. The passenger who boards first was supposed to sit in #1, the passenger who boards n was supposed to sit in #n, etc. So we are looking for the probability that passenger 100 will sit in seat #100.

When the first passenger boards, there are three possibilities:
1. She happens to choose seat #1 (probability 1/100). In this case, all other passengers will sit where they were supposed to, and passenger 100 will sit in #100 ("positive outcome").
2. She happens to choose seat #100 (probability 1/100 too). In this case, passenger 100 will not sit in his assigned seat ("negative outcome").
3. She will sit somewhere else (seats #2-#99, probability 98/100 - but that's unimportant for our specific purpose). In this case, the determination of the final outcome (whether passenger 100 will get to sit in #100) is deferred to the following "rounds" (boarding of the following passengers).

It can be noted that the probabilities for positive and negative outcomes are equal so far (1/100 each).

When the n passenger boards, there are 2 possibilities:
1. The final outcome was already determined by the preceding passengers. That is: either seat #1 or/and seat #100 are already occupied. In this case, it doesn't matter where passenger n sits (of course, if seat #n is vacant, the passenger will sit there, by the conditions of the puzzle).
2. Seats #1 and seat #100 are still vacant. In this case there are 3 possibilities, as for the first passenger (above):
2.1. She happens to choose seat #1 (probability 1/(101-n) ) -> "positive outcome".
2.2. She happens to choose seat #100 (probability 1/(101-n) too) -> "negative outcome".
2.3. She will sit somewhere else (probability (99-n)/(101-n) - but that's again unimportant for our specific purpose). In that case, the determination of the final outcome is deferred again to the following "rounds".

It can be noted again that as long as the outcome is yet undetermined, the probabilities for determining positive or negative outcomes are equal at each round ( 1/(101-n) each in round/passenger n). Neither possibility is preferred over the other.

So by the preservation of this symmetry from round to round until determination, we get equal overall probabilities for both positive and negative outcomes (1/2 each).

This explanation is no longer shorter than OP's, but that's mostly due to the resolution of details. Yet, it involves less calculations.

Another way to look at the puzzle: when all passengers are finally seated, we get a permutation of (1,2,...,99,100). If 1 and 100 are in the same cycle (under the puzzle's conditions) - the outcome is negative. Otherwise it is positive. If passenger n (n<100) sits in #1, the cycle of 1 is closed without including 100. If passenger n sits in 100, 100 and 1 will be in the same cycle.

 

[Gavran]

It seems that the quoted solution from the initial post online is similar to mine. But I also find the description unconvincing and hard to understand. So I'll rewrite my approach in a more detailed way, hoping it is clearer (please let me know):

There are two kinds of passengers. The first one who can choose and the second one who cannot choose. The passengers who can choose will decide the final outcome, while others will not decide the final outcome.

Let us see the general case when there are n passengers.
The first passenger chooses the seat with the probability 1/n among n available seats. In the case that the first passenger chooses the first passenger seat or the last passenger seat, the process ends, and all passengers from two to n-1 will sit on their own seat, while the last passenger will sit on the first passenger seat or the last passenger seat, depending on the first passenger’s choice. If the first passenger chooses the i-th passenger seat where i≠1 and i≠n, all passengers from 2 to i-1 will sit on their own seat, and now the i-th passenger will choose the seat with the probability 1/(n-i+1) among n-i+1 available seats. In the case that the i-th passenger chooses the first passenger seat or the last passenger seat, the process ends, and all passengers from i+1 to n-1 will sit on their own seat, while the last passenger will sit on the first passenger seat or the last passenger seat depending on the i-th passenger’s choice. If the i-th passenger chooses the j-th passenger seat where j≠1 and j≠n …

We can say that the passenger who can choose will always choose the seat among available seats, including the first passenger seat and the last passenger seat, with the same probability (the first passenger will choose with probability of 1/n, the i-th passenger will choose with probability of 1/(n-i+1), the j-th passenger will choose with probability of 1/(n-j+1), …). Therefore, the overall probability that the first passenger seat will be chosen must be equal to the overall probability that the last passenger seat will be chosen. These two outcomes are only two possible outcomes because the first passenger seat or the last passenger seat must always be chosen by one of the first n-1 passengers, and because their probabilities are equal, the probability that the passenger n will sit on their own seat is 1/2.

I hope the above is what you are trying to say.

Your approach is excellent, but I am not sure about the next part of your explanation.

When the n passenger boards, there are 2 possibilities:
1. The final outcome was already determined by the preceding passengers. That is: either seat #1 or/and seat #100 are already occupied. In this case, it doesn't matter where passenger n sits (of course, if seat #n is vacant, the passenger will sit there, by the conditions of the puzzle).

In this scenario the n-th passenger can only sit on their own seat except in the case when the n-th passenger is the last passenger and the seat n is already taken.

 

[JimWhoKnew]

In this scenario the n-th passenger can only sit on their own seat except in the case when the n-th passenger is the last passenger and the seat n is already taken.

You are right. I didn't go into it, since the goal was to show the symmetry, and these details don't affect the result. In hindsight, I should have. (since I've mentioned the need to comply with the constraints, I wasn't really wrong, just unclear).

We can also note that passenger 100 either sits in seat #100 or #1.
In the "permutation view" (of $~S_{100}~$) we have one "long" cycle of length $~l~$, $~1\le l \le 100~$ (always containing 1), and $~100-l~$ cycles of length 1 (those who sit in their own seats).
Suppose passenger 1 sits in #43. Then passengers 2 to 42 will sit in their seats, and 43 will either sit in #1 (thus closing the "long cycle"), or will sit in a seat >43. So the long cycle always begins with 1, and its elements appear in an increasing order.
In this view, we are actually asking what is the probability that 100 will not be an element of the long cycle (if it is, it is necessarily the last ($~l^{th}~$) element, "leading back to" the opening 1).

Edit: made some changes to conform with conventions.

 

[Gavran]

(if it is, it is necessarily the last ($~l^{th}~$) element, "leading back to" the opening 1).

I suppose that by the l-th element in this scenario, you are referring to the 100th passenger who is taking seat #1. Any cycle that contains the passenger sitting in seat #100 must end with the 100th passenger sitting in seat #1.

 

[JimWhoKnew]

I suppose that by the l-th element in this scenario, you are referring to the 100th passenger who is taking seat #1. Any cycle that contains the passenger sitting in seat #100 must end with the 100th passenger sitting in seat #1.

Yes.
In the notation I'm using, for $~l>1~$ the long cycle is of the form $~(1,k_2,k_3,\dots,k_l)~$ , meaning: passenger 1 sits in seat $k_2$ , passenger $k_2$ sits in $k_3$ , ... , $k_{l-1}$ in $k_l$ , $k_l$ sits in 1.
As concluded in earlier posts: $~1<k_2<k_3<\dots <k_l \le 100~$. If $~k_l<100~$ then passenger 100 sits in #100, otherwise he sits in #1.

 

[Gavran]

In the notation I'm using, for $~l>1~$ the long cycle is of the form $~(1,k_2,k_3,\dots,k_l)~$ , meaning: passenger 1 sits in seat $k_2$ , passenger $k_2$ sits in $k_3$ , ... , $k_{l-1}$ in $k_l$ , $k_l$ sits in 1.
As concluded in earlier posts: $~1<k_2<k_3<\dots <k_l \le 100~$. If $~k_l<100~$ then passenger 100 sits in #100, otherwise he sits in #1.

Now we can use the above to calculate how many events with a positive outcome there are. For the general case when there are n passengers, we can define sets $A=\{1\}$ and $B=\{2,3,...,n-2,n-1\}$. Every set $D=A\cup C$ where $C\subseteq B$ defines one event with a positive outcome. Simply, the number of different events with the positive outcome is the cardinality of the power set of set $B$, which equals $2^{n-2}$.

 

[JimWhoKnew]

Now we can use the above to calculate how many events with a positive outcome there are. For the general case when there are n passengers, we can define sets $A=\{1\}$ and $B=\{2,3,...,n-2,n-1\}$. Every set $D=A\cup C$ where $C\subseteq B$ defines one event with a positive outcome. Simply, the number of different events with the positive outcome is the cardinality of the power set of set $B$, which equals $2^{n-2}$.

I suppose that by "event" you mean a permutation that complies with the constraints imposed by the problem.
The number of positive events for which the long cycle is of length $l$ is $$\binom {n-2}{l-1} \quad ,$$and is equal to the number of negative events for which the cycle is of length $~n+1-l~$ (or $~l+1~,~l\le99~$, by the binomial symmetry). For $~l=n~$ the binomial above should be evaluated as 0. So the overall number of positive events ($~2^{n-2}~$) is the same as the overall number of negative ones and the symmetry is maintained here too. But the different single events are not equi-probable, so we can't infer the 1/2 immediately from this counting.

 

[Gavran]

I suppose that by "event" you mean a permutation that complies with the constraints imposed by the problem.
The number of positive events for which the long cycle is of length $l$ is $$\binom {n-2}{l-1} \quad ,$$and is equal to the number of negative events for which the cycle is of length $~n+1-l~$ (or $~l+1~,~l\le99~$, by the binomial symmetry).

I agree with all that you said in post #15, but is it okay to use the term “permutation” here?
The expression $$ \binom{n-2}{l-1} $$ indicates that we speak about combinations here.

 

[JimWhoKnew]

I agree with all that you said in post #15, but is it okay to use the term “permutation” here?
The expression $$ \binom{n-2}{l-1} $$ indicates that we speak about combinations here.

The final sitting arrangement can be looked at as a transformation that re-orders the numbers $~1,2,...,n~$, which makes it an element of the Symmetric Group $~S_n~$. So I call it a permutation (am I wrong about it?). Out of the $~n!~$ possible permutations, only $~2^{n-1}~$ are allowed "events" (positive+negative), ie. comply with the constraints imposed by the problem (one "long cycle" of length $l$ containing 1 and $~l-1~$ additional numbers in an increasing order, and $~n-l~$ cycles of length 1).

 

[JimWhoKnew]

The final sitting arrangement can be looked at as a transformation that re-orders the numbers $~1,2,...,n~$, which makes it an element of the Symmetric Group $~S_n~$. So I call it a permutation (am I wrong about it?). Out of the $~n!~$ possible permutations, only $~2^{n-1}~$ are allowed "events" (positive+negative), ie. comply with the constraints imposed by the problem (one "long cycle" of length $l$ containing 1 and $~l-1~$ additional numbers in an increasing order, and $~n-l~$ cycles of length 1).

To be clearer, I consider the case $~n=3~$ as an example.
There are 2 positive events:
$(1,2,3)\quad\leftrightarrow\quad (1)(2)(3)$
$(2,1,3)\quad\leftrightarrow\quad (1,2)(3)$
(on the right I write the same permutation as on the left in cycles notation),
and 2 negative events:
$(3,2,1)\quad\leftrightarrow\quad (1,3)(2)$
$(2,3,1)\quad\leftrightarrow\quad (1,2,3)\quad .$
There are 2 additional permutations in $~S_3~$ which are not events (prohibited by the conditions of the problem):
$(1,3,2)\quad\leftrightarrow\quad (1)(2,3)\quad$
(1 is not in the long cycle, passenger 2 sits in #3 although seat #2 is vacant)
$(3,1,2)\quad\leftrightarrow\quad (1,3,2)\quad$
(the numbers in the long cycle are not in an increasing order, passenger 2 sits in #1 although seat #2 is vacant)

 

[Gavran]

The final sitting arrangement can be looked at as a transformation that re-orders the numbers $~1,2,...,n~$, which makes it an element of the Symmetric Group $~S_n~$. So I call it a permutation (am I wrong about it?). Out of the $~n!~$ possible permutations, only $~2^{n-1}~$ are allowed "events" (positive+negative), ie. comply with the constraints imposed by the problem (one "long cycle" of length $l$ containing 1 and $~l-1~$ additional numbers in an increasing order, and $~n-l~$ cycles of length 1).

I am not sure about this.

In my opinion, we deal with combinations. Two long positive event cycles with the same elements must be equal because their elements must be in increasing order, excluding element 1 at the end of the cycles. No matter how we represent the cycle (1,4,12,8) or (8,12,1,4), it will always be (4,8,12,1), and this is a combination.
Based on your explanation, I believe you are trying to say that combinations are a special case of permutations, and if this is true, you are right, but I have never heard anything like this before.

 

[JimWhoKnew]

I am not sure about this.

In my opinion, we deal with combinations...
Based on your explanation, I believe you are trying to say that combinations are a special case of permutations, and if this is true, you are right, but I have never heard anything like this before.

It seems to me that we have a communication problem, assigning different names to concepts.

A permutation is a bijection of a set onto itself (from Wikipedia). The map between passenger's number (by boarding order) to the number of the seat in which he actually sits, satisfies this definition (remember: the seats were numbered such that passenger #k was supposed to sit in seat #k - the identity transformation/permutation). In the context of $~S_n~$ we can regard the distinct permutations as distinct combinations for "arranging" the n integers, so we probably use the different words to describe the same thing.

Two long positive event cycles with the same elements must be equal because their elements must be in increasing order, excluding element 1 at the end of the cycles. No matter how we represent the cycle (1,4,12,8) or (8,12,1,4), it will always be (4,8,12,1), and this is a combination.

In the convention i"m using, cycles begin with the smallest number (on the left). In our present context, the long cycles begin with 1. I wrote it in #11 and #13. With this convention, the representation is determined uniquely, eliminating the freedom you've described. I'm not calculating the number of equivalent representations, I'm calculating the number of distinct representation-invariant "physical outcomes" (permutations/combinations/sitting arrengements).

So knowing that I use the convention that cycles begin with the smallest number, please take a look at the detailed example in #18. Even if you disagree, I trust you'll be able to figure out what I'm trying to say there. Then you'll be able to point out with a concrete example whatever you disagree about.

 

[JimWhoKnew]

I am not sure about this.

In my opinion, we deal with combinations. Two long positive event cycles with the same elements must be equal because their elements must be in increasing order, excluding element 1 at the end of the cycles. No matter how we represent the cycle (1,4,12,8) or (8,12,1,4), it will always be (4,8,12,1), and this is a combination.
Based on your explanation, I believe you are trying to say that combinations are a special case of permutations, and if this is true, you are right, but I have never heard anything like this before.

I think I understand your point (partially). Mapping passengers to seats is not a bijection of a set onto itself. For example, we can't simply compose 2 functions of this sort, and there is no group structure. But mathematically we can describe it as a bijection of the set $~\{1,2,\dots,n\}~$ onto itself, and the representation by cycles is still useful. Your suggestion of "Combinations" may be better.

Apart from that, do you have any other comments on the example in #18 ?