1985 IMO Problems/Problem 2
Problem
Let and be given relatively prime natural numbers, . Each number in the set is colored either blue or white. It is given that
(i) for each , both and have the same color;
(ii) for each , both and have the same color.
Prove that all the numbers in have the same color.
Solution
We may consider the elements of as residues mod . 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 , which put no restrictions on the colors of the other residues.
We note that (i) is equivalent to saying that has the same color as , and given this, (ii) implies that and have the same color. But this means that , and have the same color, which is to say that all residues of the form have the same color. But these are all the residues mod , since and 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.
1985 IMO (Problems) • Resources) | ||
Preceded by Problem 1 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 3 |
All IMO Problems and Solutions |