The Pigeonhole Principle

go back

The Pidgeonhole Principle

If $m$ items are placed in $n$ pigeonholes, where $m>n$, then at least one pigeonhole will contain more than one item

If you are asked to prove this, state that:

1. Identify the “Pigeons” and “Pigeonholes”: There is a total of $n$ pigeonholes, and $m$ pigeons
2. State the Pigeonhole Principle: By the pigeonhole principle, as the number of pigeons is larger than the number of pigeonholes, there must be at least 1 pigeonhole with at least 1 pigeon.
3. Give the Alternative “Worst Case” Explanation: Furthermore, assuming that at least $n$ pigeons are in different pigeonholes, then the $n+1th$ pigeon must be in one of the $n$ pigeonholes, and thus at least 1 pigeonhole will have at least 1 pigeon.