2007 USAMO Problems/Problem 3
Problem
Let be a set containing elements, for some positive integer . Suppose that the -element subsets of are partitioned into two classes. Prove that there are at least pairwise disjoint sets in the same class.
Solution
Call an -element subset of separable if it has a subset in each class of the partition. We recursively build a set of disjoint separable subsets of : begin with empty and at each step if there is a separable subset which is disjoint from all sets in add that set to . The process terminates when every separable subset intersects a set in . Let be the set of elements in which are not in any set in . We claim that one class contains every -element subset of .
Suppose that are elements of . Denote by the set . Note that for each , is not separable, so that and are in the same class. But then is in the same class for each — in particular, and are in the same class. But for any two sets we may construct such a sequence with equal to one and equal to the other.
We are now ready to construct our disjoint sets. Suppose that . Then , so we may select disjoint -element subsets of . Then for each of the sets in , we may select a subset which is in the same class as all the subsets of , for a total of disjoint sets.
See also
2007 USAMO (Problems • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.