A deterministic counting guarantee: more items than buckets force a shared bucket. Derive the ceiling bound and distinguish unavoidable concentration from collision probability.
Pigeonhole principle
The pigeonhole principle says that assigning more items than available buckets, with each item assigned to exactly one bucket, forces some bucket to contain at least two items. For a quant, it gives a quick feasibility check: a proposed allocation or encoding cannot keep every bucket lightly loaded when there are too few destinations.
The useful general form is stronger. If N items are assigned to k≥1 buckets and nj is the number in bucket j, then
1≤j≤kmaxnj≥⌈kN⌉.
Here N is a nonnegative integer and k a positive integer. The ceiling gives the smallest integer at least as large as its argument. The largest count cannot be smaller than the average N/k; because counts are integers, it must reach the ceiling. No randomness, independence or equal allocation probabilities are required. The Edinburgh counting notes give the same bound with a contradiction proof.
Twenty-five orders, six venues
Suppose a fictional routing record contains 25 distinct orders over a stated interval. Each order was assigned to exactly one of six venues. Some venue must have received at least
⌈625⌉=5
orders. If every venue had received at most four, the record could contain at most 6×4=24 orders, contradicting the total of 25.
Twenty-five fictional orders allocated across six venues have counts 5, 4, 4, 4, 4, 4. At least five at one venue is unavoidable because four per venue would hold only 24.
An allocation attaining the lower bound. These are counts over the chosen interval, not simultaneous outstanding orders or venue capacities.
The allocation (5,4,4,4,4,4) totals 25 and has largest count five. It therefore shows that five is the strongest lower bound available from these counts alone: six at one venue is not guaranteed.
The principle does not identify that venue, require all six venues to receive orders, or imply that five orders were outstanding simultaneously. Sending all 25 orders to one venue also satisfies the counting assumptions. If an order can be split across venues, define the counted items and their unique assignments again before applying the bound.
What the guarantee buys you
In a hash table, mapping more distinct keys than hash buckets forces a collision. Viewed as a function, that map cannot be injective: at least two inputs share an output. This counting fact does not reveal which keys collide or assess the hash function's quality.
An occupancy and birthday problem asks a different question: how likely is a collision under a specified random allocation model? Such a probability can be substantial before a collision becomes unavoidable. Pigeonhole reasoning supplies certainty once the count forces it; it supplies no collision probability below that threshold.
The practical method is to name the items, define the buckets, and check that each item enters exactly one bucket. To force at least r≥2 items into some one of k buckets, k(r−1)+1 items suffice. With one fewer item, giving every bucket exactly r−1 still avoids the target. The difficult step in richer proofs is often choosing the buckets, as Yong's lecture illustrates.
