Member-only story
The Pigeonhole Principle and Its Surprisingly Powerful Applications
The most powerful tool you’ll ever learn
If I had to teach only one tool or mathematical principle to someone, it would have to be what I consider one of the most impressive intellectual power tools of mathematics yet so simple that anyone can understand it — it is called the pigeonhole principle.
In this article, we use this simple principle to show some impressive results. Among other things, we will show that the following statements are true:
- In London, there must be at least two non-bald people with the same number of hairs on their heads
- There does not exist an algorithm that losslessly compresses any data
- No matter how you distribute 5 points on a sphere, we can always find a (closed) hemisphere containing at least 4 of the points
- There will always be at least two guests at a party who shake hands with the same number of people
These statements seem difficult to prove (some even unapproachable). But they can be proved in a few lines with simple logical arguments and without a single equation.
Let’s get started.
The pigeonhole principle
For some reason, this amazing logical weapon is not taught at the lower levels of mathematics even though completely accessible even for people with only little to no mathematical experience. In fact, the principle itself is stupidly simple.
It states:
“If n items are put into m containers, with n > m, then at least one container must contain more than one item.”
Really!? Is that it? I can hear you ask and yes that is it! But as you will soon see, we can use this and versions of this to prove amazing and at times completely unintuitive things.
It has its name from how we think of it. We imagine a flock of pigeons that has to go into pigeonholes but where there are more pigeons than pigeonholes. Then there must be at least one pigeonhole containing more than one pigeon.
