1978 IMO Problems/Problem 6

Revision as of 18:45, 7 July 2023 by Shrekmate (talk | contribs) (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.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

$\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