If you put eleven socks into ten drawers, at least one drawer will contain two socks. It seems too obvious to deserve a name, yet this principle, known as the pigeonhole principle, lets you prove results that are far from evident, and it explains some unbreakable limits of computing: no program compresses every file, no hash function is free of collisions.
Simple form
Pigeonhole principle: if n + 1 objects (or more) are placed into n boxes, at least one box contains at least two objects.
The proof is by contradiction: if every box held at most one object, there would be at most n objects.
In terms of functions: if |A| > |B|, no function from A to B is injective. Two different elements of A necessarily land on the same element of B.
Generalised form
If N objects are placed into k boxes, at least one box contains at least ⌈N/k⌉ objects, where ⌈x⌉ denotes the smallest integer greater than or equal to x.
Example: in a group of 100 people, at least ⌈100/12⌉ = 9 were born in the same month. We don't know which month, or who they are: we only know they must exist. This is typical of the pigeonhole principle: it gives non-constructive existence proofs.
Surprising examples
Two numbers, one a multiple of the other
Statement: if you choose any 51 numbers between 1 and 100, there are always two of which one divides the other.
Idea: every number can be written uniquely as 2ᵃ · d, with d odd. Between 1 and 100 there are 50 possible odd values of d (1, 3, 5, …, 99). These are the boxes. With 51 numbers, two share the same odd part d: they are 2ᵃ · d and 2ᵇ · d with a < b, and the first divides the second.
With 50 numbers the statement can fail: the numbers from 51 to 100 contain no such pair.
Points in a square
Statement: given 5 points in a square of side 1, two of them are at distance at most √2/2 ≈ 0.707.
Idea: divide the square into 4 small squares of side 1/2. With 5 points and 4 small squares, two points fall into the same one, and the greatest distance within a square of side 1/2 is its diagonal, √2/2.
Subsets with the same sum
Statement: given 10 distinct integers between 1 and 100, there are two disjoint non-empty subsets with the same sum.
Idea: there are 2¹⁰ − 1 = 1023 non-empty subsets. The sum of a subset cannot exceed 91 + 92 + … + 100 = 955, so there are at most 955 possible sums. There are more subsets than sums, so two different subsets have the same sum. Removing the elements they share from both gives two disjoint subsets, still with equal sums.
Note that the proof doesn't say which ones they are: finding them is a separate problem.
Lossless compression: an absolute limit
A lossless compression program must be injective: two different files cannot produce the same compressed file, otherwise decompression would not know which one to return.
Let's count. Files of exactly n bits number 2ⁿ. Shorter files, from 0 to n − 1 bits, number 2⁰ + 2¹ + … + 2ⁿ⁻¹ = 2ⁿ − 1. One fewer. So no compressor can reduce the size of every n-bit file: at least one stays the same length or grows.
Real compressors work because the files we care about, text, images, recordings, are highly regular and make up a tiny fraction of all possible files. On data that is already compressed or encrypted, which looks random, the gain is zero or negative. That is why compressing an encrypted archive is pointless: if you want compression, do it before encrypting.
Hashes, checksums and collisions
A hash function with a 256-bit output has 2²⁵⁶ possible values, while there are infinitely many possible inputs. By the pigeonhole principle collisions always exist, infinitely many of them. The security of a cryptographic hash lies not in the absence of collisions but in the practical impossibility of finding one.
The same holds for checksums and check digits: a single decimal check digit has only 10 values, so on average one in ten pairs of different codes share the same digit. Check digits are designed to catch the most likely errors, such as one wrong digit or two swapped digits, not every possible error.
This should be distinguished from a related but different phenomenon: the pigeonhole principle guarantees a collision only when the objects outnumber the boxes, whereas the probability of a collision becomes high much earlier, as shown by the probabilistic calculation known as the birthday paradox.
In short
- With more objects than boxes, at least one box holds two; with N objects and k boxes, at least ⌈N/k⌉.
- The principle proves existence without saying which object or which box.
- Choosing the right "boxes" is the real idea behind every proof.
- No lossless compressor can shorten every file of a given length.
- Hashes and checksums always have collisions: they are designed so that collisions are hard to find or rare for typical errors.
