The pigeonhole principle: guaranteed collisions, and the craft of choosing the holes

The principle, and why it cannot fail

The pigeonhole principle says: place more than n items into n boxes, and at least one box receives at least two items. The proof is one line of last lesson’s counting — suppose instead that every box held at most one item; then n boxes hold at most n items in total, but we placed n + 1. Contradiction, of the honest kind you met in unit 04: the assumption “no box has two” cannot survive the count.

Two classics, argued gently. First: among any 13 people, two share a birth month. The boxes are the 12 months; the pigeons are the 13 people; 13 into 12 forces a shared box. Second, the famous one: two residents of Moscow have exactly the same number of hairs on their head. A human head carries at most about 1,000,000 hairs, so the boxes are the hair-counts 0 through 1,000,000 — about a million of them. Moscow has over 13,000,000 residents. People outnumber possible hair-counts thirteen to one, so some count is shared. The argument never examines a single scalp: the size of the population beats the size of the answer space, and that alone settles it.

Mind what the principle does and does not say. It proves a shared box exists; it never tells you which box, or which two items share it. Among the 13 people it does not say anyone is born in January — all 13 could cluster in two summer months. Existence without location is the principle’s signature, and it is exactly what made the Hook’s ticket closable without reading any code.

Classic examples: months and hair counts

The craft: you design the boxes

Stated, the principle sounds too obvious to be useful. Its power comes from a degree of freedom the statement hides: you decide what the boxes are. Most pigeonhole proofs are one clever box-design away from trivial.

The workhorse design is remainders. Divide any integer by n and the remainder is one of exactly n values: 0, 1, …, n−1. Those n values are boxes. So among any n + 1 integers, two leave the same remainder when divided by n — and their difference is therefore divisible by n. You never look at the numbers; you count the boxes:

// Any 4 integers: two share a remainder mod 3.
// Three boxes (0, 1, 2) cannot hold four numbers one each.
const xs = [7, 12, 22, 31];
xs.map(n => n % 3);   // [1, 0, 1, 1] — 7, 22, 31 all landed in box 1
                      // 22 - 7 = 15, divisible by 3, as promised

Ranges work as boxes too. Pick any 6 distinct numbers from 1 to 10: two of them must be consecutive. Design the boxes as five pairs — 2, 4, 6, 8, 10 — and 6 numbers into 5 pair-boxes force two numbers into the same pair. The insight is never the counting; it is seeing that “consecutive” can be encoded as “same box”.

More pigeons: the generalized principle

The principle scales. Place n · k + 1 items into n boxes and some box holds at least k + 1. Same one-line proof: if every box held at most k, the total would be at most n · k — one short. Concretely: 25 pigeons into 12 holes (25 = 12 · 2 + 1) force 3 pigeons into some hole. And the Hook’s arithmetic is exactly this form: 100,000 sessions into 4,096 buckets — since 4,096 · 24 = 98,304 is less than 100,000, some bucket holds at least 25. The general recipe: divide items by boxes and round up; that ceiling is the guaranteed worst-case occupancy of the fullest box.

Hash tables: collisions are arithmetic, not bad luck

A hash function maps a huge key space — all possible strings — into a small bucket space. The moment stored keys outnumber buckets, the pigeonhole principle applies with no further conditions: a table with 1,000 buckets holding 1,001 keys has a collision. Not probably. Not because the hash is weak. By counting. A bucket is an equivalence class — the set of all keys the hash maps to the same value — and 1,001 keys cannot occupy 1,000 classes one each.

In practice, collisions arrive long before they are guaranteed. With 1,000 buckets and random keys, the odds that some two keys collide pass 50% at around just 38 keys. The intuition — no probability machinery needed — is that collisions come from pairs, and pairs grow fast: 38 keys form 38 · 37 / 2 = 703 pairs (a counting fact from last lesson), each pair an independent 1-in-1,000 shot at colliding. This is the birthday-paradox effect, and it is why real hash tables plan for collisions at every load factor, not just past capacity.

When you next review a hash table implementation, ask yourself not “is the hash function good?” but “how many buckets do I have, and how many keys am I storing?” The math answers the collision question before you read a line of code. The misconception this lesson dismantles: a good hash function avoids collisions. It cannot — past the bucket count, collisions are forced by counting. What a good hash function does is spread collisions evenly so no bucket is needlessly crowded; what a bad one does is cluster them. Zero collisions requires dodging the principle itself: perfect hashing, which is possible only when the key set is fixed and known in advance.