|
|
| (667 intermediate revisions by more than 100 users not shown) |
| Line 1: |
Line 1: |
| {{multiple issues|
| | This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users. |
| {{no footnotes|date=July 2014}}
| |
| {{overly detailed|date=July 2014}}
| |
| {{ref improve|date=July 2014}}
| |
| }}
| |
| [[Image:TooManyPigeons.jpg|thumb|right|An image of pigeons in holes. Here there are {{nowrap|''n'' {{=}} 10}} pigeons in {{nowrap|''m'' {{=}} 9}} holes. Since 10 is greater than 9, the pigeonhole principle says that at least one hole has more than one pigeon.]]
| |
|
| |
|
| 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.<ref name=Herstein64>{{harvnb|Herstein|1964|loc= p. 90}}</ref> This theorem is exemplified in real-life by truisms like "there must be at least two left gloves or two right gloves in a group of three gloves". It is an example of a [[combinatorics|counting argument]], and despite seeming intuitive it can be used to demonstrate possibly unexpected results; for example, that two people in London have the same number of hairs on their heads (see [[Pigeonhole_principle#Hair-counting|below]]).
| | If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]] |
| | * Only registered users will be able to execute this rendering mode. |
| | * Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere. |
|
| |
|
| The first formalization of the idea is believed to have been made by [[Peter Gustav Lejeune Dirichlet]] in 1834 under the name ''Schubfachprinzip'' ("drawer principle" or "shelf principle"). For this reason it is also commonly called '''Dirichlet's box principle''', '''Dirichlet's drawer principle''' or simply "Dirichlet principle" — a name that could also refer to the minimum principle for [[harmonic function]]s. The original "drawer" name is still in use in [[French language|French]] ("principe des tiroirs"), [[Polish language|Polish]] ("zasada szufladkowa"), [[Hungarian language|Hungarian]] ("skatulyaelv"), [[Italian language|Italian]] ("principio dei cassetti"), [[German language|German]] ("Schubfachprinzip"), [[Danish language|Danish]] ("Skuffeprincippet"), and [[Chinese language|Chinese]] ("抽屉原理").
| | Registered users will be able to choose between the following three rendering modes: |
|
| |
|
| The principle has several generalizations and can be stated in various ways. In a more quantified generalization: for [[natural number]]s ''k'' and ''m'', if ''n'' = ''km'' + 1 objects are distributed among ''m'' sets, then the pigeonhole principle asserts that one of the sets will contain at least ''k'' + 1 objects.<ref>{{harvnb|Fletcher|Patty|1987|loc=p. 27}}</ref> For arbitrary ''n'' and ''m'' this generalizes to ''k'' + 1 = ⌊(''n'' - 1)/''m''⌋ + 1, where ⌊...⌋ is the [[floor function]].
| | '''MathML''' |
| | :<math forcemathmode="mathml">E=mc^2</math> |
|
| |
|
| Though the most straightforward application is to finite sets (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, which is ''"there does not exist an [[injective function]] on [[finite set]]s whose [[codomain]] is smaller than its [[domain (mathematics)|domain]]"''. Advanced mathematical proofs like [[Siegel's lemma]] build upon this more general concept.
| | <!--'''PNG''' (currently default in production) |
| | :<math forcemathmode="png">E=mc^2</math> |
|
| |
|
| == Examples == | | '''source''' |
| | :<math forcemathmode="source">E=mc^2</math> --> |
|
| |
|
| === Sock-picking === | | <span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples]. |
| Assume you have a mixture of black socks and blue socks, what is the minimum number of socks needed before a pair of the same color can be guaranteed. Using the pigeonhole principle, to have at least one pair of the same color {{nowrap|(''m'' {{=}} 2}} holes, one per color) using one pigeonhole per color, you need only three socks {{nowrap|(''n'' {{=}} 3}} items).
| |
|
| |
|
| === Hand-shaking === | | ==Demos== |
| If there are ''n'' people who can shake hands with one another (where {{nowrap|''n'' > 1}}), the pigeonhole principle shows that there is always a pair of people who will shake hands with the same number of people. As the 'holes', or ''m'', correspond to number of hands shaken, and each person can shake hands with anybody from 0 to {{nowrap|''n'' − 1}} other people, this creates {{nowrap|''n'' − 1}} possible holes. This is because either the '0' or the {{nowrap|'''n'' − 1'}} hole must be empty (if one person shakes hands with everybody, it's not possible to have another person who shakes hands with nobody; likewise, if one person shakes hands with no one there cannot be a person who shakes hands with everybody). This leaves ''n'' people to be placed in at most {{nowrap|''n'' − 1}} non-empty holes, guaranteeing duplication.
| |
|
| |
|
| === Hair-counting ===
| | Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]: |
| We can demonstrate there must be at least two people in [[London]] with the same number of hairs on their heads as follows. 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 {{nowrap|(''m'' {{=}} 1 million}} holes). There are more than 1,000,000 people in London (''n'' is bigger than 1 million items). Assigning a pigeonhole to each number of hairs on a person's head, and assign people to pigeonholes according to the number of hairs on their head, 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, {{nowrap|''n'' > ''m''}}). For the average case (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 we get to the 150,001st person. The principle just proves the existence of an overlap; it says nothing of the number of overlaps (which falls under the subject of [[Probability Distribution]]).
| |
|
| |
|
| === The birthday problem ===
| |
| The [[birthday problem]] asks, for a set of ''n'' randomly chosen people, what is the probability that some pair of them will have the same birthday. By the pigeonhole principle, if there are 367 people in the room, we know that there is at least one pair who share the same birthday, as there are only 366 possible birthdays to choose from (including February 29, the standard leap day). The birthday paradox refers to the surprising result that with a 50% probability there will be a pair of people with the same birthday in any group of 23 people.
| |
|
| |
|
| === Softball team ===
| | * accessibility: |
| Imagine seven people who want to play [[softball]] {{nowrap|(''n'' {{=}} 7}} items), with a limitation of only four softball teams {{nowrap|(''m'' {{=}} 4}} holes) to choose from. The pigeonhole principle tells us that they cannot all play for different teams. At least 2 must play on the same team:
| | ** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]] |
| : ⌊(n-1)/m⌋ + 1 = ⌊(7-1)/4⌋ + 1 = ⌊6/4⌋ + 1 = 1 + 1 = 2. | | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)] |
| | ** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)] |
| | ** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]]. |
| | ** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]]. |
| | ** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode. |
|
| |
|
| == Uses and applications == | | ==Test pages == |
|
| |
|
| The pigeonhole principle arises in [[computer science]]. For example, [[collision (computer science)|collisions]] are inevitable in a [[hash table]] because the number of possible keys exceeds the number of indices in the array. A [[hashing algorithm]], no matter how clever, cannot avoid these collisions.
| | To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages: |
| | *[[Displaystyle]] |
| | *[[MathAxisAlignment]] |
| | *[[Styling]] |
| | *[[Linebreaking]] |
| | *[[Unique Ids]] |
| | *[[Help:Formula]] |
|
| |
|
| The principle can be used to prove that any [[lossless data compression|lossless compression algorithm]], provided it makes some inputs smaller (as the name compression suggests), will also make some other inputs larger. Otherwise, the set of all input sequences up to a given length ''L'' could be mapped to the (much) smaller set of all sequences of length less than ''L'', and do so without collisions (because the compression is lossless), which possibility the pigeonhole principle excludes.
| | *[[Inputtypes|Inputtypes (private Wikis only)]] |
| | | *[[Url2Image|Url2Image (private Wikis only)]] |
| A notable problem in [[mathematical analysis]] is, for a fixed [[irrational number]] ''a'', to show that the set {[''na'']: ''n'' is an integer} of [[fractional part]]s is [[Dense-in-itself|dense]] in [0, 1]. One finds that it is not easy to explicitly find integers ''n'', ''m'' such that {{nowrap|{{!}}''na'' − ''ma''{{!}} < ''e''}}, where {{nowrap|''e'' > 0}} is a small positive number and ''a'' is some arbitrary irrational number. But if one takes ''M'' such that {{nowrap|1/''M'' < ''e''}}, by the pigeonhole principle there must be {{nowrap|''n''<sub>1</sub>, ''n''<sub>2</sub> ∈ {1, 2, ..., ''M'' + 1}}} such that ''n''<sub>1</sub>''a'' and ''n''<sub>2</sub>''a'' are in the same integer subdivision of size 1/''M'' (there are only ''M'' such subdivisions between consecutive integers). In particular, we can find ''n''<sub>1</sub>, ''n''<sub>2</sub> such that ''n''<sub>1</sub>''a'' is in {{nowrap|(''p'' + ''k''/''M'', ''p'' + (''k'' + 1)/''M'')}}, and ''n''<sub>2</sub>''a'' is in {{nowrap|(''q'' + ''k''/''M'', ''q'' + (''k'' + 1)/''M'')}}, for some ''p'', ''q'' integers and ''k'' in {{nowrap|{0, 1, ..., ''M'' − 1}}}. We can then easily verify that {{nowrap|(''n''<sub>2</sub> − ''n''<sub>1</sub>)''a''}} is in {{nowrap|(''q'' − ''p'' − 1/''M'', ''q'' − ''p'' + 1/''M'')}}. This implies that {{nowrap|[''na''] < 1/''M'' < ''e''}}, where ''n'' = {{nowrap|''n''<sub>2</sub> − ''n''<sub>1</sub>}} or ''n'' = {{nowrap|''n''<sub>1</sub> − ''n''<sub>2</sub>}}. This shows that 0 is a limit point of {[''na'']}. We can then use this fact to prove the case for ''p'' in <nowiki>(</nowiki>0, 1<nowiki>]</nowiki>: find ''n'' such that {{nowrap|[''na''] < 1/''M'' < ''e''}}; then if {{nowrap|''p'' ∈ (0, 1/''M''}}], we are done. Otherwise ''p'' in {{nowrap|(''j''/''M'', (''j'' + 1)/''M''}}], and by setting ''k'' = sup{{nowrap|{''r'' ∈ ''N'' : ''r''[''na''] < ''j''/''M''}}}, one obtains {{nowrap|{{!}}[(''k'' + 1)''na''] − ''p''{{!}} < 1/''M'' < ''e''}}.
| | ==Bug reporting== |
| | | If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de . |
| == Alternate formulations == | |
| The following are alternate formulations of the pigeonhole principle.
| |
| | |
| #If ''n'' objects are distributed over ''m'' places, and if ''n'' > ''m'', then some place receives at least two objects.<ref name=Herstein64 />
| |
| #(equivalent formulation of 1) If ''n'' objects are distributed over ''n'' places in such a way that no place receives more than one object, then each place receives exactly one object.<ref name=Herstein64 />
| |
| #If ''n'' objects are distributed over ''m'' places, and if ''n'' < ''m'', then some place receives no object.
| |
| #(equivalent formulation of 3) If ''n'' objects are distributed over ''n'' places in such a way that no place receives no object, then each place receives exactly one object.
| |
| | |
| == Generalizations of the pigeonhole principle ==
| |
| A generalized version of this principle states that, if ''n'' discrete objects are to be allocated to ''m'' containers, then at least one container must hold at least <math>\lceil n/m \rceil</math> objects, where <math>\lceil x\rceil</math> is the [[ceiling function]], denoting the smallest integer larger than or equal to ''x''.
| |
| Similarly, at least one container must hold no more than <math>\lfloor n/m \rfloor</math> objects, where <math>\lfloor x \rfloor</math> is the [[floor function]], denoting the largest integer smaller than or equal to ''x''.
| |
| | |
| A probabilistic generalization of the pigeonhole principle states that if ''n'' pigeons are randomly put into ''m'' pigeonholes with uniform probability 1/''m'', then at least one pigeonhole will hold more than one pigeon with probability
| |
| | |
| :<math>1 - \frac{(m)_n}{m^n}, \!</math>
| |
| | |
| where (''m'')<sub>''n''</sub> is the [[falling factorial]] {{nowrap|''m''(''m'' − 1)(''m'' − 2)...(''m'' − ''n'' + 1)}}. For ''n'' = 0 and for ''n'' = 1 (and ''m'' > 0), that probability is zero; in other words, if there is just one pigeon, there cannot be a conflict. For ''n'' > ''m'' (more pigeons than pigeonholes) it is one, in which case it coincides with the ordinary pigeonhole principle. But even if the number of pigeons does not exceed the number of pigeonholes (''n'' ≤ ''m''), due to the random nature of the assignment of pigeons to pigeonholes there is often a substantial chance that clashes will occur. For example, if 2 pigeons are randomly assigned to 4 pigeonholes, there is a 25% chance that at least one pigeonhole will hold more than one pigeon; for 5 pigeons and 10 holes, that probability is 69.76%; and for 10 pigeons and 20 holes it is about 93.45%. If the number of holes stays fixed, there is always a greater probability of a pair when you add more pigeons. This problem is treated at much greater length in the [[birthday paradox]].
| |
| | |
| A further probabilistic generalisation is that when a real-valued [[random variable]] ''X'' has a finite [[mean]] ''E''(''X''), then the probability is nonzero that ''X'' is greater than or equal to ''E''(''X''), and similarly the probability is nonzero that ''X'' is less than or equal to ''E''(''X''). To see that this implies the standard pigeonhole principle, take any fixed arrangement of ''n'' pigeons into ''m'' holes and let ''X'' be the number of pigeons in a hole chosen uniformly at random. The mean of ''X'' is ''n''/''m'', so if there are more pigeons than holes the mean is greater than one. Therefore, ''X'' is sometimes at least 2.
| |
| | |
| == Infinite sets ==
| |
| The pigeonhole principle can be extended to [[infinite set]]s by phrasing it in terms of [[cardinal number]]s: if the cardinality of set A is greater than the cardinality of set B, then there is no injection from A to B. However in this form the principle is [[tautology (logic)|tautological]], since the meaning of the statement that the cardinality of set A is greater than the cardinality of set B is exactly that there is no injective map from A to B. What makes the situation of finite sets interesting is that adding at least one element to a set is sufficient to ensure that the cardinality increases.
| |
| | |
| Another way to phrase the pigeonhole principle is similar to the principle that finite sets are [[Dedekind finite]]: Let A and B be finite sets. If there is a surjection from A to B that is not injective, then no surjection from A to B is injective. In fact no function of any kind from A to B is injective.
| |
| | |
| The above principle is not true for infinite sets: Consider the function on the natural numbers that sends 1 and 2 to 1, 3 and 4 to 2, 5 and 6 to 3... and so on.
| |
| | |
| There is a similar principle for infinite sets: If uncountably many pigeons are stuffed into countably many pigeonholes, there will exist at least one pigeonhole having uncountably many pigeons stuffed into it.
| |
| | |
| This principle is not a generalisation of the pigeonhole principle for finite sets however: It is in general false for finite sets. In technical terms it says that if A and B are finite sets such that any surjective function from A to B is not injective, then there exists an element of b of B such that there exists a bijection between the preimage of b and A. This is a quite different statement, and is absurd for large finite cardinalities.
| |
| | |
| == See also ==
| |
| * [[Combinatorial principles]]
| |
| * [[Combinatorial proof]]
| |
| * [[Dedekind-infinite set]]
| |
| * [[Hilbert's paradox of the Grand Hotel]]
| |
| * [[Multinomial theorem]]
| |
| * [[Pumping lemma for regular languages]]
| |
| * [[Ramsey's theorem]]
| |
| * [[Pochhammer symbol]]
| |
| | |
| ==Notes==
| |
| {{reflist}}
| |
| | |
| == References ==
| |
| * {{citation|first1=Peter|last1=Fletcher|first2=C.Wayne|last2=Patty|title=Foundations of Higher Mathematics|year=1987|publisher=PWS-Kent|isbn=0-87150-164-3}}
| |
| * [[Ralph Grimaldi|Grimaldi, Ralph P]]. ''Discrete and Combinatorial Mathematics: An Applied Introduction''. 4th edn. 1998. ISBN 0-201-19912-2. pp. 244–248.
| |
| * {{ citation | first1 = I. N. | last1 = Herstein | year = 1964 | isbn = 978-1114541016 | title = Topics In Algebra | publisher = [[Blaisdell Publishing Company]] | location = Waltham }}
| |
| * 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.
| |
| | |
| == External links ==
| |
| * {{springer|title=Dirichlet box principle|id=p/d032800}}
| |
| * "[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD09xx/EWD980.html The strange case of The Pigeon-hole Principle]"; [[Edsger Dijkstra]] investigates interpretations and reformulations of the principle.
| |
| * "[http://zimmer.csufresno.edu/~larryc/proofs/proofs.pigeonhole.html The Pigeon Hole Principle]"; Elementary examples of the principle in use by Larry Cusick.
| |
| * "[http://www.cut-the-knot.org/do_you_know/pigeon.shtml Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles]"; basic Pigeonhole Principle analysis and examples by [[Alexander Bogomolny]].
| |
| * "[http://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle 16 fun applications of the pigeonhole principle]"; Interesting facts derived by the principle.
| |
| | |
| {{DEFAULTSORT:Pigeonhole Principle}}
| |
| | |
| [[Category:Combinatorics]]
| |
| [[Category:Theorems in discrete mathematics]]
| |
| [[Category:Mathematical principles]]
| |
| [[Category:Ramsey theory]]
| |
