Exercise 893Combinatorics › Counting principlesL1Added 3 Nov 2026

Pigeonhole proof

#pigeonhole#proof#contradiction

Statement

Prove the pigeonhole principle: if $n$ pigeons are placed in $k$ holes and $n>k$ , then some hole contains at least $2$ pigeons.

Hint

Contradiction: if each hole has $\le1$ , then $n\le k$ .

Show solutionHide solution

Contradiction. Suppose each hole has at most $1$ pigeon. Then the total number of pigeons is at most $k$ . But $n>k$ , contradiction.

Conclusion. Some hole has $\ge2$ pigeons.