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.
Suppose the contrary. Then there exists a partition of into 6 difference-free subsets . A set S is difference-free if there are not such that x = y - z.
By the Pigeonhole principle, one of these subsets, say , has a minimum of members, . Since is difference-free, each of the differences cannot belong to , and so must belong to one of .
One of these subsets, say , has a minimum of members, . Since and are difference-free, each of the differences cannot belong to one of , and so must belong to one of .
One of these subsets, say , has a minimum of members, . Since are difference-free, each of the differences cannot belong to one of , and so must belong to one of .
One of these subsets, say , has a minimum of members, . Since are difference-free, each of the differences cannot belong to one of , and so must belong to one of .
One of these subsets, say , has a minimum of members, . Since are difference-free, each of the differences cannot belong to one of , and so must belong to .
Then has at least two members, . The difference cannot belong to one of , a contradiction!
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 |