Pigeonhole Principle

The Pigeonhole Principle is a simple and elegant concept:

If you place more than n pigeons into n pigeonholes, at least one of the pigeonholes must contain more than one pigeon.

More generally, if you need to make more than n selections and only have n options, at least one of the options must be selected more than once.

This is also known as Dirichlet’s box principle, named after a German mathematician who applied this concept in a mathematical proof back in 1834!

The Pigeonhole Principle seems pretty straightforward and obvious, so how can it be useful? Here are a few ways you can apply it in real life:

Example 1: Socks in Drawers

You have a drawer with black, white, and red socks. If you blindly reach in to grab socks, how many socks do you need to grab in order to guarantee you will have two of the same color?

Well, there are only 3 colors of socks, so if you grab 3 socks, it is possible you will get one of each color. However, if you grab 4 socks, two of them must be the same color.

Example 2: Hairs on Heads

Prove that, at least two people in California have the exact same number of hairs on their heads. Setting aside the fact that there are likely quite a few bald people, you can apply the Pigeonhole Principle to prove this to be true.

The average number of hairs on a person’s head is somewhere in the range of ~150,000. You might reasonably assume an upper bound of 1,000,000–2,000,000 hairs on any person’s head (can you imagine?). Since the population of California is roughly 40 million, it follows that there must be at least two people there with the exact same number of hairs on their heads.


Relevant Brainteasers and Puzzles

Some more difficult or complex problems can be solved by cleverly identifying or defining the “right pigeonholes” on which to apply the Pigeonhole Principle.

Try some fun brainteasers that you can make a lot easier to solve using this concept:

Five’s a Crowd (medium)
Same Number of Handshakes (medium)
Divisible by 100 (hard)

Leave a Reply

Your email address will not be published. Required fields are marked *