Difference between revisions of "1978 IMO Problems/Problem 6"

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$

@@ 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>\left \lfloor \frac{988}{k}\right \rfloor +1</math> members belong. Let the numbers assigned to these members be <math>a_1,a_2,\ldots, a_{\left \lfloor \frac{988}{k}\right \rfloor +1}</math>, where we assume WLOG that
+<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.
-<cmath>1\leq a_1<a_2<a_3<\cdots<a_{\left \lfloor \frac{988}{k}\right \rfloor +1}\leq 989.</cmath>
+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>.
-Assuming that these numbers satisfy the conditions of the problem, then there exists no <math>(x,y,z)</math> triple (not necessarily distinct), such that <math>a_x+a_y = a_z</math>. Since every pair of the above <math>a_i</math> correspond to a unique sum less than or equal to 1978, then there are minimum of <math>\dbinom{\left \lfloor \frac{988}{k}\right \rfloor +1}{2}</math> numbers that must be assigned to members of the other countries. Note that this doesn't account for the case when <math>x=y</math>. Consequently, if we can show that
+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>.
-<cmath>\dbinom{\left \lfloor \frac{988}{k}\right \rfloor +1}{2}>1978-\left (\left \lfloor \frac{988}{k}\right \rfloor +1\right ) (*)</cmath>
+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>.
-for all <math>1\leq k\leq 6</math>, then, by the Pigeonhole Principle, there is at least one member whose number is the sum of the numbers of two other members from his own country. It is easy to verify by hand that <math>(*)</math> holds for all <math>k</math> within the desired range, and hence, our proof is complete. <math>\blacksquare</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}}

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

Page

Toolbox

Search

Difference between revisions of "1978 IMO Problems/Problem 6"

Latest revision as of 18:45, 7 July 2023

See Also