1978 IMO Problems/Problem 6

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$

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

Problem

Solution

See Also