Pigeon Hole Principle

.jocelyn. on Flickr

A simple, quirky theorem with big applications, from picking socks to counting hairs.

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

16 Fun Applications of the Pigeon Hole Principle

https://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle/

The Birthday Paradox

https://www.kidscodecs.com/birthday-paradox/

Video about the Pigeon Hole Principle

https://www.youtube.com/watch?v=9nYjPdMUAsk

Pigeon Hole Principle

https://en.wikipedia.org/wiki/Pigeonhole_principle

Fun facts

https://www.math.hmc.edu/funfacts/ffiles/10001.4.shtml

Pigeon Hole Principle

http://encyclopedia.kids.net.au/page/pi/Pigeonhole_principle

Pigeon Hole Principle for kids

https://kids.kiddle.co/Pigeonhole_principle

Also In The October 2019 Issue

Bring out your virtual carving knives — it’s time to give your digital pumpkins some spooky faces!

30+ ideas for STEAM-theme gifts for kids of all ages!

Teach kids basic coding skills by letting them program Botley to zoom around the room, draw shapes, and even avoid obstacles!

How 3D printing could help us get to Mars, and create new tools, homes, spacecrafts — even organs!

No discussion of design is complete without the history of lorem ipsum. It's more than placeholder text you stuff into a visual design.

"Hello World!" is one of the first programs you learn how to code. Here's the phrase in 4 languages with links to 100 more examples.

Learn the delicious-sounding secrets that websites use to keep your passwords safe from hackers.

A simple, quirky theorem with big applications, from picking socks to counting hairs.

Are you ready to create your virtual own solar system? With a little Python code and a little math, the sky’s the limit!

Learn some of the tricks game developers use to simulate an extra dimension.

How scammers can trick you into downloading malware onto your own computer.

There are pros and cons to networking all the “smart” devices in your home. What surprises does the future hold?

Sometimes, even the most dynamic languages need to classify and check data. Now, you can add your own types to any language!

Is it possible to steal software? And how do we know who owns code?

Check out this nifty feature that helps programs distinguish between variables with different scopes.

Create a simple electronic game with CircuitPython and Adafruit, and test your reflexes against friends and family!

Links from the bottom of all the October 2019 articles, collected in one place for you to print, share, or bookmark.