The pigeonhole principle states that if n items are placed into m containers and n is greater than m, then at least one container must hold more than one item. Although the statement seems obvious, it is a genuine counting argument capable of proving unexpected results, such as that at least two people in London must have exactly the same number of hairs on their heads, since the city's population exceeds the maximum possible hair count by more than one. The principle appears as early as 1622 in a book by Jean Leurechon, but is more commonly called Dirichlet's box principle or Dirichlet's drawer principle after Peter Gustav Lejeune Dirichlet's 1834 treatment of it under the name Schubfachprinzip. A more general, quantified version states that if n = km + 1 objects are distributed among m sets, at least one set contains at least k + 1 objects, and the principle extends to infinite sets through the formal statement that no injective function can have a codomain smaller than its domain.
Facts
Connections
Associated With
Attributed To
Source Pigeonhole principle (Wikipedia)
In Branch
Sources
1. Pigeonhole principle (Wikipedia)
Wikimedia FoundationLead section
In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item.
History
Perhaps the first written reference to the pigeonhole principle appears in a short sentence from the French Jesuit Jean Leurechon's 1622 work Selectæ Propositiones: "It is necessary that two men have the same number of hairs, écus, or other things, as each other." The full principle was spelled out two years later, with additional examples, in another book that has often been attributed to Leurechon, but might be by Jean Appier Hanzelet.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.