October 1, 2019

Pigeon Hole Principle

Writer Emeritus

Imagine that you live in the good ol’ days of yore, before the internet and the telephone, when people communicated by tying messages to the legs of homing pigeons and sending them back to their owners. A delivery system not unlike the owls in Harry Potter, but with a less majestic bird!

Now imagine you’re in charge of your school’s pigeon coop. Today, you’ve received 11 pigeons, but there are only 10 pigeonholes. The solution? For now, you’ll have to put two pigeons in one hole.

In mathematics, we call this the Pigeon Hole Principle and it can be used to prove all kinds of complex theories!

A CLOSER LOOK AT THESE PIGEONS…

If you have “n” objects and “k” containers, and n > k, then at least one container will contain two objects. Or, to use a concrete example: if you have more pigeons than holes, a couple pigeons have to share!

Now, the theorem doesn’t tell you which hole gets the two pigeons. It could be the first hole, the second hole, the last hole — doesn’t matter! Technically, you also could put all the pigeons in a single hole and leave the others empty. All we know is that it’s impossible for each pigeon to have their own space, and therefore one hole has at least two birds.

EXAMPLES

To use the pigeon hole principle, you have to identify your objects and your containers, and then compare the size of the two sets to draw interesting conclusions.

1) If you have 366 people, then at least 2 of them share a birthday.

In this example, the birthdays are “containers”, so k = 365. Your “objects” are people, so n = 366. Since n > 365, we can guarantee that one day of the year is going to feature at least two birthday cakes. Chances there’ll be a lot more overlap — and days with no birthdays — but we can only guarantee one collision.

2) At least 2 people in New York have the exact same number of hairs on their head.

The average person has about 100,000 hairs on their head, with a maximum of about 500,000 hairs for really luscious locks. Let’s say there are k = 500,000 containers. The population of New York is over 8.6 million, which is way bigger!

We don’t know what the exact number is — perhaps 2 people have 196,738 hairs, or 10 people all have 100,000 hairs — but we do know that at least two people share the same number of hairs on their head.

SOLVING PROBLEMS WITH THE PIGEON HOLE PRINCIPLE

Let’s say you own yellow and blue socks and you keep them in a big jumble in your drawer. One morning, you get dressed in the dark and you can’t see the colour of your socks. (Maybe there’s a power outage?) How many socks should you pull out of the drawer to guarantee that you have a matching pair?

If you pull out 2 socks, they might both be blue, they might both be yellow, or you might get one blue and one yellow. It’s a risk. But if you pick 3 socks, you’re set!

In this example, our containers are the different sock colours (blue and yellow) so k = 2. Our objects are the socks themselves. To guarantee 2 objects in a single container, we need to pick n > k. So as long as we take 3 socks or more, either the blue container or the yellow container will have more than one sock. We’re guaranteed to be fashionable!

A MORE GENERAL PRINCIPLE

If we have “n” objects and “k” containers, and n > k, then at least one container must have ceiling (n / k) objects. The “ceiling” function simply rounds up decimal numbers. Even ceil (6.0001) = 7.

Meet Bob, a Martian creature with 7 legs who owns green, pink, and orange socks. If Bob gets dressed in the dark, how many socks should he remove from his dresser to make sure his 7 legs match?

In this example, we don’t need 2 objects in a container — we need 7! There are three socks colours, so k = 3. Therefore, we need to pick an “n” so that ceiling (n / k) = 7, which means n / k must be greater than 6.

The answer? Bob needs to pick 19 socks to ensure maximal style. 19 / 3 = 6.33, which rounds up to 7.

DON’T UNDERESTIMATE PIGEONS!

It might seem strange and a little frivolous, but the Pigeon Hole Principle has lots of applications in mathematics and computer science. At the end of the day, even the most complicated science is built on simple, intuitive truths.

Learn More

Writer Emeritus Patricia Foster 51 posts

Patricia Foster is a computer science student at Carleton University. In addition to working professionally as a software developer, she spends her time reading and writing.

The Latest
View All

Update: Your beanz Magazine Subscription

Can AI Find Clues to Aliens?

Code a Choose Your Adventure Game

World Gen Mods Ramp Up Minecraft Play