Difference between revisions of "1985 IMO Problems/Problem 2"
5849206328x (talk | contribs) m |
(→Problem) |
||
Line 7: | Line 7: | ||
(ii) for each <math> i \in M, i \neq k </math>, both <math>i </math> and <math>|i-k| </math> have the same color. | (ii) for each <math> i \in M, i \neq k </math>, both <math>i </math> and <math>|i-k| </math> have the same color. | ||
− | Prove that all | + | Prove that all the numbers in <math>M</math> have the same color. |
== Solution == | == Solution == |
Revision as of 05:25, 14 January 2012
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 |