Pigeonhole principle

[1] 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 counting argument, can be used to demonstrate possibly unexpected results.

For example, given that the 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.

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".

Advanced mathematical proofs like Siegel's lemma build upon this more general concept.

The strict original meaning of these terms corresponds to the English drawer, that is, an open-topped box that can be slid in and out of the cabinet that contains it.

These terms morphed to pigeonhole in the sense of a small open space in a desk, cabinet, or wall for keeping letters or papers, metaphorically rooted in structures that house pigeons.

Because furniture with pigeonholes is commonly used for storing or sorting things into many categories (such as letters in a post office or room keys in a hotel), the translation pigeonhole may be a better rendering of Dirichlet's original "drawer".

That understanding of the term pigeonhole, referring to some furniture features, is fading—especially among those who do not speak English natively but as a lingua franca in the scientific world—in favor of the more pictorial interpretation, literally involving pigeons and holes.

[5] Besides the original terms "Schubfachprinzip" in German[6] and "Principe des tiroirs" in French,[7] other literal translations are still in use in Arabic ("مبدأ برج الحمام"), Bulgarian ("принцип на чекмеджетата"), Chinese ("抽屉原理"), Danish ("Skuffeprincippet"), Dutch ("ladenprincipe"), Hungarian ("skatulyaelv"), Italian ("principio dei cassetti"), Japanese ("引き出し論法"), Persian ("اصل لانه کبوتری"), Polish ("zasada szufladkowa"), Portuguese ("Princípio das Gavetas"), Swedish ("Lådprincipen"), Turkish ("çekmece ilkesi"), and Vietnamese ("nguyên lý hộp").

What is the minimum number of pulled socks required to guarantee a pair of the same color?

This hand-shaking example is equivalent to the statement that in any graph with more than one vertex, there is at least one pair of vertices that share the same degree.

[citation needed] One can demonstrate there must be at least two people in London with the same number of hairs on their heads as follows.

[12] It seems that the question whether there were any two persons in the World that have an equal number of hairs on their head?

[13][14] 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:[2] "It is necessary that two men have the same number of hairs, écus, or other things, as each other.

"[15] 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.

[16] Hashing in computer science is the process of mapping an arbitrarily large set of data n to m fixed-size values.

A notable problem in mathematical analysis is, for a fixed irrational number a, to show that the set ⁠

In the proof of the pumping lemma for regular languages, a version that mixes finite and infinite sets is used: If infinitely many objects are placed into finitely many boxes, then two objects share a box.

[21] The simple form is obtained from this by taking q1 = q2 = ... = qn = 2, which gives n + 1 objects.

Taking q1 = q2 = ... = qn = r gives the more quantified version of the principle, namely: Let n and r be positive integers.

is the ceiling function, denoting the smallest integer larger than or equal to x.

is the floor function, denoting the largest integer smaller than or equal to x.

If the number of holes stays fixed, there is always a greater probability of a pair when you add more pigeons.

However, adding at least one element to a finite set is sufficient to ensure that the cardinality increases.

This 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.

Yakir Aharonov et al. presented arguments that quantum mechanics may violate the pigeonhole principle, and proposed interferometric experiments to test the pigeonhole principle in quantum mechanics.

[24][25] In a January 2015 arXiv preprint, researchers Alastair Rae and Ted Forgan at the University of Birmingham performed a theoretical wave function analysis, employing the standard pigeonhole principle, on the flight of electrons at various energies through an interferometer.

If the electrons had no interaction strength at all, they would each produce a single, perfectly circular peak.

If the interaction strength was fairly low, as would be the case in many real experiments, the deviation from a zero-interaction pattern would be nearly indiscernible, much smaller than the lattice spacing of atoms in solids, such as the detectors used for observing these patterns.