Pigeonhole principle

An image of 10 pigeons and 9 holes. — 10 pigeons and 9 holes.^[1]

The pigeonhole principle is the idea that if you have more things than places to put them, at least one of the places will have to hold more than one thing. While this statement seems obvious, it can be used in surprisingly clever ways.

In any room with $367$ people, at least one pair are guaranteed to share the same birthday. This is because there are only $366$ different birthdays to choose from (including February $29$).

By that same logic, at least one pair of people in London share the exact same number of hairs on their heads since the population of London $(8,800,000)$ is far greater than the maximum number of hairs one can have on their head $(1,000,000).$

Here is a more mathematical description of the pigeonhole principle:

Let $X$ and $Y$ be the domain and target of a function $f: X \rightarrow Y.$ If $|X| \geq n + 1$ and $|Y| \leq n$ for some $n \in \mathbb{Z}^+$: $$f \text{ is not injective}$$ In other words, $f$ assigns at least $2$ elements of $X$ to the same element in $Y.$

⚠ Envision the function $f$ as mapping pigeons (elements of the domain $X$) to holes (elements of the target $Y$).

If your drawer contains a disorganized mix of black, red, and yellow socks, how many socks do you have to pull out at random to be guaranteed a matching pair? By the pigeonhole principle, with $3$ varieties of socks, once you pull out $4$, there will definitely be a pair of socks whose colors match.

Contents

Generalized pigeonhole principle

There is a generalized form of the pigeonhole principle which does not require the number of elements in the domain to exceed the number of elements in the target:

Let $X$ and $Y$ be the domain and target of a function $f: X \rightarrow Y.$ If $|X| \geq n$ and $|Y| = k$ for some $n, k \in \mathbb{Z}^+$, then there exists some $y \in Y$ that is mapped to by at least $\lceil {\frac{n}{k}} \rceil$ elements in $X.$

Let's return to the socks in the drawer problem, where there's black, red, and yellow socks. This time, you'd like to find out how many socks you need to pull out to be guaranteed $4$ matching socks. There are $k = 3$ colors of socks. To have $4$ matching socks, you need $1$ color to be mapped to by at least $4 = \lceil {\frac{n}{k}} \rceil = \lceil {\frac{n}{3}} \rceil$ socks. Looking at this equation, $10$ is the smallest integer for which $\lceil {\frac{n}{3}} \rceil = 4$, so $10$ socks must be pulled out to guarantee $4$ of them match. As you can see, the generalized pigeonhole principle allows you to count how many socks you need to pull out before you are guaranteed any number of matching socks, not just $2.$

The converse of the generalized pigeonhole principle can also prove to be useful:

Let $X$ and $Y$ be the domain and target of a function $f: X \rightarrow Y.$ If $|Y| = k$ for some $k \in \mathbb{Z}^+$ and there exists some $y \in Y$ that is mapped to by at least $b$ elements in $X$, then $|X| \geq k \times (b - 1) + 1.$

This form is more concerned with the number of elements the domain must have to ensure that a certain number of elements get mapped to an element in the target. If $|X| \leq k \times (b - 1)$, then it is not guaranteed that an element in the target gets mapped to by $b$ elements in the domain.

The socks in the drawer problem can be revisited from a different perspective. Basically, we were trying to assign $b = 4$ socks to $1$ color among $k = 3$ colors. This necessitated pulling out at least $k \times (b - 1) + 1 = 3 \times (4 - 1) + 1 = 3 \times 3 + 1 = 10$ socks.

References

Pigeons-in-holes.jpg by en:User:BenFrantzDale; this image by en:User:McKay, CC BY-SA 3.0, via Wikimedia Commons.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort