TheoremProved

Pigeonhole principle

Statement

If $n+1$ or more objects are placed into $n$ boxes, at least one box contains two or more objects. More generally, if $kn+1$ objects are placed into $n$ boxes, some box contains at least $k+1$ objects.

Why is it true?

You cannot fit more pigeons into holes than holes allow without doubling someone up: if there are strictly more items than containers, at least one container must hold more than one item. It sounds trivial, but forcing a repetition or collision out of a simple counting mismatch is a surprisingly powerful proof technique.

Proof sketch

Proof by contradiction: if every one of the $n$ boxes contained at most $k$ objects, the total number of objects would be at most $kn$ , contradicting that there are $kn+1$ objects. Hence some box must contain at least $k+1$ objects.

Topics that use this theorem

The pigeonhole principle

Related theorems

Ramsey's theorem Inclusion–exclusion principle

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

Richard A. Brualdi (2010). Introductory Combinatorics