IMO 1977 LL SWE41

Origin: SWE

Problem

A wheel consists of a fixed circular disk and a mobile circular ring. On the disk the numbers 1, 2, 3, . . ., N are marked, and on the ring N integers a1, a2, . . . , aN of sum 1 are marked (see the figure). The ring can be turned into N differ- ent positions in which the numbers on the disk and on the ring match each other. Multiply every number on the ring with the corresponding number on the disk and form the sum of N products. In this way a a1 a2 a3 a4 \cdot \cdot \cdot aN \cdot \cdot \cdot N sum is obtained for every position of the ring. Prove that the N sums are different.

Solution

The considered sums are congruent modulo n to Sk = N i=1(i + k)ai, k = 0, 1, . . ., N −1. Since Sk = S0 + k(a1 + \cdot \cdot \cdot + an) = S0 + k, all these sums give distinct residues modulo n and therefore are distinct.