Why the Pigeonhole Principle Is One of Math's Most Powerful Ideas

The Pigeonhole Principle is a really simple concept, discovered all the way back in the 1800s. It has explained everything from the amount of hair on people's heads to fundamental principles of computing. Here's how it works.

The Pigeonhole Principle

Peter Gustav Lejeune Dirichlet was a man with a lot of names and a lot of brains. He gave his name to his kids, and his brains - in a metaphorical sense - to the world. The youngest member of the Prussian Academy of Sciences, he worked at number theory and analysis, cranking out some quite difficult theories. He also came up with a simple little thing that he called The Drawer Principle, but that we now call The Pigeonhole Principle.

Why the Pigeonhole Principle Is One of Math's Most Powerful Ideas

Imagine fifteen pigeonholes and sixteen pigeons. A storm comes along, and all of the pigeons take shelter inside the pigeonholes. They could be arranged any number of ways. For all we know, all sixteen pigeons could be inside one hole, and the rest of the holes could be empty. What we know for sure, no matter what, is that there is at least one hole that contains more than one pigeon. The principle works no matter what the particular number of pigeons and pigeonholes, of course. As long as there are (N - 1) number of pigeonholes, and (N) number of pigeons, we know there will always be at least two pigeons in one hole.

So What?

This doesn't sound like the kind of stuff that sets the world on fire, but it can be a powerful way to look at different mathematical problems, like the hair of New Yorkers. Are there two New Yorkers out there with the exact same number of hairs on their heads? There definitely are. Leaving aside all of the bald New Yorkers (who would all have no hair), there are about 8 million people in total in New York, and only about 150,000 hairs on a person's head. That's eight million pigeons and only 150,000 hutches. At least two have to be in the same place - and two people in New York have to have the same number of hairs.

We can also apply the principle to groupings. In every group of N friends, at least two people have the same amount of friends. How do we know? In a group of, for example, 20 friends, the most friends one person can have is 19. (We are assuming all friendships are mutual.) That's 20 pigeons, and 19 holes, or N pigeons and N - 1 holes. Some pigeons have to be in the same hole, having the same amount of friends. It even works with behavior. There are N people in a room, and they go around shaking hands. No one shakes hands with the same person twice. Have two of them shaken the same number of hands? Yes, because there are N people and N - 1 amounts of handshakes to be had by each person. Two people have to have the same number of handshakes.

No, Really. So What?

Now let's say you have a group of around seven billion - the population of the world. And you want to find similarities in ancestral DNA. As the world's human population is currently as high as it's ever been - that is, until tomorrow - and we all have family trees that branch out into four grandparents, eight great grandparents, 16 great great grandparents, and so on, it's obvious that there are plenty of shared ancestors. This means that people will share certain mutations, markers, or sequences when it comes to DNA. Go even farther back, to non-human ancestors, and we'll still find these similar sequences of DNA.

Why the Pigeonhole Principle Is One of Math's Most Powerful Ideas

Wouldn't it be great if there were some kind of principle that allowed a computer to lump these similar sequences together, letting us know that they overlapped? This kind of analysis, which allows us to identify similar data, is a great strength of the pigeonhole principle when it comes to computers.

The principle has its drawbacks, though. Sometimes we want a distinct answer for every possibility. Input a wide range of data, and get a wide range of output. The pigeonhole principle shows that this is not always possible. In many situations, no matter how extensive the number of outputs, there are going to be collisions, in which distinct input data gets stuffed into the same pigeonhole.

[Via Pigeonhole Principle, The Pigeonhole Principle, Proof of Complexity of Pigeonhole Principles.]