Exercise 1091Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026
Binomial coefficient bound
#pigeonhole#binomial#subset size
Statement
Show that if we choose more than subsets of an -element set, two have different sizes. (Actually, the largest number of distinct-size subsets is .) Show that among subsets, two have the same size.
Hint
The number of subsets of a given size is at most the middle binomial coefficient.
Show solutionHide solution
Solution
Sizes. There are possible sizes.
No pigeonhole needed if we choose subsets (two same size by pigeonhole).
But with subsets: if all sizes are distinct, at most sizes. So we'd need , which is false for . Contradiction.
Conclusion. Among subsets, two have the same size (for ).