Editing Pigeonhole principle (section)

== Examples ==

=== Sock picking ===
Suppose a drawer contains a mixture of black socks and blue socks, each of which can be worn on either foot. You pull a number of socks from the drawer without looking. What is the minimum number of pulled socks required to guarantee a pair of the same color? By the pigeonhole principle ({{math|''m'' {{=}} 2}}, using one pigeonhole per color), the answer is three ({{math|''n'' {{=}} 3}} items). Either you have ''three'' of one color, or you have ''two'' of one color and ''one'' of the other.{{Citation needed|date=February 2025}}

=== Hand shaking ===
If {{math|''n''}} people can shake hands with one another (where {{math|''n'' > 1}}), the pigeonhole principle shows that there is always a pair of people who will shake hands with the same number of people. In this application of the principle, the "hole" to which a person is assigned is the number of hands that person shakes. Since each person shakes hands with some number of people from 0 to {{math|''n'' &minus; 1}}, there are {{math|''n''}} possible holes. On the other hand, either the "0" hole, the {{math|"''n'' &minus; 1"}} hole, or both must be empty, for it is impossible (if {{math|''n'' > 1}}) for some person to shake hands with everybody else while some person shakes hands with nobody. This leaves {{math|''n''}} people to be placed into at most {{math|''n'' &minus; 1}} non-empty holes, so the principle applies.

This hand-shaking example is equivalent to the statement that in any [[Graph (discrete mathematics)|graph]] with more than one [[Vertex (graph theory)|vertex]], there is at least one pair of vertices that share the same [[Degree (graph theory)|degree]].<ref>{{Cite web|last=Pandey|first=Avinash|title=D3 Graph Theory - Interactive Graph Theory Tutorials|url=https://d3gt.com/unit.html?pigeonhole|access-date=2021-01-12|website=d3gt.com|language=en}}</ref> This can be seen by associating each person with a vertex and each [[Edge (graph)|edge]] with a handshake.{{Citation needed|date=February 2025}}

=== Hair counting ===
One can demonstrate there must be at least two people in [[London]] with the same number of hairs on their heads as follows.<ref>{{cite book|title=The Psychology of Reasoning|first=Eugenio|last=Rignano|translator-first=Winifred A.|translator-last=Holl|publisher=K. Paul, Trench, Trubner & Company, Limited|year=1923|page=72|isbn=9780415191326 |url=https://books.google.com/books?id=1i9VAAAAMAAJ&pg=PA72}}</ref><ref>To avoid a slightly messier presentation, this example only refers to people who are not bald.</ref> Since a typical human head has an [[average]] of around 150,000 hairs, it is reasonable to assume (as an upper bound) that no one has more than 1,000,000 hairs on their head {{math|(''m'' {{=}} 1 million}} holes). There are more than 1,000,000 people in London ({{math|''n''}} is bigger than 1&nbsp;million items). Assigning a pigeonhole to each number of hairs on a person's head, and assigning people to pigeonholes according to the number of hairs on their heads, there must be at least two people assigned to the same pigeonhole by the 1,000,001st assignment (because they have the same number of hairs on their heads; or, {{math|''n'' > ''m''}}). Assuming London has 9.002 million people,<ref>{{Cite web|url=http://data.london.gov.uk/dataset/londons-population|title=London's Population / Greater London Authority (GLA)|website=data.london.gov.uk}}</ref> it follows that at least ten Londoners have the same number of hairs, as having nine Londoners in each of the 1 million pigeonholes accounts for only 9 million people.

For the average case ({{math|1=''m'' = 150,000}}) with the constraint: fewest overlaps, there will be at most one person assigned to every pigeonhole and the 150,001st person assigned to the same pigeonhole as someone else. In the absence of this constraint, there may be empty pigeonholes because the "collision" happens before the 150,001st person. The principle just proves the existence of an overlap; it says nothing about the number of overlaps (which falls under the subject of [[probability distribution]]).{{Citation needed|date=February 2025}}

There is a passing, satirical, allusion in English to this version of the principle in ''A History of the Athenian Society'', prefixed to ''A Supplement to the Athenian Oracle: Being a Collection of the Remaining Questions and Answers in the Old Athenian Mercuries'' (printed for Andrew Bell, London, 1710).<ref>{{Cite web|url=https://books.google.com/books?id=JCwUAAAAQAAJ&q=mean+hairs|title = A Supplement to the Athenian Oracle: Being a Collection of the Remaining Questions and Answers in the Old Athenian Mercuries. ... To which is Prefix'd the History of the Athenian Society, ... By a Member of the Athenian Society|year = 1710}}</ref> It seems that the question ''whether there were any two persons in the World that have an equal number of hairs on their head?'' had been raised in ''The Athenian Mercury'' before 1704.<ref>{{Cite web|url=https://books.google.com/books?id=4QsUAAAAQAAJ&q=sent+quarters|title = The Athenian Oracle being an entire collection of all the valuable questions and answers|year = 1704}}</ref><ref>{{Cite web|url=https://books.google.com/books?id=GG0PAAAAQAAJ&q=town+eternity|title = The Athenian Oracle: Being an Entire Collection of All the Valuable Questions and Answers in the Old Athenian Mercuries. ... By a Member of the Athenian Society|year = 1704}}</ref>

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'':<ref name=leurechon/> "It is necessary that two men have the same number of hairs, [[écu]]s, or other things, as each other."<ref>{{citation|first=Jean|last=Leurechon|title=Selecæe Propositiones in Tota Sparsim Mathematica Pulcherrimæ|year=1622|publisher=Gasparem Bernardum|page=2}}</ref> 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 one of his students.<ref name=leurechon/>

=== The birthday problem ===
{{Main|Birthday problem}}

The birthday problem asks, for a set of {{math|''n''}} randomly chosen people, what is the probability that some pair of them will have the same birthday? The problem itself is mainly concerned with counterintuitive probabilities, but we can also tell by the pigeonhole principle that among 367 people, there is at least one pair of people who share the same birthday with 100% probability, as there are only 366 possible birthdays to choose from.

=== Team tournament ===
Imagine seven people who want to play in a tournament of teams {{math|(''n'' {{=}} 7}} items), with a limitation of only four teams {{math|(''m'' {{=}} 4}} holes) to choose from. The pigeonhole principle tells us that they cannot all play for different teams; there must be at least one team featuring at least two of the seven players:{{Citation needed|date=February 2025}} 
: <math display=block> \left\lfloor \frac{n-1}{m} \right\rfloor + 1 = \left\lfloor \frac{7-1}{4} \right\rfloor + 1 = \left\lfloor \frac64 \right\rfloor + 1 = 1 + 1 = 2 </math>

===Subset sum===
Any [[subset]] of size six from the [[set (math)|set]] <math> S = \{ 1,2,3, \dots ,9\} </math> must contain two elements whose sum is 10. The pigeonholes will be labeled by the two element subsets <math> \{1,9\}, \{2,8\}, \{3,7\}, \{4,6\} </math> and the [[singleton (mathematics)|singleton]] <math> \{5\} </math> , five pigeonholes in all. When the six "pigeons" (elements of the size six subset) are placed into these pigeonholes, each pigeon going into the pigeonhole that has it contained in its label, at least one of the pigeonholes labeled with a two-element subset will have two pigeons in it.<ref>{{harvnb|Grimaldi|1994|page=277}}</ref>

===Hashing===

[[Hash_function|Hashing]] in [[computer science]] is the process of mapping an arbitrarily large set of data {{math|''n''}} to {{math|''m''}} fixed-size values. This has applications in [[caching]] whereby large data sets can be stored by a reference to their representative values (their "hash codes") in a "hash table" for fast recall. Typically, the number of unique objects in a data set {{math|''n''}} is larger than the number of available unique hash codes {{math|''m''}}, and the pigeonhole principle holds in this case that hashing those objects is no guarantee of uniqueness, since if you hashed all objects in the data set {{math|''n''}}, some objects must necessarily share the same hash code.{{Citation needed|date=February 2025}}