Exercise 533Combinatorics › Pigeonhole principleL1Added 3 Nov 2026

Proof of the generalized pigeonhole principle

#generalized pigeonhole#proof#ceil

Statement

Prove the generalized pigeonhole principle: if $n$ pigeons occupy $k$ holes, some hole contains at least $\lceil n/k\rceil$ pigeons.

Hint

Contradiction: if every hole has $\le \lceil n/k\rceil -1$ , the total is at most $k(\lceil n/k\rceil-1)<n$ .

Show solutionHide solution

Contradiction. Suppose every hole has $\le \lceil n/k\rceil -1$ pigeons. Total $\le k(\lceil n/k\rceil-1)$ .

Bound. $\lceil n/k\rceil< n/k+1$ , so $\lceil n/k\rceil-1<n/k$ , hence $k(\lceil n/k\rceil-1)<n$ . Contradiction.

Conclusion. Some hole has $\ge\lceil n/k\rceil$ pigeons.