Consider the following questions:
- Are there two people in Boston with exactly the same number of hairs on their heads?
- 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?
- 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.
About that handshake…
The handshake problem is a little subtler. We will argue that when n people meet and some subset of them shake hands, at least 2 of them must have shaken hands with exactly the same number of other people. The holes will correspond to the number of handshakes, and the people will be the pigeons. Each of the n people can take part in anywhere from 0 to n-1 handshakes (remember they can’t shake their own hands). 0 to n-1 is a total of n different numbers of handshakes (for example if n=3, then each person can shake a total of 0, 1, or 2 hands). We also have n people, so at first it seems like we have just enough holes for our pigeons. The extra layer here is to notice that if there is anybody in the group that shook n-1 hands (everybody but themselves), then nobody in the group could have shaken 0 hands. So either nobody shook 0 hands or nobody shook n-1 hands. This brings us down to only n-1 different numbers of possible handshakes for the group and n people. So, the pigeonhole principle applies and says that there must be at least 2 people who took part in exactly the same number of handshakes. Our answer to question #3 is that it is impossible for everyone in a group to shake hands with a different number of people.
The pigeonhole principle is a great example of how even simple insights can have far-reaching implications.
Comments