1985 IMO Problems/Problem 2
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.
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|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|