### 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 ai before the break. Suppose the result is false. Then we must have ai ≠ 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 ai - aj ≠ i - j mod 2n for all unequal i, j. Then ai - i ≠ aj - j for i and j distinct. Hence, working mod 2n, a1 - 1, a2 - 2, ... , a2n-1 - (2n-1) is just a permutation of 1, 2, ... , 2n-1. Hence ∑ (ai - i) = ∑ i = n(2n - 1) = n mod 2n. But ∑ (ai - i) = (∑ ai) - (∑ i) = 0 mod 2n. Contradiction. So for some i > j we must have ai - aj = i - j. But 1 ≤ ai, aj ≤ 2n-1, so -(2n-2) < (ai - aj) ≤ 2n-2. So either ai - aj = i - j, or ai - aj = 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.