1978 IMO Problems/Problem 6
An international society has its members from six different countries. The list of members has 1978 names, numbered
. 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.
Lets consider the members numbered
. If these members belong to
countries then, by the Pigeonhole principle, there must exist a country to which a minimum of
members belong. Let the numbers assigned to these members be
, where we assume WLOG that
Assuming that these numbers satisfy the conditions of the problem, then there exists no triple (not necessarily distinct), such that
. Since every pair of the above
correspond to a unique sum less than or equal to 1978, then there are minimum of
numbers that must be assigned to members of the other countries. Note that this doesn't account for the case when
. Consequently, if we can show that
for all , 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
holds for all
within the desired range, and hence, our proof is complete.