pigeonhole principle

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 nkm + 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:

  1. If n objects are distributed into n bins so that no bin contains more than one object, then each bin contains exactly one object.
  2. If n objects are distributed into n bins so that no bin contains no objects, then each bin contains exactly one object.
  3. If n objects are distributed into m bins and n < m, then at least one bin will contain no objects.

 

« Back to Glossary Index

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.