Editing Pigeonhole principle (section)

{{short description|If there are more items than boxes holding them, one box must contain at least two items}}
[[Image:TooManyPigeons.jpg|thumb|right|Pigeons in holes. Here there are {{math|1=''n'' = 10}} pigeons in {{math|1=''m'' = 9}} holes. Since 10 is greater than 9, the pigeonhole principle says that at least one hole has more than one pigeon. (The top left hole has 2 pigeons.)]]

In [[mathematics]], the '''pigeonhole principle''' states that if {{mvar|n}} items are put into {{mvar|m}} containers, with {{math|''n'' > ''m''}}, then at least one container must contain more than one item.<ref name=Herstein64>{{harvnb|Herstein|1964|loc= p.&nbsp;90}}</ref> For example, of three gloves, at least two must be right-handed or at least two must be left-handed, because there are three objects but only two categories of handedness to put them into. This seemingly obvious statement, a type of [[combinatorics|counting argument]], can be used to demonstrate possibly unexpected results. For example, given that the [[Demographics of London|population of London]] is more than one unit greater than the maximum number of hairs that can be on a human's head, the principle requires that there must be at least two people in London who have the same number of hairs on their heads.

Although the pigeonhole principle appears as early as 1624 in a book attributed to [[Jean Leurechon]],<ref name=leurechon>{{cite journal|last1=Rittaud|first1=Benoît|last2=Heeffer|first2=Albrecht|doi=10.1007/s00283-013-9389-1|issue=2|journal=The Mathematical Intelligencer|mr=3207654|pages=27–29|title=The pigeonhole principle, two centuries before Dirichlet|volume=36|year=2014|hdl=1854/LU-4115264|s2cid=44193229|url=https://biblio.ugent.be/publication/4115264|hdl-access=free}}</ref> it is commonly called '''Dirichlet's box principle''' or '''Dirichlet's drawer principle''' after an 1834 treatment of the principle by [[Peter Gustav Lejeune Dirichlet]] under the name {{lang|de|Schubfachprinzip}} ("drawer principle" or "shelf principle").<ref>Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "[http://jeff560.tripod.com/p.html Pigeonhole principle]". In Jeff Miller (ed.) ''[http://jeff560.tripod.com/mathword.html Earliest Known Uses of Some of the Words of Mathematics]''. Electronic document, retrieved November 11, 2006</ref>

The principle has several generalizations and can be stated in various ways. In a more quantified version: for [[natural number]]s {{mvar|k}} and {{mvar|m}}, if {{math|1=''n'' = ''km'' + 1}} objects are distributed among {{mvar|m}} sets, the pigeonhole principle asserts that at least one of the sets will contain at least {{math|''k'' + 1}} objects.<ref>{{harvnb|Fletcher|Patty|1987|loc=p. 27}}</ref> For arbitrary {{mvar|n}} and {{mvar|m}}, this generalizes to <math>k + 1 = \lfloor(n - 1)/m \rfloor + 1 = \lceil n/m\rceil</math>, where <math>\lfloor\cdots\rfloor</math> and <math>\lceil\cdots\rceil</math> denote the [[floor and ceiling functions]], respectively.

Though the principle's most straightforward application is to [[finite set]]s (such as pigeons and boxes), it is also used with [[infinite set]]s that cannot be put into [[one-to-one correspondence]]. To do so requires the formal statement of the pigeonhole principle: "there does not exist an [[injective function]] whose [[codomain]] is smaller than its [[domain of a function|domain]]". Advanced mathematical proofs like [[Siegel's lemma]] build upon this more general concept.