Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

 
(→‎Problem)
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
Let <math>\displaystyle n</math> and <math>\displaystyle k</math> be given relatively prime natural numbers, <math>\displaystyle n < k</math>.  Each number in the set <math>\displaystyle M = \{ 1,2, \ldots , n-1 \} </math> is colored either blue or white.  It is given that
+
Let <math>n</math> and <math>k</math> be given relatively prime natural numbers, <math>k < n</math>.  Each number in the set <math>M = \{ 1,2, \ldots , n-1 \} </math> is colored either blue or white.  It is given that
  
−
(i) for each <math> i \in M </math>, both <math> \displaystyle i </math> and <math> \displaystyle n-i </math> have the same color;
+
(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> \displaystyle i </math> and <math> \displaystyle |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>\displaystyle M</math> have the same color.
+
Prove that all the numbers in <math>M</math> have the same color.
  
 
== Solution ==
 
== Solution ==
  
−
We may consider the elements of <math>\displaystyle M </math> as residues mod <math>\displaystyle n</math>.  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 <math>\displaystyle k</math>, which put no restrictions on the colors of the other residues.
+
We may consider the elements of <math>M </math> as residues mod <math>n</math>.  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 <math>k</math>, which put no restrictions on the colors of the other residues.
  
−
We note that (i) is equivalent to saying that <math>\displaystyle i</math> has the same color as <math>\displaystyle -i</math>, and given this, (ii) implies that <math>\displaystyle i </math> and <math> \displaystyle (-i + k) </math> have the same color.  But this means that <math> \displaystyle i, -i </math>, and <math> \displaystyle i+k </math> have the same color, which is to say that all residues of the form <math> i + mk \; (m \in \mathbb{N}_0)</math> have the same color.  But these are all the residues mod <math>\displaystyle n</math>, since <math> \displaystyle k </math> and <math> \displaystyle n </math> are relatively prime.  Q.E.D.
+
We note that (i) is equivalent to saying that <math>i</math> has the same color as <math>-i</math>, and given this, (ii) implies that <math>i </math> and <math>(-i + k) </math> have the same color.  But this means that <math>i, -i </math>, and <math>i+k </math> have the same color, which is to say that all residues of the form <math> i + mk \; (m \in \mathbb{N}_0)</math> have the same color.  But these are all the residues mod <math>n</math>, since <math>k </math> and <math>n </math> are relatively prime.  Q.E.D.
  
 
{{alternate solutions}}
 
{{alternate solutions}}
−
 
+
{{IMO box|year=1985|num-b=1|num-a=3}}
−
== Resources ==
 
−
 
 
−
* [[1985 IMO Problems]]
 
−
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=366589#p366589 Discussion on AoPS/MathLinks]
 
−
 
 
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 00:11, 12 July 2020

Problem

Let $n$ and $k$ be given relatively prime natural numbers, $k < n$. 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 the numbers 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1985_IMO_Problems/Problem_2&oldid=128126"