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...")
 
(The previous solution was incorrect (the assertion that every pair of the a_i had a unique sum cannot be justified). This solution is based on that in Arthur Engel's Problem Solving Strategies.)
 
(2 intermediate revisions by 2 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.
+
<math>\emph{Problem:}</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.
  
−
<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>
+
<math>\emph{Proof:}</math> 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 18:45, 7 July 2023

$\emph{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.

$\emph{Proof:}$ 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=195396"