Difference between revisions of "1985 IMO Problems/Problem 2"

Revision as of 08:19, 4 April 2010

Problem

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

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

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

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

Solution

We may consider the elements of $M$ as residues mod $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 $k$ , which put no restrictions on the colors of the other residues.

We note that (i) is equivalent to saying that $i$ has the same color as $-i$ , and given this, (ii) implies that $i$ and $(-i + k)$ have the same color. But this means that $i, -i$ , and $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 $n$ , since $k$ and $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.

1985 IMO (Problems) • Resources
Preceded by Problem 1	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 3
All IMO Problems and Solutions

@@ Line 5: / Line 5: @@
 (i) for each <math> i \in M </math>, both <math>i </math> and <math>n-i </math> have the same color;
-(ii) for each <math> i \in M, i \neq k </math>, both <math>i </math> and <math>|i-j| </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 number in <math>M</math> have the same color.

Page

Toolbox

Search

Difference between revisions of "1985 IMO Problems/Problem 2"

Revision as of 08:19, 4 April 2010

Problem

Solution