The idea: more pigeons than holes
The pigeonhole principle says: if n pigeons fly into m holes and n > m, at least one hole gets two or more pigeons. It sounds obvious, and it is. Its power comes from choosing what the pigeons and the holes are. The canvas places the pigeons one at a time and stops at the moment a hole is forced to share.
Pick a scenario, then press Next Item to place one pigeon or Place All to run to the end. Each pigeon takes two steps: it appears with the reason for its hole, then flies in. The panel on the right compares the fullest hole with the guarantee ⌈n/m⌉.
The proof is the worst case
To keep the pigeons apart for as long as possible, put each one into an empty hole. After m pigeons every hole holds one, and pigeon m + 1 has nowhere to go but a hole that is already taken. Any other order only makes a shared hole come sooner. That is the whole proof, and the canvas plays it: the socks and the people arrive in the worst-case order, each picking a new colour or month while one is left.
The general form: some hole gets at least ⌈n/m⌉ pigeons (n/m rounded up). If every hole had at most ⌈n/m⌉ − 1, the total would be at most m(⌈n/m⌉ − 1) < n. With 25 people and 12 months, the even spread gives every month 2 people after 24, and person 25 makes some month hold 3 = ⌈25/12⌉ (Demo: 25 people → three share a month).
The condition n > m matters. 12 people can have 12 different birth months, so nothing is forced (Demo: 12 people can all differ). The principle also tells you only that a shared hole exists, not which one.
Socks: choose the holes
A drawer holds red, blue and black socks, and you draw in the dark. How many socks must you take to be sure of a pair? The holes are the 3 colours, so 4 socks are enough: the first three can all differ, the fourth must match one of them (Demo: socks, 3 colours → 4 socks give a pair). For k socks of the same colour you need 3(k − 1) + 1 socks. The question "how many?" is always answered by the worst case plus one.
Birthdays
Among any 13 people two were born in the same month: 13 pigeons, 12 holes (Demo: 13 people → two share a birth month). Among any 367 people two share a birthday, because there are only 366 possible dates including February 29. In a city of a million people, at least ⌈1 000 000 / 366⌉ = 2 733 share a birthday.
This is not the birthday paradox. The paradox says that with only 23 people the probability of a shared birthday is above 50%. The pigeonhole principle gives certainty, and it needs 367.
Sums divisible by n
Claim: any n integers a₁, …, aₙ contain a block of consecutive ones, ai+1 + … + aj, whose sum is divisible by n. The pigeons are the n + 1 prefix sums S₀ = 0, S₁ = a₁, S₂ = a₁ + a₂, …, Sₙ. The holes are the n possible remainders mod n. Two prefix sums Si and Sj (i < j) land in the same hole, and then Sj − Si = ai+1 + … + aj is a multiple of n.
The canvas uses n = 6 and a = 4, 1, 3, 5, 3, 2 (Demo: a block whose sum is divisible by 6):
| prefix sum | value | mod 6 |
|---|---|---|
| S₀ | 0 | 0 |
| S₁ | 4 | 4 |
| S₂ | 5 | 5 |
| S₃ | 8 | 2 |
| S₄ | 13 | 1 |
| S₅ | 16 | 4, same as S₁ |
So S₅ − S₁ = 16 − 4 = 12 = a₂ + a₃ + a₄ + a₅ = 1 + 3 + 5 + 3. The collision came early, at the sixth pigeon; it is guaranteed by the seventh (S₆) at the latest. The same idea shows that some number made only of the digits 1 and 0 (such as 111…1000) is a multiple of any given n.
Erdős–Szekeres: a monotone run is unavoidable
The Erdős–Szekeres theorem: any sequence of n² + 1 different numbers has an increasing or a decreasing subsequence of length n + 1. A subsequence keeps the order but may skip numbers. For n = 3: any 10 different numbers contain an increasing or a decreasing run of 4.
Give every number a label (I, D): I is the length of the longest increasing subsequence that ends at it, D the length of the longest decreasing one. Two numbers never get the same label. If an earlier number x is smaller than a later number y, any increasing run ending at x can be extended by y, so y's I is bigger; if x is larger, y's D is bigger. If no run of length 4 existed, every label would have I, D ≤ 3: only 9 holes for 10 pigeons, and each hole may hold just one. So some label has I = 4 or D = 4.
On the canvas the sequence 6, 3, 8, 5, 10, 7, 1, 2, 4, 9 fills all nine cells, and the last number gets I = 4 through the run 1 < 2 < 4 < 9 (Demo: Erdős–Szekeres, 10 numbers → run of 4). The bound is tight: 7, 8, 9, 4, 5, 6, 1, 2, 3 has 9 numbers and no monotone run of 4. Computing the I labels for every position is the classic longest increasing subsequence algorithm.
Where it shows up in computing
- Hashing: a hash table with more keys than buckets must have a collision, whatever the hash function (see Open Hashing). A 256-bit hash maps infinitely many inputs to 2²⁵⁶ values, so collisions exist; security rests on them being hard to find.
- Compression: no lossless compressor can shrink every file. There are 2ⁿ files of n bits but fewer than 2ⁿ shorter ones, so two files would share a compressed form (see Huffman Coding).
- Loops in finite machines: a program with k possible states that runs for more than k steps must repeat a state; the same argument proves the pumping lemma for regular languages.
For the counting side, Inclusion–Exclusion and the Pigeonhole Principle counts the elements of a union exactly, and Truth Tables and Sets shows the sets behind it.
What the page leaves out
Ramsey theory (among any 6 people, 3 know each other or 3 are strangers), the infinite pigeonhole principle, the continuous version (two antipodal points on the equator have the same temperature, which uses the intermediate value theorem), Dirichlet's approximation theorem, and the probability of a collision before it is forced (the birthday paradox and hash collision rates).