1985 IMO Problems/Problem 2

Problem

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

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

(ii) for each $i \in M, i \neq k$ , both $\displaystyle i$ and $\displaystyle |i-j|$ have the same color.

Prove that all number in $\displaystyle M$ have the same color.

Solution

We may consider the elements of $\displaystyle M$ as residues mod $\displaystyle n$ . To these we may add the residue 0, since (i) may only imply that 0 has the same color as itself, and (ii) may only imply that 0 has the same color as $\displaystyle k$ , which put no restrictions on the colors of the other residues.

We note that (i) is equivalent to saying that $\displaystyle i$ has the same color as $\displaystyle -i$ , and given this, (ii) implies that $\displaystyle i$ and $\displaystyle (-i + k)$ have the same color. But this means that $\displaystyle i, -i$ , and $\displaystyle i+k$ have the same color, which is to say that all residues of the form $i + mk \; (m \in \mathbb{N}_0)$ have the same color. But these are all the residues mod $\displaystyle n$ , since $\displaystyle k$ and $\displaystyle n$ are relatively prime. Q.E.D.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Page

Toolbox

Search

1985 IMO Problems/Problem 2

Problem

Solution

Resources