# The pigeonhole principle: a counting concept with countless applications

By Jack M.

Consider the following questions:

1. Are there two people in Boston with exactly the same number of hairs on their heads?

2. You only own red, yellow, and blue socks. You’re pulling socks out of your sock drawer but the room is pitch black and you can’t see their color. What is the minimum number of socks you need to pull to guarantee that you leave your room with a matching pair of socks?

3. A group of people meet up and some number of them shake hands with each other. Is it possible that every person in the group shook hands with a different number of people? (People can’t shake their own hand).

At first blush, it might seem like these questions require very different approaches to answer. However, at the heart of the solution to each of these problems lies a simple mathematical concept called “the pigeonhole principle.”

The pigeonhole principle states: if n objects are placed into m holes and there are more objects than holes (n > m), then there is at least one hole containing more than one object.

For example, if you place 10 pigeons into 8 holes, at least one of the holes must have more than one pigeon in it: how could you place each pigeon into its own hole when there are fewer holes than pigeons? Another example: if you pick any 5 cards from a standard 52 card deck, then at least 2 of the 5 will have the same suit. You’re putting 5 pigeons (cards) into 4 holes (suits). Note that it’s also possible that more than 2 of the 5 cards share a suit. This is okay. Usually the pigeonhole principle is used to argue that at least 2 objects share some property, even if in fact many more do.

This concept might seem so intuitive that it doesn’t deserve its own name, but it is ubiquitous in math and computer science and has many far-reaching and unexpected consequences. Often the challenge in applying the pigeonhole principle is realizing which elements of your word problem should be thought of as holes and which should be thought of as pigeons. The most common case is when you are trying to argue that there exist two objects (or mathematical constructs) that share some property. You can then think of the objects as pigeons and the holes as properties. Let’s see how the pigeonhole principle applies to our three opening questions.

Are there two people in Boston with exactly the same number of hairs on their heads?

Before reading on, think about how you might go about answering this. What are the pigeons and what are the holes? Some googling reveals that the human head has on average about 100,000-150,000 hair follicles on it and even the hairiest among us won’t have more than 500,000. This means that, at most, there are about 500,000 options for how many hairs someone can have: if someone had exactly 1 hair, another had exactly 2 hairs etc. all the way up to 500,000, that only leaves room for 500,000 unique hair counts. Meanwhile, the population of Boston city proper is around 710,000 people. So there simply aren’t enough holes (possible hair counts) for all of the pigeons (Bostonians), and we can conclude that there must be at least two people in Boston with exactly the same number of hairs on their heads.

What about the socks?

Try your hand at the sock puzzle. We have 3 colors and our goal is to find the minimum number of socks such that at least 2 of them share a color. Sound familiar? Think of the colors as holes and the socks as pigeons. If we pick 4 socks, at least 2 of them must share a color in the same way that if we try to put 4 pigeons into 3 holes, at least 2 pigeons must share a hole.