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:
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.
This problem was suggested by András Gyárfás.
The problems on this page are the property of the MAA's American Mathematics Competitions