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.
Problem 1071
Official 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 - 1, a 2 - 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 © John Scholes [email protected] 16 Dec 2002