A lecturer at my uni recently nerd sniped[1] me with a problem that was frankly joyful to solve. I was surprised to find that, despite being in an office full of physicists, I was the only person to solve this using a symmetry argument. So I thought I'd try to finally get around to doing some blogging by explaining what I think is the most elegant way to solve this problem.
The problem is as follows.
100 passengers are queueing to get on a plane. The first passenger is absent minded and sits in any seat with equal probability. Each other passenger will sit in their assigned seat if it is available, but will otherwise sit in any available seat with equal probability.
What is the probability that the final passenger to board will end up in their assigned seat?
It's often insightful to take a look some simpler situations and see if any patterns arise.
For the case of two passengers, the problem is somewhat trivial: if the first passenger sits in their assigned seat then the second (final) passenger can sit in their own seat. The answer is therefore \(\frac{1}{2}\).
For three passengers things are already quite a bit less trivial. With this in mind[2] we'll label the passengers \(P_1\), \(P_2\), and \(P_3\) based on the order in which the will board, and the seats \(S_1\), \(S_2\), and \(S_3\) based on which passenger is assigned to which seat. \(P_2\), for example, is the second passenger to board and has been assigned \(S_2\).
Let's look at what \(P_1\) could do:
If \(P_1\) sits in \(S_1\) or \(S_3\) then the outcome is determined already. If they sit in the second passenger's seat, however, then another choice is presented:
Therefore the possible ways that \(P_3\) could sit in \(S_3\) are if \(P_1\) sits in \(S_1\) (\(p = \frac{1}{3}\)) OR \(P_1\) sits in \(S_2\) (\(p = \frac{1}{3}\)) AND \(P_2\) sits in \(S_1\) (\(p = \frac{1}{2}\)). The probability is therefore
\[ p = \frac{1}{3} + \frac{1}{3} \cdot \frac{1}{2} = \frac{1}{2} \,. \]Four passengers makes thing yet more complicated, but it is worth examining because at least one vital pattern crops up. We'll label the passengers and seats in the same way (\(P_1 \ldots P_4\) and \(S_1 \ldots S_4\))
This time there are four possibilities for what \(P_1\) will do:
Again two of the choices determine the outcome, but the remaining two choices lead to different paths through the probability space. If \(P_2\) is forced to pick they could:
⚙ Note
At this point it's worth taking a moment to consider different ways in which the third passenger would be forced to pick at random:
It is important to note[^foreshadowing] that in both these situations \(S_2\) and \(S_3\) will be occupied, while \(S_1\) and \(S_4\) will be available. This will be important when we generalise this line of thinking to an arbitrary number of passengers.
And if \(P_3\) is forced to pick they could:
Phew. Having gone through all of the possible things that could happen, let's summarise the ways in which \(S_4\) could be available when \(P_4\) comes to sit:
The probability that \(S_4\) is available for \(P_4\) is therefore
\[ p = \frac{1}{4} + \frac{1}{4} \cdot \frac{1}{3} + \frac{1}{4} \cdot \frac{1}{3} \cdot \frac{1}{2} + \frac{1}{4} \cdot \frac{1}{2} = \frac{6}{24} + \frac{2}{24} + \frac{1}{24} + \frac{3}{24} = \frac{1}{2} \,. \]As we all know, if a pattern emerges in the first three cases that you check then all other cases will conform to that pattern[4] . But solely for fun, let's see if we can prove that this pattern holds for an arbitrary number of passengers \(n\).
What really cracked this problem for me, was when I drew out a table of all the possible places that \(P_1\) could sit and where the remaining passengers would end up:
| \(S_1\) | \(S_2\) | \(S_3\) | \(S_4\) | ... | \(S_i\) | ... | \(S_n\) |
|---|---|---|---|---|---|---|---|
| \(P_1\) | \(P_2\) | \(P_3\) | \(P_4\) | ... | \(P_i\) | ... | \(P_n\) |
| \(P_1\) | ... | ... | |||||
| \(P_2\) | \(P_1\) | ... | ... | ||||
| \(P_2\) | \(P_3\) | \(P_1\) | ... | ... | |||
| \(P_2\) | \(P_3\) | \(P_4\) | ... | \(P_1\) | ... | ||
| ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ | ⋮ |
| \(P_n\) | \(P_2\) | \(P_3\) | \(P_4\) | ... | \(P_i\) | ... | \(P_1\) |
Each row in this table indicates the known configuration of passengers (i.e. the passenger who would be able to sit in their assigned seat before another passenger has to pick at random) after \(P_1\) has sat in a particular seat. The important thing to internalise here is that if \(P_1\) sits in some arbitrary seat \(S_j\) then passengers \(P_2\) to \(P_{j - 1}\) will sit in their assigned seats.
However this is just a specific case of a more general rule. Let's consider an arbitrary passenger \(P_i\), and let's assume that seats \(S_2\) to \(S_i\) are occupied by passengers \(P_1\) to \(P_{i - 1}\) (which means that \(S_1\) and \(S_{i + 1}\) to \(S_n\) must be available):
The first two possibilities have the same probability of occurring and both resolve the problem (either forcing \(P_n\) to, or preventing \(P_n\) from being able to, sit in \(S_n\)), and the third possibility always puts \(P_j\) into exactly the same situation \(P_i\) (the special case of \(j = n - 1\) is still the same situation, it's just that the third possibility has a \(0\%\) chance of occurring). This means that once the situation described above occurs then the probability of \(P_n\) being able to sit \(S_n\) must be the same as the probability of \(P_n\) not being able to sit \(S_n\), as there is nothing to break the symmetry (all situations which could occur have the same probability for those two outcomes).
The final piece of this puzzle is to think back to the situation where \(P_1\) comes to take their seat (remember that \(P_1\) will seat in any seat at random). The three assumptions that we made for \(P_i\) were that they will need to pick at random, \(S_{i + 1}\) to \(S_n\) will be available, and \(S_1\) will be available. Well ... all three assumptions are already true for \(P_1\): they will pick at random, \(S_2\) to \(S_n\) are available since no-one has sat down yet, and \(S_1\) is available (again since no-one has sat down yet).
This means that the probability of \(P_n\) being able to sit in \(S_n\) must be the same as not being able to sit in \(S_n\), and since they must sit somewhere that probability is \(\frac{1}{2}\).
Despite being such a fundamentally important concept in many areas of science, I find that many scientists struggle to recognise situations where symmetry can be used to make rigorous arguments. In fact I myself only really got comfortable with it when I took a Master's course run by a lecturer who emphasised using symmetry to solve non-physics problems. If this post hasn't helped you recognise the power of symmetry in solving a variety of problems, I hope it has at least been interesting!