Cat among the pigeons

Some interesting observations with the pigeonhole principle

post

How many cats or pigeons can you see in this picture? Image: Flickr user Daniel Kulinski, CC BY-NC-SA 2.0.

I often find myself explaining how maths can be applied to real-world problems. This time we’ll look at the real world applied to maths! 

10 pigeons in 9 holes means that at least one hole is shared.

10 pigeons in 9 holes means that at least one hole is shared. Image: Wikimedia Commons user BenFrantzDale, CC-BY-SA 3.0

Pigeon keeping doesn’t seem to be very popular in the UK, which is something I like about this country (you wouldn’t believe how messy it can get). This hobby gives a name to one of my favourite theorems, the pigeonhole principle. It’s very powerful and also very intuitive—yes, bear with me, even if you think you “just can’t get maths”!

Domestic pigeons live in pigeonholes. What happens if we have more birds than holes? Then at least one of the holes must contain two birds. Now you can start showing off: you just learned a very important theorem.

The pigeonhole principle states precisely that if $n$ items are put into $m$ containers, with $n > m > 0$, then at least one container must contain more than one item. So if 10 pigeons will try to sleep in 9 pigeonholes, at least two of them cannot enjoy the luxury of a single room.

Why do we care about pigeons so much? This theorem has surprisingly many applications. Let’s take a look at a few of them.

Issue 5 collage, computer-rendered

Pick any page from this excellent maths magazine

The words in a magazine

Take any magazine or book in English, open it at a random page and underline a sequence of 27 words. Now, look at their first letters. I bet at least two of them start with the same letter, don’t they?

That’s because the alphabet consists of 26 letters (“pigeonholes”) and you just picked 27 words (“pigeons”).

Hair twins

In London, we can find at least two people with the same number of hairs on their heads (even if we exclude bald citizens). We can have only several hundred thousand hairs (“pigeonholes”), while London has a few million residents (“pigeons”).

Follow the star to… the Royal Albert Hall?! Image: Flickr user Nick Kenrick, CC BY-NC-SA 2.0.

Initial twins

Next time you go to the Royal Albert Hall, you can bet your friends that there are at least two visitors with the same first and last initials. The hall seats up to 5,272 people (“pigeons”). To be on the safe side, I’ll assume that there are 40 letters for each initial, just because as a proper Pole I don’t want to forget about letters from different alphabets. This gives us $40 \times 4 0=1600$ possible initial combinations (“pigeonholes”).

If the show is boring, go around and check IDs: maybe you’ll be lucky to find the initial twins!

The New Year’s Day Parade

At least 2,733 attendees of the New Year’s Day Parade in London must share their birthday. Every year around one million people gather in London to celebrate the New Year. We have 366 possible birthdays, so on average, there are $\text{1,000,000}/366=\text{2,732}.24$ people per one date. But the maximum must be at least the average (think about it!), so there must be a birthday shared by at least 2,733 spectators.

These are just fun facts easily proven by the pigeonhole principle. However, applications of this powerful theorem are ubiquitous in many areas of mathematics and other sciences. So next time you play musical chairs, you can count it as one of your 5-a-day maths exercises—because not only maths is fun, but also fun is maths!

As a PhD student at Imperial College, London, Paula uses maths and stats to study the impact of wind energy on electricity prices. The title of her TEDx talk `Let’s have a maths party!’ seems to summarise her two favourite activities.

More from Chalkdust