Fact-checked by Grok 2 weeks ago

Pigeonhole principle

The pigeonhole principle is a fundamental theorem in combinatorics asserting that if n + 1 pigeons are distributed into n pigeonholes, then at least one pigeonhole contains at least two pigeons.^[1] This simple observation, which guarantees the existence of a repetition or collision without specifying its location, serves as a cornerstone for proving non-constructive results across mathematics.^[2] Although commonly attributed to the German mathematician Peter Gustav Lejeune Dirichlet, who formalized and applied it in 1834 to problems in number theory such as Diophantine approximation, the principle has deeper historical roots.^[3] Similar ideas appeared indirectly in Jean Leurechon's 1622 Latin text Récréation mathématique, where combinatorial problems implied the necessity of overlaps in distributions, predating Dirichlet by over two centuries.^[4] Dirichlet's version, often called the "drawer principle" or "box principle" in German contexts, emphasized its utility in proving the existence of integer solutions to equations by considering modular arithmetic and finite possibilities.^[5] A generalized pigeonhole principle extends the basic form: if N objects are placed into k containers, with N > k, then at least one container holds at least ⌈N/k⌉ objects.^[6] This version quantifies the minimum overload and is crucial for more precise bounds in proofs. The principle finds wide application in diverse areas, including number theory for establishing properties of primes and irrationals, graph theory for demonstrating shared vertices or edges, and computer science for analyzing hashing collisions and algorithm limits.^[7] ^[8] Notable examples include proving that among any six people, at least three share the same gender or that in a group of 13 individuals, at least two share the same birth month, illustrating its role in everyday probabilistic reasoning.^[9] In advanced contexts, such as proof complexity and Ramsey theory, the principle underpins studies of unavoidable sets and the inherent limitations of formal proof systems.^[2] ^[10]

Introduction and Statement

Formal Statement

The pigeonhole principle, in its basic finite form, states that if n pigeons are placed into m pigeonholes where n > m, then at least one pigeonhole contains more than one pigeon.^[11] This principle is a fundamental result in combinatorics, asserting the existence of a non-empty intersection in the distribution without specifying which pigeonhole is affected.^[11] The proof proceeds by contradiction. Suppose each of the m pigeonholes contains at most one pigeon; then the total number of pigeons would be at most m. However, since n > m, this assumption leads to a contradiction, implying that at least one pigeonhole must contain at least two pigeons.^[12] A generalized formulation specifies the minimal maximum occupancy: when n pigeons are distributed into m pigeonholes, at least one pigeonhole contains at least \lceil n/m \rceil pigeons, where \lceil \cdot \rceil denotes the ceiling function.^[13] A basic corollary follows: to guarantee that at least one pigeonhole contains at least k+1 pigeons, it suffices to have m k + 1 pigeons, as fewer would allow a distribution with at most k per pigeonhole.^[14]

Intuitive Explanation

The pigeonhole principle gets its name from a vivid analogy: picture pigeons as the items to be distributed and pigeonholes as the limited categories or containers available for them. If more pigeons are placed into the holes than there are holes, then necessarily at least one hole will end up with more than one pigeon, as there are simply not enough holes to give each pigeon its own space.^[15] This metaphor captures the principle's essence—overcrowding forces sharing—because any attempt to assign the excess pigeons will inevitably result in at least one category holding multiple items, no matter how evenly one tries to spread them out. The logic rests on the impossibility of a one-to-one correspondence when items outnumber categories, guaranteeing duplication in the worst case.^[15] A frequent misconception is that the principle implies an even or average distribution across categories; in reality, it provides an ironclad assurance about the unavoidable presence of multiples, without regard to typical or probabilistic outcomes.^[1] To build intuition, simple diagrams showing pigeons crowding into fewer holes than needed can effectively illustrate this inevitability.

History and Etymology

Origins

The pigeonhole principle has roots in early modern mathematics, with an implicit formulation appearing in Jean Leurechon's 1622 Latin text Récréation mathématique. In this recreational mathematics book, combinatorial problems, such as arguing that among a finite number of people, at least two must have the same number of hairs, implied the necessity of overlaps in distributions.^[4] Similar ideas were echoed in subsequent works, including Marin Mersenne's 1625 writings, predating more systematic uses by over two centuries.^[16] The principle saw more explicit development in the 19th century, particularly through Peter Gustav Lejeune Dirichlet's work in number theory. Dirichlet formalized the Schubfachprinzip (drawer principle) around 1834. In 1842, he employed it in his investigations of Diophantine approximation, using it to prove that for any real number \alpha and positive integer Q, there exist integers p and q with $1 \leq q \leq Q such that |\alpha - p/q| < 1/(qQ).^[17]^[16] This application highlighted the principle's utility in guaranteeing the existence of solutions by considering fractional parts distributed into intervals, marking a shift toward systematic use in analytic number theory. Earlier in the century, similar ideas appeared in the works of other mathematicians, such as Augustin-Louis Cauchy, who in 1833 applied a pigeonhole-like argument in his analysis of continuous functions and limits, arguing about the distribution of values to establish properties of convergence without naming the principle explicitly. These instances reflect ad hoc employments in proofs involving distribution and existence. By the late 19th and early 20th centuries, such arguments had coalesced into a widely recognized combinatorial tool, frequently invoked across number theory, analysis, and geometry to resolve problems of inevitability and multiplicity.^[4]

Naming and Early Uses

The term "pigeonhole principle" originates from the analogy to the small compartments, or "pigeonholes," used in post offices for sorting mail; if more letters arrive than there are available slots, at least one slot must hold multiple letters.^[18] This metaphor illustrates the core idea of distributing items into fewer containers than items available, ensuring at least one container receives more than one. The English phrasing evokes the physical act of assigning pigeons to nesting holes, a visual aid that made the concept accessible in recreational and combinatorial contexts.^[19] In German mathematics, the equivalent concept appeared as the Schubfachprinzip (drawer principle), formalized by Peter Gustav Lejeune Dirichlet in 1834 during his lectures on number theory, where it served as a tool for proving the existence of approximations in Diophantine analysis. Dirichlet's formulation emphasized the "drawer" metaphor from office furniture, predating the pigeon imagery but conveying the same inevitability of overcrowding. The principle's early applications in the 19th century focused on infinite series and modular arithmetic, though without the specific English nomenclature.^[16] The English term "pigeonhole principle" was first explicitly used in mathematical literature by Raphael M. Robinson in his 1941 paper "On the Simultaneous Approximation of Two Real Numbers," published in the Bulletin of the American Mathematical Society.^[17] Prior to this formal naming, the principle appeared unnamed in early 20th-century English puzzles and texts, such as Henry Ernest Dudeney's 1917 Amusements in Mathematics, which popularized variants like the sock-picking scenario—where drawing enough socks from a drawer guarantees a matching pair—and the no-three-in-line problem on a chessboard, both relying on the underlying logic of forced duplication.^[20] These recreational examples helped embed the idea in popular culture, bridging abstract combinatorics with everyday intuition. By the 1920s, the principle had spread into formal combinatorics texts in English, notably in Percy Alexander MacMahon's Combinatory Analysis (1915–1916), where it underpinned proofs for plane partitions and symmetric functions, demonstrating its utility in enumerative problems without yet adopting the "pigeonhole" label universally.^[21] This adoption marked the transition from ad hoc puzzle applications to a standard tool in discrete mathematics, influencing subsequent works in set theory and graph theory.^[22]

Basic Examples

Everyday Scenarios

One common everyday illustration of the pigeonhole principle involves selecting socks from a drawer in the dark. Suppose there are three pairs of socks, each pair a different color: red, blue, and white, making six socks in total but only three colors. To guarantee obtaining at least one matching pair of the same color, one must draw four socks. With three socks, it is possible to have one of each color, but the fourth sock must match one of the existing colors by the principle, as there are only three possible colors (pigeonholes) for four socks (pigeons).^[23] Another relatable scenario concerns hair colors among a group of people. Consider a room with 100 individuals and only 99 possible distinct hair colors. The pigeonhole principle ensures that at least two people must share the same hair color, since distributing 100 people (pigeons) into 99 hair colors (pigeonholes) requires at least one color to be assigned to two or more individuals. This example highlights how the principle applies even to natural variations in appearance, assuming no one is bald or outside the color categories considered. A simple social example arises in determining shared characteristics among a small group, such as gender. In any gathering of three people, at least two must be of the same gender. Here, the two possible genders serve as the pigeonholes, and three people as the pigeons; it is impossible to assign three individuals to two categories without at least one category containing two. This basic case demonstrates the principle's utility in everyday observations of group compositions.

Classic Mathematical Illustrations

The birthday problem provides a classic probabilistic illustration of the pigeonhole principle. Consider a group of randomly selected people, assuming birthdays are equally likely on any of the 365 days and ignoring leap years and other complications. The probability that at least two share the same birthday exceeds 50% when the group size reaches 23. This result arises from calculating the complementary probability that all birthdays are distinct, which is approximately P = \frac{365!}{(365-22)! \cdot 365^{22}} \approx 0.4927, so the desired probability is about 0.5073. The pigeonhole principle offers a deterministic lower bound for certainty: with 366 people (pigeons) and only 365 possible birthdays (pigeonholes), at least one pigeonhole must contain at least two pigeons, guaranteeing a shared birthday. Another well-known combinatorial puzzle involves subset sums from the set S = \{1, 2, \dots, 2n-1\}. This set has $2n-1 elements, yielding $2^{2n-1} possible subsets, including the empty set. The sum of any subset ranges from 0 (empty subset) to the total sum \sum_{k=1}^{2n-1} k = n(2n-1), giving at most n(2n-1) + 1 distinct possible sums. For n \geq 2, $2^{2n-1} > n(2n-1) + 1; for example, when n=2, there are 8 subsets but only 7 possible sums (0 through 6). Thus, by the pigeonhole principle, at least two distinct subsets must have the same sum. A straightforward variant of the hat check problem demonstrates the basic form of the principle. Suppose there are n+1 hats, each colored with one of n possible colors. The n+1 hats serve as pigeons and the n colors as pigeonholes. By the pigeonhole principle, at least one color must be shared by at least two hats, guaranteeing a duplicate. In graph theory, the pigeonhole principle highlights degree properties in complete graphs. Consider the complete graph K_{2m+1} on $2m+1 vertices, where every pair of vertices is connected by an edge. Each vertex has degree $2m. With $2m+1 vertices forcing \binom{2m+1}{2} = m(2m+1) edges, the average degree is $2m, and in this maximal case, all vertices achieve exactly this degree, as confirmed by the handshaking lemma.

Advanced Formulations

Strong Form

The strong form of the pigeonhole principle, also known as the generalized pigeonhole principle, provides a quantitative bound on the distribution: if n pigeons are placed into m holes where n \geq m \geq 1, then at least one hole contains at least \lceil n/m \rceil pigeons.^[24] This strengthens the basic principle by specifying the minimal guaranteed occupancy in the fullest hole, rather than merely asserting the existence of multiplicity. A proof can be given using the method of contradiction. Suppose, for the sake of contradiction, that every hole contains at most \lceil n/m \rceil - 1 pigeons. Note that \lceil n/m \rceil - 1 = \lfloor (n-1)/m \rfloor, so the total number of pigeons would be at most m \cdot \lfloor (n-1)/m \rfloor \leq n-1 < n. This contradicts the assumption that there are n pigeons, so at least one hole must contain at least \lceil n/m \rceil pigeons.^[25] Alternatively, an averaging argument establishes the result. The average number of pigeons per hole is n/m. Since the number of pigeons in each hole is a non-negative integer, the maximum occupancy must be at least the ceiling of this average, i.e., at least \lceil n/m \rceil. For example, with 17 pigeons and 5 holes, \lceil 17/5 \rceil = \lceil 3.4 \rceil = 4, so at least one hole contains at least 4 pigeons.^[24] The standard pigeonhole principle is a special case of this form, corresponding to n = m+1, where \lceil (m+1)/m \rceil = 2.^[25]

Alternative Statements

The pigeonhole principle admits several equivalent formulations that highlight its logical and set-theoretic underpinnings. One logical expression states that if n > m, where n and m are positive integers, then there does not exist a bijection between a set of n elements and a set of m elements.^[2] This captures the principle's essence by emphasizing the impossibility of a one-to-one correspondence when the domain exceeds the codomain in cardinality. In set-theoretic terms, the principle asserts that for finite sets A and B with |A| > |B|, any function f: A \to B is not injective.^[26] Equivalently, under these conditions, f cannot be both surjective and injective, implying that at least one element in B has multiple preimages in A.^[27] The contrapositive provides another viewpoint: if every pigeonhole contains at most one pigeon, then the total number of pigeons does not exceed the number of pigeonholes.^[28] This form, which follows directly from the standard statement, is often used in proofs to assume injectivity and derive a bound on set sizes.^[8]

Generalizations

Finite Case Extensions

One notable extension of the pigeonhole principle in the finite case is Dirichlet's box principle, which applies the principle to fractional parts for Diophantine approximations. Consider a real number α and an integer Q ≥ 1. The Q+1 fractional parts {0·α}, {1·α}, ..., {Q·α} lie in the interval [0,1) and can be divided into Q subintervals of length 1/Q each. By the pigeonhole principle, at least two fractional parts {j·α} and {i·α} (with 0 ≤ i < j ≤ Q) fall into the same subinterval, so their difference | (j - i) α - p | < 1/Q for some integer p, where q = j - i ≤ Q. This yields a rational approximation p/q to α satisfying |α - p/q| < 1/(q Q) ≤ 1/q^2, demonstrating a finite bound on the quality of approximation using a finite number of "boxes."^[29] Another significant finite extension is the Erdős–Ginzburg–Ziv theorem, which guarantees a zero-sum subset in sequences of integers. The theorem states that in any sequence of 2n-1 integers, there exists a subsequence of exactly n elements whose sum is divisible by n. The proof relies on the pigeonhole principle applied to partial sums: let S = (a_1, ..., a_{2n-1}) be the sequence, and define the partial sums s_k = a_1 + ... + a_k modulo n for k = 1 to 2n-1. If any s_k ≡ 0 \pmod{n}, then the first k elements sum to a multiple of n (and if k = n, it is the desired subsequence; otherwise, adjust by removing cycles if needed). Otherwise, the 2n-1 nonzero residues modulo n (which has n-1 possible nonzero values) must repeat by the pigeonhole principle, so s_j ≡ s_i \pmod{n} for some 1 ≤ i < j ≤ 2n-1, implying that the sum a_{i+1} + ... + a_j is divisible by n (with j - i ≤ n-1, but induction or refinement ensures length n). This theorem, proved in 1961, generalizes the basic pigeonhole principle to additive structures in finite abelian groups. In multipartite graph theory, the pigeonhole principle extends to force high densities in substructures. For instance, in a tripartite graph with vertex parts X, Y, Z and sufficiently many edges, the principle applied to edge distributions across the three bipartite components (X-Y, Y-Z, Z-X) ensures that at least one of the three bipartite subgraphs contains at least one-third of the total number of edges. If the part sizes are equal, at least one has edge density at least the average density across the three. More refined variants, such as in quasirandom hypergraph embeddings, use the principle on colored edges in tripartite settings to guarantee a monochromatic or dense subconfiguration exceeding uniform random expectations. Weighted variants of the pigeonhole principle account for capacities or masses assigned to pigeons or holes, generalizing the uniform case. A standard formulation states that if a finite set of pigeons with positive weights w_1, ..., w_m is distributed into n holes such that the total weight exceeds n b (where b is a threshold), then at least one hole receives total weight greater than b. This follows by contradiction: if all holes have weight ≤ b, the total would be ≤ n b. For non-uniform hole capacities c_1, ..., c_n, if the total pigeon weight exceeds ∑ c_i, then some hole exceeds its capacity. These extensions appear in optimization and proof complexity, where weights represent multiplicities or costs in finite encodings.

Infinite Sets

The pigeonhole principle extends to infinite sets by considering cardinalities rather than finite counts, where the "pigeons" form a set A and the "holes" form a set B, with a function f: A \to B assigning elements to subsets (fibers f^{-1}(b) for b \in B).^[30] In the countable infinite case, if a countable infinite set of pigeons is placed into finitely many holes, then at least one hole must contain infinitely many pigeons; formally, if A is countably infinite and B is finite with |B| = n < \aleph_0, any function f: A \to B has some b \in B such that f^{-1}(b) is infinite.^[31] This follows from the finite pigeonhole principle applied to initial finite subsets of A, with the infinitude ensured by the unending supply of pigeons beyond any finite stage. For arbitrary infinite cardinals, the principle manifests in cardinal arithmetic: if |A| > |B|, there is no injection from A to B, meaning any function f: A \to B cannot be one-to-one and thus some fiber f^{-1}(b) must have cardinality at least as large as the difference in sizes.^[31] Equivalently, if there exists a surjection from A onto B but no injection from A to B, the principle implies non-injectivity for any attempted mapping, highlighting that larger infinities cannot be squeezed into smaller ones without overlap.^[30] This generalization relies on the well-ordering principle, equivalent to the axiom of choice (AC), to compare cardinals precisely.^[32] Without the axiom of choice, stronger forms of the infinite pigeonhole principle may fail, but weaker versions hold using finite support or dependent choice; for instance, restricted pigeonhole principles for sequences of finite sets can be proven in ZF set theory alone, ensuring that infinite subsets exist in certain partitions without invoking full AC. These limited principles suffice for countable cases or well-ordered cardinals but do not guarantee selections across arbitrary infinite families. Hilbert's hotel paradox provides an intuitive example of how infinite sets defy finite intuitions in the context of cardinalities. A fully occupied hotel with countably infinite rooms (one guest per room) can accommodate additional guests—finitely many or even countably infinite—by shifting existing guests to higher-numbered rooms, revealing that countable infinities allow "room" despite fullness, as no single room ends up with more than one guest, but the mapping demonstrates equipotency.^[33] This paradox, popularized by David Hilbert in the early 20th century, underscores how infinite sets behave differently from finite ones, with the reassignment functioning as a bijection between the original and expanded guest sets.^[33]

Applications

Combinatorics and Number Theory

The pigeonhole principle serves as a foundational tool in combinatorics and number theory for establishing the existence of certain structures in colorings or partitions of discrete sets, often without constructing them explicitly. In these fields, it underpins proofs that guarantee monochromatic solutions to equations or configurations in sufficiently large finite or infinite sets, highlighting unavoidable patterns in combinatorial arrangements.^[34] In Ramsey theory, the pigeonhole principle is instrumental in forcing the emergence of monochromatic cliques within edge colorings of complete graphs. For instance, in the proof of Ramsey's theorem for graphs, when coloring the edges of a complete graph K_s with r colors, the principle is applied repeatedly to degrees or neighborhoods: if a vertex has degree greater than the Ramsey number minus one in a two-color case, then by pigeonholing the edges into colors, at least one color class yields a monochromatic clique of the desired size. This iterative application demonstrates how the principle generalizes to ensure ordered structures in random-like colorings, with Ramsey numbers R(k,l) bounding the minimal vertices needed for monochromatic K_k or K_l.^[34]^[35] Schur's theorem exemplifies the principle's role in additive combinatorics: for any finite coloring of the positive integers with r colors, there exist monochromatic x, y, z such that x + y = z, provided the set is large enough relative to r. The proof proceeds by considering the finite version, where for a set $$ colored with r colors, if n exceeds a Schur number S(r), then by pigeonholing sums of pairs within color classes, a monochromatic solution is forced; the infinite case follows by compactness or repeated application. This result, established by Issai Schur in 1916, quantifies the threshold via Schur numbers, such as S(2) = 5 and S(3) = 13, illustrating the principle's power in bounding additive dependencies.^[36]^[37] Van der Waerden's theorem extends this to arithmetic progressions: for positive integers k and r, there exists W(k,r) such that any r-coloring of [W(k,r)] contains a monochromatic arithmetic progression of length k. The original 1927 proof by Bartel van der Waerden uses the pigeonhole principle inductively: assuming the result for shorter progressions, one colors blocks of size W(k-1, t) and applies the principle to identify repeated color patterns, ensuring a progression in one color by embedding smaller ones. This yields finite bounds like W(3,2) = 9, emphasizing existence in colorings without specifying locations.^[38]^[39] In number theory, the pigeonhole principle, often termed Dirichlet's box principle, contributes to partial proofs of infinitely many primes in arithmetic progressions. Dirichlet's 1837 theorem asserts that for coprime a, d > 0, there are infinitely many primes p \equiv a \pmod{d}, but elementary approaches using the principle demonstrate this for specific cases, such as progressions like $4k+3. One such Euclidean-style proof considers products of primes in residue classes modulo d; by pigeonholing the prime factors of numbers up to a bound exceeding the number of classes, a contradiction arises if only finitely many primes occupy the progression, forcing an additional prime therein. These methods provide intuitive existence arguments, though full generality requires analytic tools.^[40]^[41]

Computer Science and Algorithms

In hashing, the pigeonhole principle guarantees collisions when the number of keys exceeds the number of available buckets. Specifically, inserting n distinct keys into a hash table with m buckets ensures at least one collision if n > m, as each key must map to one of the m positions.^[42] This fundamental limit influences hash table design, where the load factor \alpha = n/m is typically maintained below 0.7 to balance space efficiency and performance; higher loads increase chain lengths in separate chaining or clustering in open addressing, degrading average insertion and lookup times from O(1) toward O(n) in the worst case.^[43] Even with universal hashing, the principle underscores that collisions are unavoidable for large n, prompting techniques like rehashing to mitigate their impact. The pigeonhole principle establishes information-theoretic lower bounds for comparison-based sorting algorithms. With n! possible permutations of n elements, a sorting algorithm's decision tree—where each internal node represents a comparison with two branches—must have at least n! leaves to distinguish all orderings. Since a tree of height h has at most $2^h leaves, h \geq \log_2(n!), and by Stirling's approximation, \log_2(n!) \approx n \log_2 n - n, yielding an \Omega(n \log n) bound on the number of comparisons required in the worst case.^[44] This bound holds for algorithms like mergesort and heapsort, which achieve \Theta(n \log n) time, confirming optimality among comparison sorts.^[45] In probabilistic data structures like Bloom filters, the pigeonhole principle explains the inevitability of false positives due to bit overlaps in a fixed-size array. A Bloom filter uses an array of m bits and k independent hash functions to represent a set: insertion sets the k hashed bits to 1, while membership queries check if all k bits are 1, accepting false positives (but never false negatives) when non-members hash to already-set bits from other elements. With more elements than bits, the principle guarantees shared positions, leading to a false positive rate of approximately (1 - e^{-kn/m})^k, minimized at k = (m/n) \ln 2 for a rate of about $0.6185^{m/n}. This trade-off enables space savings up to 100x over exact sets in applications like spell checkers and network packet filtering, where low error rates suffice.^[46] Cryptographic applications leverage the pigeonhole principle in birthday attacks to exploit collisions in hash functions more efficiently than exhaustive search. For an n-bit hash output space of $2^n possible values, evaluating roughly $1.17 \times 2^{n/2} inputs yields a collision with high probability, as the "birthdays" (hash values) must repeat among the pigeonholes by the generalized birthday paradox; a strict guarantee occurs at $2^{n/2} + 1 inputs.^[47] This reduces the attack complexity from O(2^n) to O(2^{n/2}), necessitating at least 256-bit hashes like SHA-256 for 128-bit security against practical collisions, influencing standards in digital signatures and blockchain.

Physics and Other Fields

The pigeonhole principle manifests in quantum mechanics through the quantum pigeonhole effect, where three quantum particles distributed into two quantum states can result in no two particles sharing the same state, violating the classical principle due to quantum superposition and interference. This effect highlights fundamental quantum correlations, such as the monogamy of entanglement, which limits how entanglement can be distributed among multiple systems, akin to bounding shared "pigeonholes" in quantum information sharing.^[48] In quantum error correction, particularly within stabilizer codes, the pigeonhole principle ensures unique error identification in decoding procedures. For high-threshold fault-tolerant quantum memories, it guarantees that syndrome measurements distinguish errors unambiguously, as multiple error patterns mapping to the same syndrome would violate the code's minimum distance property via pigeonhole on the error space. Recent advancements in 2024 have leveraged this in constructing low-overhead codes for scalable quantum computing.^[49]^[50] In biology, the pigeonhole principle elucidates genetic diversity constraints in populations with limited alleles, ensuring that beyond a certain population size, individuals must share alleles, thereby promoting phenotypic similarities or linkage disequilibria. This is evident in population genetics models where sampling more loci than available chromosomal positions forces dependencies among markers. In cancer evolution, it governs subclonal reconstruction by enforcing that the cancer cell fraction of descendant clones cannot sum to more than the ancestor's fraction, as otherwise the total would exceed the population limit, enabling inference of phylogenetic trees from sequencing data.^[51]^[52]^[53] In economics, the principle supports analysis of resource allocation in competitive markets and games, proving equilibrium existence by demonstrating that with more agents than resources, at least one resource must be over-allocated, leading to saturation or inefficiency. This application informs models of market oversupply, where sector capacities act as pigeonholes, guaranteeing excess in high-demand areas under constrained total supply.^[54]

References

[1]
The strange case of The Pigeon-hole Principle (EWD 980)
The Pigeon-hole Principle states: if more than n objects are distributed into n compartments, some compartment receives more than one object.
[2]
[PDF] Proof Complexity of Pigeonhole Principles - Full-Time Faculty
The pigeonhole principle asserts that there is no injective mapping from m pigeons to n holes as long as m>n. It is amazingly simple, expresses one of the most ...
[3]
[PDF] Historical Perspectives - Computer Science
Pigeon-Hole Principle. • J. Dirichlet (1834). • “Drawer principle”. • “Shelf Principle”. • “Box principle”. Theorem (pigeon-hole): There is no injective (1-to-1) ...
[4]
The Pigeonhole Principle, Two Centuries Before Dirichlet
Aug 7, 2013 · The Pigeonhole Principle, Two Centuries Before Dirichlet. Years Ago; David E. Rowe, Editor; Published: 07 August 2013. Volume 36, pages 27–29 ...
[5]
[PDF] On a theorem of Davenport and Schmidt
Jul 13, 2020 · In 1842 Dirichlet [13] applied the pigeonhole principle to give good approximations of real numbers by rationals. One form of his theorem in ...Missing: history | Show results with:history
[6]
[PDF] The Pigeon-hole Principle - University of Utah Math Dept.
It says the following: if you place n+1 pigeons in n holes, there the must exist at least one hole with at least two pigeons in it. This can be generalized as ...<|control11|><|separator|>
[7]
Pigeonhole Principle: Real Life Applications and Mathematical ...
This research paper investigates the Pigeonhole Principle, exploring its historical context, basic theorems, and various real-life applications.
[8]
[PDF] Pigeonhole Principle, Inclusion-Exclusion: Chapter 14.8
Since jAj > 2jBj, the Generalized Pigeonhole Principle implies that at least three people have exactly the same number of hairs. We don't know who they are, but ...
[9]
[PDF] An Introduction to Combinatorics and Graph Theory - Whitman College
Here is a simple application of the Pigeonhole Principle that leads to many interesting questions. EXAMPLE 1.6.8 Suppose 6 people are gathered together ...
[10]
[PDF] Introduction to Ramsey Theory - Simon Fraser University
Ramsey theory is the mathematics of coloring, or the study of the preservation of properties under set partitions, asking if order can always be found in chaos.
[11]
[PDF] Pigeonhole Principle and the Probabilistic Method - MIT Mathematics
Feb 20, 2015 · A basic version states: If m objects (or pigeons) are put in n boxes (or pigeonholes) and n<m, then at least one box contains more than one ...
[12]
[PDF] 1 Pigeonhole Principle
Jun 22, 2012 · The Pigeonhole Principle states that if you have n+1 objects and place them into n bins, then at least one bin will have at least 2 objects.Missing: mathematics | Show results with:mathematics
[13]
[PDF] Pigeonhole Principle and Recurrence Relations - CMU Math
Mar 28, 2021 · The generalized principle says if N objects are placed into k boxes, then at least one box contains at least the ceiling of N/k objects.
[14]
[PDF] Pigeonhole Principle
The Pigeonhole Principle: If n + 1 or more objects are placed in n boxes, then at least one box contains more than one object. If kn + 1 or more objects are ...
[15]
Dirichlet's Box Principle -- from Wolfram MathWorld
A.k.a. the pigeonhole principle. Given n boxes and m>n objects, at least one box must contain more than one object. This statement has important ...
[16]
[PDF] The infinitude of the primes - Keith Conrad
Euclid's proof. Euclid's proof of the infinitude of the primes uses the fact that all integers greater than. 1 have a prime factor, so let's discuss that ...Missing: pigeonhole | Show results with:pigeonhole
[17]
Earliest Known Uses of Some of the Words of Mathematics (P)
Aug 7, 2018 · PIGEONHOLE PRINCIPLE. The principle itself is attributed to Dirichlet in 1834, although he apparently used the term Schubfachprinzip.
[18]
(PDF) The Pigeonhole Principle, Two Centuries Before Dirichlet
Aug 5, 2025 · this is known as Dirichlet's box principle, Dirichlet's drawer principle, or the pigeonhole principle, after peter Gustav Lejeune Dirichlet who ...
[19]
Pigeon-hole - Etymology, Origin & Meaning
"Pigeonhole" originates from 1570s, meaning a small recess for pigeons, evolving to compartments in desks and figuratively to classify or set aside ideas.Missing: principle | Show results with:principle
[20]
pigeonhole principle - Wiktionary, the free dictionary
Etymology. From the commonly used expository example that if n+1 pigeons are placed in n pigeonholes, at least one pigeonhole must contain two (or more) ...
[21]
Amusements in mathematics : Dudeney, Henry Ernest, 1857-1930
Jun 8, 2010 · Amusements in mathematics ; Publication date: 1917 ; Topics: Mathematical recreations, Puzzles ; Publisher: London, New York, Nelson ; Collection ...
[22]
Combinatory analysis : MacMahon, Percy Alexander, 1854-1929
Feb 29, 2008 · Publication date: 1915-16 ; Topics: Combinations, Number theory, Partitions (Mathematics), Permutations ; Publisher: Cambridge University Press.Missing: work pigeonhole
[23]
[PDF] A Combinatorial Miscellany 1 Introduction. - MIT Mathematics
Aug 2, 1999 · A highlight of MacMahon's work ... The hard part in applying the pigeonhole principle is deciding what are the pigeons and what are the ...
[24]
Pigeonhole Principle | Brilliant Math & Science Wiki
If there are n n n pigeons, then it is possible for all of the pigeons to rest happily in separate pigeonholes.
[25]
[PDF] Discrete Structures - Reed College
Pigeonhole principle. If n + 1 objects (pigeons, perhaps) are placed in n ... has hair color H2. Similarly, B has hair color H1. Now for the.
[26]
[PDF] The igeonhole rinciple The Pigeonhole Principle states that if n + 1 ...
Here are a couple more examples of the Pigeonhole Principle. Convince ... Among any three people, you can find two that are of the same gender. Among ...
[27]
[PDF] No More Counting Please 1.3.1 Binomial Theorem
More generally, if there are n pigeons we want to put into k pigeonholes, then at least one pigeonhole must contain at least Ln/kn pigeons.
[28]
[PDF] Pigeonhole Principle - MIT OpenCourseWare
Sep 2, 2013 · Then, if every pigeon is in a hole, some hole must contain at least two pigeons. The pigeonhole principle is extremely useful in mathematics: we ...
[29]
[PDF] The Pigeonhole Principle - HKUST Math Department
The abstract formulation of the three principles: Let X and Y be finite sets and let f : X −→ Y be a function. • If X has more elements than Y , then f is ...Missing: theoretic | Show results with:theoretic
[30]
7.3 The pigeonhole principle
We can come up with stronger forms of the pigeonhole principle by considering pigeonholes with capacities. Suppose we have six pigeonholes in a desk, each of ...
[31]
[PDF] The pigeonhole principle If k pigeons are put in m<k holes, there is a ...
If k pigeons are put in m<k holes, there is a hole with more than one pigeon. This assertion is known as the Dirichlet or pigeonhole principle.
[32]
[PDF] 8. Dirichlet's Theorem and Farey Fractions
There is a very simple, and useful, theorem due to Dirichlet which tells us how well a real number can be approximated by a rational number a/q in terms of the.
[33]
[PDF] Embedding tetrahedra into quasirandom hypergraphs
density ... tripartite graph P “ pX Y¨ Y Y¨ Z, Eq we denote ... possible colours, the pigeonhole principle tells us that there exist two distinct integers i3.
[34]
[PDF] A Generalization of the Pigeonhole Principle
Apr 21, 2015 · The goal of this short note is to prove the following theorem which is a generalization of the generalized pigeonhole principle. Theorem 1 ...
[35]
HowToCount
The Pigeonhole Principle generalizes in an obvious way to functions with larger domains; if f:A→B, then there is some x in B such that |f-1(x)| ≥ |A|/|B|. 2.4.
[36]
Cardinality – Portfolio for Bachelor of Science in Mathematics
If the number of pigeons is greater than the number of pigeonholes, then at least one pigeonhole will contain more than one pigeon. Thus, there is not a one-to ...
[37]
[PDF] Contents 4 Cardinality and Countability - Evan Dummit
◦ A fourth equivalent to the axiom of choice is called the well-ordering principle ... by the infinite version of the pigeonhole principle, some residue class ...
[38]
[PDF] The True (?) Story of Hilbert's Infinite Hotel - arXiv
The paper outlines the origin and early history of Hilbert's hotel paradox. At the same time it retracts the author's earlier conclusion that the paradox was ...
[39]
[PDF] Pigeonhole Principle and Ramsey Theory
The familiar statement is that if we have n pigeonholes and more than n pigeons, then there must be a pigeonhole with more than one pigeon.1. More formally, a ...<|separator|>
[40]
[PDF] Ramsey Theory on the Integers
If more than n pigeons are put into n pigeonholes, then some pigeon- hole must contain at least two pigeons. We now present the pigeonhole principle using ...
[41]
4.2 Schur's Theorem
Schur's Theorem: If the set of positive integers N N is finitely coloured then there exist x,y,z x , y , z having the same colour such that x+y=z.
[42]
[PDF] Introduction. Pigeon-hole principle.
iEI. •. Page 9. Generalization of Schur's theorem: x+y-Z=0 →→ x+y-2Z = 0 ? Theorem ( van der Waerden, 1927). For any C. l. = W = wcc.l) ...
[43]
[PDF] Van der Waerden's Theorem
By the pigeonhole principle, W(2,r) = r + 1 for all r. Next, suppose we know that W(k − 1,t) is finite for all t. Our aim is to show that, for a fixed r, W ...
[44]
[PDF] Van Der Waerden's Theorem
We present the original proof of van der Waerden's Theorem. Our treatment is ... This is by the Pigeonhole Principle which we will be using over and ...
[45]
[PDF] Euclidean proofs of Dirichlet's theorem - Keith Conrad
By the pigeonhole principle, at least one such irreducible factor g must have ... Lin, Infinitely many primes in the arithmetic progression kn − 1, Amer.
[46]
What Dirichlet Had to Do with the Pigeonhole Principle - Samin Riasat
Mar 9, 2013 · Suppose you have six pigeons. You want to put them into five holes. Then at least one of the holes must contain more than one pigeon.
[47]
[PDF] HASH FUNCTIONS
... pigeonhole principle tells us that there must exist a collision for h. Mihir Bellare. UCSD. 3. Page 4. Collision resistance (CR). Definition: A collision for a ...
[48]
[PDF] Hash functions
If |D| > 2n then the pigeonhole principle tells us that there must exist a collision for h. We want that even though collisions exist, they are hard to find. We ...
[49]
[PDF] 4 - The Pigeon Hole Principle and Complexity - William T. Trotter
Nov 14, 2017 · Now you have all the information and can easily assemble the linear order L with these answers. Page 21. Lower Bound on Sorting. Theorem In ...
[50]
[PDF] How to sort? 1 Sorting Algorithms
We can find a lower bound by using the pigeonhole principle: the number of possible outcomes should be at least as large as the number of possible answers ...
[51]
[PDF] A New Analysis of the False-Positive Rate of a Bloom Filter
The probability of a false positive – or false positive rate – of a Bloom filter is a function of the randomness of the values generated by the hash functions ...
[52]
[PDF] Hash functions: Theory, attacks, and applications - Microsoft
Nov 14, 2005 · Table 1: Complexity of generic attacks on different properties of hash functions. H A naıve implementation of the birthday attack would store 2n ...
[53]
Quantum violation of the pigeonhole principle and the nature of ...
The pigeonhole principle: “If you put three pigeons in two pigeonholes, at least two of the pigeons end up in the same hole,” is an obvious yet fundamental ...
[54]
https://link.springer.com/article/10.1007/s10107-020-01604-z
[55]
High-threshold and low-overhead fault-tolerant quantum memory
Mar 27, 2024 · These are stabilizer codes of the Calderbank–Shor–Steane ... Because of (2) and the pigeonhole principle, this choice of (a, b) is unique.
[56]
[PDF] High-threshold and low-overhead fault-tolerant quantum memory
Feb 21, 2024 · These are stabilizer codes of CSS-type [44, 45] that can ... Because of (ii) and the pigeonhole principle, this choice of (a, b) is unique.
[57]
SOME STATISTICAL ISSUES IN POPULATION GENETICS KHANG ...
In fact, by the pigeonhole principle, at least one pair of markers must be dependent (located on the same chromosome) when the number of loci sampled ...
[58]
PhyloWGS: Reconstructing subclonal composition and evolution ...
Feb 13, 2015 · Note that if the ISA is valid, by the pigeonhole principle, weak parsimony is guaranteed to be valid whenever the population frequency of the ...
[59]
Principles of Reconstructing the Subclonal Architecture of Cancers
The pigeonhole principle determines that as 100% + 80% > 100%, the 80% cluster must represent a cellular population that is a descendant of the 100% population.
[60]
Equilibrium computation in resource allocation games
Feb 17, 2021 · By using the pigeonhole principle on the number of resources f \in E{\setminus }\{e_1\}, there exists an f \in E{\setminus }\{e_1\} such that: \ ...Missing: saturation | Show results with:saturation