More items than slots
The pigeonhole principle states that if you place more items than there are containers, at least one container holds more than one item. It sounds obvious, yet it underlies surprising algorithmic guarantees and lower bounds.
Where it shows up
- Hashing: if you hash more keys than there are buckets, some bucket must hold two keys, so collisions are unavoidable and must be handled. This proves no hash function can avoid collisions on a large enough key set.
- Cycle detection: a sequence of states drawn from a finite set must eventually repeat a state once it runs longer than the number of states, which guarantees that following pointers in a finite space enters a cycle.
- Duplicate finding: among n plus one numbers each between one and n, two must be equal, since there are only n distinct possible values.
A generalized form
The generalized principle sharpens the count: distributing items into containers forces some container to hold at least the total divided by the number of containers, rounded up. This is how arguments establish that a search or a counting structure must have a bucket of a certain minimum size, which often drives worst case lower bounds.
Key idea
The pigeonhole principle guarantees that more items than containers force a shared container; it proves unavoidable hash collisions, the existence of cycles in finite state spaces, and minimum bucket sizes for lower bounds.