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 04: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 | ||
