In mathematics, the pigeonhole principle states that if n items are to be sorted into m bins and n > m, then at least of the containers must contain more than one item.
A more quantified version states that for natural numbers n, k, and m, if there are n = km + 1 items and m bins, then at least one bin will contain k + 1 objects.
The pigeonhole principle serves as the premise for many other useful postulates, including:
- If n objects are distributed into n bins so that no bin contains more than one object, then each bin contains exactly one object.
- If n objects are distributed into n bins so that no bin contains no objects, then each bin contains exactly one object.
- If n objects are distributed into m bins and n < m, then at least one bin will contain no objects.
« Back to Glossary Index