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} - 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.

© John Scholes

jscholes@kalva.demon.co.uk

16 Dec 2002