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 "1978 IMO Problems/Problem 6"

(Created page with "<math>emph{Problem:}</math> An international society has its members from six different countries. The list of members has 1978 names, numbered <math>\color[rgb]{0.35,0.35,0.3...")
 
m (Added sections)
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
<math>emph{Problem:}</math> An international society has its members from six different countries. The list of members has 1978 names, numbered <math>\color[rgb]{0.35,0.35,0.35}1, 2, \ldots, 1978</math>. Prove that there is at least one member whose number is the sum of the numbers of two (not necessarily distinct) members from his own country.
+
==Problem==
  
−
<math>\emph{Proof:}</math> Lets consider the members numbered <math>1,2,3,\ldots 989</math>. If these members belong to <math>1\leq k\leq 6</math> countries then, by the Pigeonhole principle, there must exist a country to which a minimum of <math>\lfloor \frac{988}{k}\rfloor +1</math>
+
An international society has its members from six different countries. The list of members has 1978 names, numbered <math>1, 2, \ldots, 1978</math>. Prove that there is at least one member whose number is the sum of the numbers of two (not necessarily distinct) members from his own country.
 +
 
 +
==Solution==
 +
 
 +
Suppose the contrary. Then there exists a partition of <math>\{1,2,3,\ldots, 1978\}</math> into 6 difference-free subsets <math>A,B,C,D,E,F</math>. A set S is difference-free if there are not <math>x,y,z \in S</math> such that x = y - z.
 +
 
 +
By the Pigeonhole principle, one of these subsets, say <math>A</math>, has a minimum of <math>\left \lfloor \frac{1978}{6}\right \rfloor +1 = 330</math> members, <math>a_1 < a_2 < \ldots < a_{330}</math>. Since <math>A</math> is difference-free, each of the <math>329</math> differences <math>a_{330} - a_1, a_{330} - a_2, \ldots, a_{330} - a_{329}</math> cannot belong to <math>A</math>, and so must belong to one of <math>B, C, D, E, F</math>.
 +
 
 +
One of these subsets, say <math>B</math>, has a minimum of <math>\left \lfloor \frac{329}{5}\right \rfloor +1 = 66</math> members, <math>b_1 < b_2 < \ldots < b_{66}</math>. Since <math>A</math> and <math>B</math> are difference-free, each of the <math>65</math> differences <math>b_{66} - b_1, b_{66} - b_2, \ldots, b_{66} - b_{65}</math> cannot belong to one of <math>A, B</math>, and so must belong to one of <math>C, D, E, F</math>.
 +
 
 +
One of these subsets, say <math>C</math>, has a minimum of <math>\left \lfloor \frac{65}{4}\right \rfloor +1 = 17</math> members, <math>c_1 < c_2 < \ldots < c_{17}</math>. Since <math>A, B, C</math> are difference-free, each of the <math>16</math> differences <math>c_{17} - c_1, c_{17} - c_2, \ldots, c_{17} - c_{16}</math> cannot belong to one of <math>A, B, C</math>, and so must belong to one of <math>D, E, F</math>.
 +
 
 +
One of these subsets, say <math>D</math>, has a minimum of <math>\left \lfloor \frac{16}{3}\right \rfloor +1 = 6</math> members, <math>d_1 < d_2 < \ldots < d_6</math>. Since <math>A, B, C, D</math> are difference-free, each of the <math>5</math> differences <math>d_6 - d_1, d_6 - d_2, \ldots, d_6 - d_5</math> cannot belong to one of <math>A, B, C, D</math>, and so must belong to one of <math>E, F</math>.
 +
 
 +
One of these subsets, say <math>E</math>, has a minimum of <math>\left \lfloor \frac{5}{2}\right \rfloor +1 = 3</math> members, <math>e_1 < e_2 < e_3</math>. Since <math>A, B, C, D, E</math> are difference-free, each of the <math>2</math> differences <math>e_3 - e_1, e_3 - e_2</math> cannot belong to one of <math>A, B, C, D, E</math>, and so must belong to <math>F</math>.
 +
 
 +
Then <math>F</math> has at least two members, <math>f_1 < f_2</math>. The difference <math>g = f_2 - f_1</math> cannot belong to one of <math>A, B, C, D, E, F</math>, a contradiction! <math>\blacksquare</math>
 +
 
 +
== See Also == {{IMO box|year=1978|num-b=5|after=Last Question}}

Latest revision as of 01:12, 2 March 2025

Problem

An international society has its members from six different countries. The list of members has 1978 names, numbered $1, 2, \ldots, 1978$. Prove that there is at least one member whose number is the sum of the numbers of two (not necessarily distinct) members from his own country.

Solution

Suppose the contrary. Then there exists a partition of $\{1,2,3,\ldots, 1978\}$ into 6 difference-free subsets $A,B,C,D,E,F$. A set S is difference-free if there are not $x,y,z \in S$ such that x = y - z.

By the Pigeonhole principle, one of these subsets, say $A$, has a minimum of $\left \lfloor \frac{1978}{6}\right \rfloor +1 = 330$ members, $a_1 < a_2 < \ldots < a_{330}$. Since $A$ is difference-free, each of the $329$ differences $a_{330} - a_1, a_{330} - a_2, \ldots, a_{330} - a_{329}$ cannot belong to $A$, and so must belong to one of $B, C, D, E, F$.

One of these subsets, say $B$, has a minimum of $\left \lfloor \frac{329}{5}\right \rfloor +1 = 66$ members, $b_1 < b_2 < \ldots < b_{66}$. Since $A$ and $B$ are difference-free, each of the $65$ differences $b_{66} - b_1, b_{66} - b_2, \ldots, b_{66} - b_{65}$ cannot belong to one of $A, B$, and so must belong to one of $C, D, E, F$.

One of these subsets, say $C$, has a minimum of $\left \lfloor \frac{65}{4}\right \rfloor +1 = 17$ members, $c_1 < c_2 < \ldots < c_{17}$. Since $A, B, C$ are difference-free, each of the $16$ differences $c_{17} - c_1, c_{17} - c_2, \ldots, c_{17} - c_{16}$ cannot belong to one of $A, B, C$, and so must belong to one of $D, E, F$.

One of these subsets, say $D$, has a minimum of $\left \lfloor \frac{16}{3}\right \rfloor +1 = 6$ members, $d_1 < d_2 < \ldots < d_6$. Since $A, B, C, D$ are difference-free, each of the $5$ differences $d_6 - d_1, d_6 - d_2, \ldots, d_6 - d_5$ cannot belong to one of $A, B, C, D$, and so must belong to one of $E, F$.

One of these subsets, say $E$, has a minimum of $\left \lfloor \frac{5}{2}\right \rfloor +1 = 3$ members, $e_1 < e_2 < e_3$. Since $A, B, C, D, E$ are difference-free, each of the $2$ differences $e_3 - e_1, e_3 - e_2$ cannot belong to one of $A, B, C, D, E$, and so must belong to $F$.

Then $F$ has at least two members, $f_1 < f_2$. The difference $g = f_2 - f_1$ cannot belong to one of $A, B, C, D, E, F$, a contradiction! $\blacksquare$

See Also

1978 IMO (Problems) • Resources
Preceded by
Problem 5 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Last Question
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1978_IMO_Problems/Problem_6&oldid=244106"