2007 USAMO Problems/Problem 3
(András Gyárfás) 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.
Claim: If we have instead elements, then we must have k disjoint subsets in a class. We proceed by Induction
Base Case: is trivial.
Case 1: If there exists an element subset s.t. has 2 n-element subsets in different classes. Consider the elements that are not in , from the Induction hypothesis, we have disjoint subsets in one of the classes. Those subsets paired with a subset of in the same class forms disjoint subsets of size n.
Case 2: All element subsets have all of their n-element subsets in one class. Look at any 2 n-element subsets and . Then we can create a path s.t. any 2 consecutive terms belong to the same n+1-element subset.(i.e. we change 1 element each time.) Thus, and are in the same class and we see that all subsets are in one class. Obviously we can find disjoint subsets of size n.
The question is asking for the case when which we have proved.
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.
In order to apply induction, we generalize the result to be proved so that it reads as follows:
Proposition. If the -element subsets of a set with elements are partitioned into two classes, then there are at least pairwise disjoint sets in the same class.
Proof. Fix and proceed by induction on . The case of is trivial. Assume and that the proposition is true for . Let be the partition of the -element subsets into two classes. If all the -element subsets belong to the same class, the result is obvious. Otherwise select two -element subsets and from different classes so that their intersection has maximal size. It is easy to see that . (If , then build from by replacing some element not in with an element of not already in . Then and and either and or and are in different classes.) Removing from , there are elements left. On this set the partition induced by has, by the inductive hypothesis, pairwise disjoint sets in the same class. Adding either or as appropriate gives pairwise disjoint sets in the same class.
Remark: The value is sharp. A set with elements can be split into a set with elements and a set of elements. Let one class consist of all -element subsets of and the other consist of all -element subsets that intersect . Then neither class contains pairwise disjoint sets.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
- <url>viewtopic.php?t=145845 Discussion on AoPS/MathLinks</url>
|2007 USAMO (Problems • Resources)
|1 • 2 • 3 • 4 • 5 • 6
|All USAMO Problems and Solutions