This is a neat little problem that I was discussing today with my lab group out at lunch. Not particularly difficult but interesting implications nonetheless
Imagine there are a 100 people in line to board a plane that seats 100. The first person in line, Alice, realizes she lost her boarding pass, so when she boards she decides to take a random seat instead. Every person that boards the plane after her will either take their “proper” seat, or if that seat is taken, a random seat instead.
Question: What is the probability that the last person that boards will end up in their proper seat?
Moreover, and this is the part I’m still pondering about. Can you think of a physical system that would follow this combinatorial statistics? Maybe a spin wave function in a crystal etc…
Here is a rephrasing which simplifies the intuition of this nice puzzle.
Suppose whenever someone finds their seat taken, they politely evict the squatter and take their seat. In this case, the first passenger (Alice, who lost her boarding pass) keeps getting evicted (and choosing a new random seat) until, by the time everyone else has boarded, she has been forced by a process of elimination into her correct seat.
This process is the same as the original process except for the identities of the people in the seats, so the probability of the last boarder finding their seat occupied is the same.
When the last boarder boards, Alice is either in her own seat or in the last boarder’s seat, which have both looked exactly the same (i.e. empty) to her up to now, so there is no way poor Alice could be more likely to choose one than the other.