29th IMO shortlist 1988/31 solution

29th IMO 1988 shortlist

Problem 31

An even number of people have a discussion sitting at a circular table. After a break they sit down again in a different order. Show that there must be two people with the same number of people sitting between them before and after the break.

Solution

Label the people 0, 1, 2, ... , 2n-1. Suppose that before the break they are in the order 0, 1, 2, ... , 2n-1 (with 2n-1 also next to 0). Without loss of generality, we may assume that 0 sits in the same position after the break (rotating the table does not affect things). Suppose that after the break person i is in the position occupied by a_i before the break. Suppose the result is false. Then we must have a_i ≠ i for all i > 0 (otherwise 0 and i would have the same number of people between them before and after the break).

Suppose first that a_i - a_j ≠ i - j mod 2n for all unequal i, j. Then a_i - i ≠ a_j - j for i and j distinct. Hence, working mod 2n, a₁ - 1, a₂ - 2, ... , a_2n-1 - (2n-1) is just a permutation of 1, 2, ... , 2n-1. Hence ∑ (a_i - i) = ∑ i = n(2n - 1) = n mod 2n. But ∑ (a_i - i) = (∑ a_i) - (∑ i) = 0 mod 2n. Contradiction. So for some i > j we must have a_i - a_j = i - j. But 1 ≤ a_i, a_j ≤ 2n-1, so -(2n-2) < (a_i - a_j) ≤ 2n-2. So either a_i - a_j = i - j, or a_i - a_j = i - j - 2n. But the number of people between positions i and j is i - j - 1 going one way round and 2n - (i - j) - 1 going the other way round. So in either case there are the same number of people between persons i and j before and after the break. Contradiction.

29th IMO shortlist 1988