MathDB

3

Part of 2007 USAMO

Problems(1)

on parts of a partition of S into two classes( |S|=n^2+n-1)

Source: USAMO 2007

4/26/2007
Let SS be a set containing n2+nāˆ’1n^{2}+n-1 elements, for some positive integer nn. Suppose that the nn-element subsets of SS are partitioned into two classes. Prove that there are at least nn pairwise disjoint sets in the same class.
inductioncombinatorics