IMO 1988 SL 31

Origin: USS

Problem

Around a circular table an even number of persons have a discussion. After a break they sit again around the circular table in a different order. Prove that there are at least two people such that the number of participants sitting between them before and after the break is the same.

Solution

Denote the number of participants by 2n, and assign to each seat one of the numbers 1, 2, . . ., 2n. Let the participant who was sitting at the seat k before the break move to seat \pi(k). It suffices to prove that for every permutation \pi of the set {1, 2, . . ., 2n}, there exist distinct i, j such that \pi(i) −\pi(j) = \pm(i −j), the differences being calculated modulo 2n. If there are distinct i and j such that \pi(i) −i = \pi(j) −j modulo 2n, then we are done. Suppose that all the differences \pi(i)−i are distinct modulo 2n. Then they take values 0, 1, . . . , 2n −1 in some order, and consequently 2n  i=1 (\pi(i) −i) = 0 + 1 + \cdot \cdot \cdot + (2n −1) \equivn(2n −1) (mod 2n). On the other hand, 2n i=1(\pi(i) −i) =  \pi(i) − i = 0, which is a contradiction because n(2n −1) is not divisible by 2n. Remark. For an odd number of participants, the statement is false. For example, the permutation (a, 2a, . . . , (2n+1)a) of (1, 2, . . . , 2n+1) modulo 2n+ 1 does not satisfy the statement when gcd(a2 −1, 2n+ 1) = 1. Check that such an a always exists.