IMO 1985 SL 4

Origin: AUS

Problem

Each of the numbers in the set N = {1, 2, 3, . . ., n −1}, where n \geq3, is colored with one of two colors, say red or black, so that: (i) i and n −i always receive the same color, and (ii) for some j \inN, relatively prime to n, i and |j −i| receive the same color for all i \inN, i ̸= j. Prove that all numbers in N must receive the same color.

Solution

Let ⟨x⟩denote the residue of an integer x modulo n. Also, we write a ∼b if a and b receive the same color. We claim that all the numbers ⟨ij⟩, i = 1, 2, . . . , n −1, are of the same color. Since j and n are coprime, this will imply the desired result. We use induction on i. For i = 1 the statement is trivial. Assume now that the statement is true for i = 1, . . . , k −1. For 1 < k < n we have ⟨kj⟩̸= j. If ⟨kj⟩> j, then by (ii), ⟨kj⟩∼⟨kj⟩−j = ⟨(k−1)j⟩. If otherwise ⟨kj⟩< j, then by (ii) and (i), ⟨kj⟩∼j −⟨kj⟩∼n −j + ⟨kj⟩= ⟨(k −1)j⟩. This completes the induction.