IMO 1985 · Problem 2

Let \(n\) and \(k\) be given relatively prime natural numbers, \(k<n\). Each number in the set \(M=\{1,2,\ldots,n-1\}\) is colored either blue or white. It is given that

(i) for each \(i\in M\), both \(i\) and \(n-i\) have the same color;

(ii) for each \(i\in M\), \(i\ne k\), both \(i\) and \(|i-k|\) have the same color. Prove that all numbers in \(M\) must have the same color.

Official text of the problem. Official problem paper (PDF)

Solution

First, we show that whenever \(i\in M\) and \(i\ne k\), the number \(i\) has the same color as the unique element of \(M\) congruent to \(i-k\pmod n\).

If \(i>k\), this element is \(i-k\), and the assertion follows directly from (ii). If \(i<k\), condition (ii) gives that \(i\) and \(k-i\) have the same color. Since \(k-i\in M\), condition (i) gives that \(k-i\) and \(n-(k-i)\) have the same color. Thus \(i\) and \(n+i-k\), the required element, have the same color.

For each \(j=1,\ldots,n-1\), let \(a_j\) be the remainder of \(jk\) upon division by \(n\). Because \(\gcd(n,k)=1\), none of these remainders is zero: otherwise \(n\mid jk\) would imply \(n\mid j\), which is impossible. They are also pairwise distinct, since \[ a_p=a_q\quad\Longrightarrow\quad n\mid(p-q)k \quad\Longrightarrow\quad n\mid p-q \quad\Longrightarrow\quad p=q \] for \(1\le p,q\le n-1\). Consequently, \(a_1,\ldots,a_{n-1}\) are exactly the elements of \(M\), in some order.

Now \(a_1=k\). For every \(j=2,\ldots,n-1\), distinctness gives \(a_j\ne k\), and \[ a_j-k\equiv (j-1)k\equiv a_{j-1}\pmod n. \] By the observation proved above, \(a_j\) and \(a_{j-1}\) therefore have the same color. Hence all terms of \(a_1,\ldots,a_{n-1}\) have the same color, including when this list has just one term. Since this list contains every element of \(M\), the conclusion follows. \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).