1979 USAMO Problems/Problem 5
Let be distinct subsets of with . Prove that for some pair .
Suppose the problem statement does not hold. It is clear that . Choose the smallest such that for each .
First, the subsets have elements (some repeated) in conjunction. Because there are elements of total, by the Pigeonhole Principle one element of , say , is in at least four subsets. Let these subsets be , without loss of generality, and let have elements . Then without loss of generality let have elements . If set has elements , then simple casework shows that it is impossible to create without having intersect one of at exactly one element. Thus assume has elements . Then has elements . Consider each remaining set . Then either contains both or none of them. Because there are distinct elements of apart from , at most subsets can contain . Then at least 3 subsets do not contain , and it is easy to see that they are disjoint from those subsets that do contain . Thus, we can partition into two subsets, one of which is the union of the subsets that do contain , and the other is the union of the subsets that do not contain . Because the latter subset has elements, we may use infinite descent to contradict the minimality of . The proof is complete.
|1979 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|