← back to lab

Pigeonhole Principle

If you put more pigeons into fewer holes, at least two pigeons must share a hole. This elementary fact powers some of the most surprising results in mathematics. With only 23 people in a room, there’s a 50% chance two share a birthday. Most people guess 183. The principle is simple. The intuition is broken.

P(collision, n, d) = 1 − ∏_i=0^n-1 (d − i)/d ≈ 1 − e^{−n(n−1)/(2d)}

People 23

P(collision) 50.7%

Empirical —

Trials 0

People in room (n) 23

Click Run 1 Trial to simulate a room of people and check for shared birthdays, or Run 1000 Trials to compare the empirical collision rate against the theoretical curve.

Sock Colors 5

Pairs per Color 3

With 5 colors in the drawer, you are guaranteed a matching pair after drawing at most 6 socks (n + 1 by the pigeonhole principle). Click Draw a Sock to test it.

Hash Space 256

Items Hashed 0

Collisions 0

P(1st collision) ~18

Hash Space Size 256

A hash function maps inputs to a fixed-size space. Even with a space of 256 slots, a collision is 50% likely after only ~18 items (the birthday bound: √(2 · 256 · ln 2) ≈ 18.8). Click Add Items to watch collisions appear.

The pigeonhole principle

If n items are placed into m containers and n > m, then at least one container must hold more than one item. This is the pigeonhole principle (Schubfachprinzip), stated by Dirichlet in 1834. It is trivially true and profoundly useful — it powers results across combinatorics, number theory, computer science, and cryptography.

The birthday paradox

With 365 possible birthdays (pigeonholes) and n people (pigeons), the probability of at least one shared birthday is P = 1 − 365!/((365−n)!·365ⁿ). This exceeds 50% at just n = 23, and 99% at n = 57. The paradox is not mathematical but psychological — humans compare n to 365 instead of to the number of pairs, which is n(n−1)/2.

The sock drawer

A drawer has socks of k colors. How many must you draw (blindfolded) to guarantee a matching pair? By the pigeonhole principle: k + 1. The first k draws could each produce a different color. The (k+1)-th must match one of them. This is the principle in its purest form.

Hash collisions and the birthday attack

A hash function maps arbitrary inputs into a fixed space of d values. By the birthday paradox, a collision becomes likely after roughly √(d) insertions, not d. For a 128-bit hash (d = 2¹²⁸), collisions appear after about 2⁶⁴ attempts. This is the birthday attack, and it halves the effective security of any hash. It is the reason cryptographic hashes need to be twice as wide as the desired security level.

Why intuition fails

The human mind estimates probabilities linearly. We intuit that 23 people from 365 days means roughly 23/365 ≈ 6% chance of a match. But collisions grow quadratically with the number of items (because the number of pairs grows as n²), and our linear intuition systematically underestimates this.