Maths WorkshopMaths problems with full solutions
Exercise 1091Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Binomial coefficient bound

#pigeonhole#binomial#subset size

Statement

Show that if we choose more than (n⌊n/2⌋)\binom{n}{\lfloor n/2\rfloor} subsets of an nn-element set, two have different sizes. (Actually, the largest number of distinct-size subsets is n+1n+1.) Show that among (n⌊n/2⌋)+1\binom{n}{\lfloor n/2\rfloor}+1 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 n+1n+1 possible sizes.

No pigeonhole needed if we choose n+2n+2 subsets (two same size by pigeonhole).

But with (n⌊n/2⌋)+1\binom{n}{\lfloor n/2\rfloor}+1 subsets: if all sizes are distinct, at most n+1n+1 sizes. So we'd need n+1≥(n⌊n/2⌋)+1n+1\ge\binom{n}{\lfloor n/2\rfloor}+1, which is false for n≥4n\ge4. Contradiction.

Conclusion. Among (n⌊n/2⌋)+1\binom{n}{\lfloor n/2\rfloor}+1 subsets, two have the same size (for n≥4n\ge4).