1978 IMO Problems/Problem 6

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

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

1978 IMO Problems/Problem 6

See Also