Pigeonhole Principle
The Pigeonhole Principle states that if n items are placed into m containers and n > m, then at least one container must hold more than one item. It is a fundamental combinatorial tool used to prove the existence of certain configurations without constructing them explicitly. Applications range from proving that two people in a city share a birthday to guaranteeing collisions in hash functions.
Worked Example
Problem
A drawer contains socks in 5 different colours. How many socks must you draw (without looking) to guarantee a matching pair?
Solution
Step 1: Identify the number of "pigeonholes" — there are 5 colours, so m = 5. Step 2: Apply the Pigeonhole Principle: to guarantee that at least one colour repeats, you need n > m items. Step 3: With n = 5 draws you might get one sock of each colour — no pair yet. Step 4: The 6th sock must match one of the 5 colours already drawn.
Answer
6 socks must be drawn to guarantee at least one matching pair.
Common Applications of the Pigeonhole Principle
| Scenario | Pigeonholes (m) | Items (n) | Guaranteed Conclusion |
|---|---|---|---|
| Birthday matching in a group | 365 days | 366 people | At least 2 share a birthday |
| Sock colour matching | 5 colours | 6 socks | At least one matching pair |
| Hair strand count in a city | 150,000 strands | 1,000,000 people | Two people have same count |
| Hash table collisions | k buckets | k+1 keys | At least one bucket has 2 keys |
| Card suit matching | 4 suits | 5 cards | At least two cards share a suit |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Mathematical Induction
Mathematical induction is a proof technique used to establish that a statement P(n) holds for all natural numbers n by verifying a base case and then proving an inductive step. In the inductive step, one assumes P(k) is true (the inductive hypothesis) and derives that P(k+1) must also be true. This technique is analogous to a line of dominoes: knocking the first triggers an infinite chain.
Proof by Contradiction
Proof by contradiction (reductio ad absurdum) is a logical proof technique in which one assumes the negation of the statement to be proved, then derives a logical contradiction, thereby establishing the original statement's truth. It relies on the law of the excluded middle: a proposition is either true or false, with no middle ground. Classic examples include proofs that √2 is irrational and that there are infinitely many prime numbers.
Graph Theory
Graph theory is the branch of mathematics that studies graphs — mathematical structures consisting of vertices (nodes) connected by edges (links) used to model pairwise relationships between objects. It was founded by Leonhard Euler in 1736 when he solved the Königsberg bridge problem. Graph theory underpins computer networks, social network analysis, circuit design, scheduling algorithms, and shortest-path computations.
The term derives from the literal image of pigeons (columba) being assigned to holes (nidi) in a dovecote. The principle was formalised by German mathematician Peter Gustav Lejeune Dirichlet in 1834 and is therefore also called the Dirichlet drawer principle (Schubfachprinzip in German).