Exercise 1813Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Subsets of fixed size

#pigeonhole#subsets#size

Statement

Show that among any $\binom{2n}{n}+1$ subsets of a $2n$ -element set, two have the same size.

Hint

Wait: that's too many. Better problem: among any $n+1$ subsets of an $n$ -element set, two have the same size.

Show solutionHide solution

Sizes. Subsets of an $n$ -element set have sizes $0,1,\ldots,n$ : $n+1$ possible sizes.

Pigeonhole (corrected). With $n+2$ subsets, two have the same size. With exactly $n+1$ subsets, all sizes can be distinct.

Conclusion. $n+2$ subsets guarantee two of the same size.