1972 IMO Problems/Problem 1
Problem
Prove that from a set of ten distinct two-digit numbers (in the decimal system), it is possible to select two disjoint subsets whose members have the same sum.
Solution
There are distinct subsets of our set of 10 two-digit numbers. The sum of the elements of any subset of our set of 10 two-digit numbers must be between and . (There are fewer attainable sums.) As , the Pigeonhole Principle implies there are two distinct subsets whose members have the same sum. Let these sets be and . Now, let and . Notice and are disjoint. They are also nonempty because if or , then one of and is a subset of the other, so they are either not distinct or have different sums. Therefore and are disjoint subsets our set of 10 distinct two-digit numbers, which proves the claim.
See Also
1972 IMO (Problems) • Resources | ||
Preceded by First Problem |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 2 |
All IMO Problems and Solutions |