What Is the Pigeonhole Principle? Examples and Applications

Pick any 13 people, anywhere. Ask nothing else about them. I can already guarantee two of them were born in the same month.

I don't need their names, their ages, or anything else about their lives. It works every single time, for every group of 13 or more. That's a strange thing to be able to say with total certainty about total strangers, and the reason it works has a name: the pigeonhole principle.

It sounds too obvious to be useful. Wait until you see what it can prove.

The idea is almost embarrassingly obvious

Picture an old writing desk with a row of small square slots built into it, the kind clerks once used to sort mail. Those slots are literally called pigeonholes, because they look like the little compartments people used to build into walls to house pigeons.

Now say you have 4 pigeonholes and 5 pigeons, and every pigeon has to go into some hole. At least one hole ends up with two or more pigeons in it. There's no way around it. Try every arrangement you like, and it happens every time.

Click a hole to send the next pigeon into it. Try to spread them out as evenly as you can, on purpose, and you'll still hit a hole with two pigeons by the time the 5th one drops. That's not luck. With 4 holes, pigeon number 5 is mathematically forced to double up somewhere.

That's the whole principle. If you have more items than containers, at least one container ends up holding more than one item. We write it formally as: if $n$ items are placed into $k$ containers and $n > k$, then some container holds at least 2 items. Simple enough to say in one sentence. Powerful enough to prove things that look nowhere near this simple.

But what if I have way more pigeons than that?

Here's where it gets more useful. Knowing that some hole gets crowded is fine, but what if you want to know exactly how crowded, at minimum?

Say you spread your pigeons as evenly as humanly possible. With $n$ pigeons and $k$ holes, the fairest split gives some holes $\lfloor n/k \rfloor$ pigeons and gives the rest one extra, $\lceil n/k \rceil$. That second number, always rounded up, is the least you can guarantee somewhere, no matter how hard you try to flatten things out.

Slide $n$ up and watch the bars. Even in the most balanced arrangement possible, at least one bar always reaches $\lceil n/k \rceil$. Try to shrink that tallest bar by moving a pigeon out of it, and you just made a different bar taller instead. You can't flatten it below the ceiling.

That gives us the generalized pigeonhole principle:

For our opening claim about birth months, $n = 13$ people and $k = 12$ months gives $\lceil 13/12 \rceil = 2$. That's the entire guarantee: at least one month has 2 people, every single time.

The real skill is naming the pigeons and the holes

Here's the part that trips people up. The pigeonhole principle itself isn't hard math, once you know the count it's one division and a round-up. The hard part, and the fun part, is figuring out what your pigeons and holes actually are in a real problem.

For the birth month claim, the pigeons are people and the holes are the 12 months. Let's watch it happen with actual random people instead of just trusting the formula.

Slide the room size down below 13 and reshuffle a few times. Sometimes you get lucky and every month is unique. Slide it up to 13 or beyond and reshuffle as many times as you like. You will never once see 12 empty gaps. Some month always doubles up. That's the difference between "probably" and "provably."

This is worth sitting with, because it's easy to confuse with a related but very different question: given a room of people, what's the chance two of them share the exact same birthday, not just the same month? That question has a genuinely surprising answer, and it lives in probability, not certainty. If that sounds interesting, the birthday paradox is the pigeonhole principle's louder, more famous cousin. Pigeonhole tells you something is certain. The birthday paradox tells you something unlikely turns out to be likely. Different tools, same neighborhood.

Guarantees come from the worst case, not the average case

One more example, because this is where the principle earns its keep in real problems: how many socks do you need to pull from a drawer, blind, to guarantee a matching pair?

Say the drawer has socks in $k$ different colors, plenty of each. If you're unlucky, or deliberately trying to avoid a match, you could pull one of every color before you're forced to double up. That's $k$ socks with zero pairs. The very next sock, sock number $k+1$, has nowhere to go but a color you've already got. A match is forced.

Step through the draws, or press play and watch it happen automatically. No matter which colors show up first, the $(k+1)$th sock always repeats one. The socks you pull are the pigeons, the colors are the holes, and "worst case" just means an imaginary adversary trying to dodge a collision for as long as mathematically possible, which turns out to be exactly $k$ draws.

This kind of worst-case reasoning shows up constantly once you notice it. A famous non-obvious version: in a city where nobody has more than 1 million hairs on their head, and the population is over 1 million, at least two people must have the exact same number of hairs. You'll never find that pair. You don't need to. The pigeonhole principle already proved they exist, the same way it proved a birth month collision, or a sock match. The proof doesn't need to point at a specific pair. It just needs to make hiding from a collision impossible.

The short version

The pigeonhole principle says that when you have more items than containers, at least one container is forced to hold more than one item. Spread things as evenly as you like, the tallest container never drops below $\lceil n/k \rceil$. The hard part is never the arithmetic. It's recognizing what counts as a pigeon and what counts as a hole in the problem sitting in front of you. Once you spot that, the guarantee falls out for free, no luck, no averages, no exceptions.

If you enjoyed the "certainty versus chance" contrast in this post, proof by contradiction is the other classic move mathematicians reach for to prove something exists without ever pointing at it directly, and it often works hand in hand with pigeonhole arguments.

All visualizations are interactive React components running entirely in your browser, computing every distribution and draw sequence live rather than looking up precomputed answers. No libraries beyond React.