Problem of the Week 1228

Seats on a Plane

An airplane has seats numbered 1, 2, ..., 100. One hundred passengers are assigned seats and are about to board, with Alice going first and Bob last. But the first 99 passengers simply take random unoccupied seats.

Bob wants his assigned seat. If it is unoccupied, he sits in it. If it is occupied, he insists that the occupier move to his or her assigned seat. The displaced person must then move in the same way, perhaps displacing another person. This continues until all displaced people are seated.

What is the probability that Alice has to move?

Source: V. Pozdnyakov and J. M. Steele, Math Mag 89 (2016) 167-176.

[View the solution]