Solution
The answer is 1/2, independent of n. Correct solutions were received by Joseph DeVincentis, Stephen Meskin, Stephen Morris, Dan Velleman, Nagendra Gulur Dwarakanath, Jim Guilford, and Derek Smith.
We may assume the seat assignment is A → 1, B → 2, C → 3, D → 4. Assume the seats actually taken (including Bob = B, who goes last) are a, b, c, d. Then we have the permutation 1 → a, 2 → b, 3 → c, 4 → d, or, in list form, P = {a, b, c, d}. When Bob refuses to sit in b but sits in 2 instead, he starts a cycle of P. If Alice is in that cycle, she has to move; if not, not. So the question is: What is the probability that, in a random permutation, the cycle that contains 2 also contains 1?
There are many ways to see that the number of permutations for which 1 and 2 are in the same cycle equals the number of permutations for which 1 and 2 are not in the same cycle. The source article gave the following pretty method.
Suppose p is a permutation for which 1 and 2 are in the same cycle. Then p's cycles look like
(1 x x x x 2 y y y) (z z z)...(w w w)
Add parentheses )( before 2 to get a permutation that splits up 1 and 2.
(1 x x x x) (2 y y y) (z z z)...(w w w)
There are details to check, but this is indeed a pretty bijection of the two sets.
Dan Velleman sent this method: After the first 99 passengers are seated, but before Bob enters, Alice leaves her seat and goes to the bathroom. Now there are two empty seats: the original one, and Alice's (temporarily) empty seat. Bob enters, and the displacement procedure is followed until one of the two empty seats is occupied. By symmetry, the probability is 1/2 that Alice's seat is occupied and 1/2 that the original empty seat is occupied. Now Alice returns to her seat. If it is occupied, then she has to go to her assigned seat, and the displacement procedure continues as before. But the end result is the same as in the original description — there is just a delay in the procedure in the case that Alice is displaced. Therefore the answer is 1/2.
Stephen Morris sent this approach. A random permutation of {1, ..., n} may be generated by the following process. Start with A1 = 1 and map it to any number in {1, 2, ..., n} at random. Call this number A2. Now repeat this process starting with A2, and then A3 etc., until A1 recurs, at which point we have created a cycle. Now repeat the whole process on the remaining numbers to create a second cycle, and continue until all numbers have been mapped. The first cycle will contain 2 precisely when 2 occurs before 1 in our random choice, and it will not contain 2 precisely when 1 occurs before 2 in our random choice. Each is equally likely.
Derek Smith provided this short inductive proof. For n = 2, the answer is obviously 1/2. For larger n, with probability 1/n, Alice has to move because she is sitting in Bob's seat; and with (inductive) probability (1/2)*(n − 2)/n, Alice has to move because Bob took the seat of Carl (who now has Bob's problem for n − 1 seats).
1/n + (1/2)*(n − 2)/n = 1/2
A famous and more well-known problem is POW 1011. Alice is at the front of a line of 100 people ready to board a 100-seat airplane. Bob is at the back of the line. Alice has lost her boarding pass, so she simply takes a random seat. Everyone else takes their proper seat if it is available, or takes a random empty seat if not. What is the probability that Bob gets to sit in his properly assigned seat?
I thought the problems were different, but it is not immediately clear. Some readers think they are the same. They are indeed very similar, and the same methods can be applied to both. But there is one difference:
In POW 1228, the underlying permutation can be any permutation of {1, 2, ..., n}.
In POW 1011, the underlying permutation is a single cycle. So the set of permutations that arise in #1011 is smaller than the set for #1228.
Of course one can modify things so that any permutation occurs in #1011, so the problems are indeed very closely related.
[Back to Problem 1228]
© Copyright 2016 Stan Wagon. Reproduced with permission.