## The pigeonhole principle: using simplicity to understand complexity

Suppose you have a certain number of pigeons, and a certain number of pigeonholes. You must place each pigeon into one pigeonhole. If you have more pigeons than you do pigeonholes, then clearly there must exist a pigeonhole containing more than one pigeon.

This statement is known as the pigeonhole principle. It seems a very trivial and obvious statement. Having twelve pigeonholes for thirteen pigeons will result in an overpopulation of pigeons, so that at least two of them will have to share a hole. However, this simple statement has an astounding number of applications in solving very non-trivial mathematical problems.

Here’s a classic example:

*There exists two (non-bald) people in County Durham who have the same
number of hairs on their head.*

Using the pigeonhole principal alone, I can convince you that this is true. Firstly, some simple numerical facts. The population of County Durham is around 800,000. The average human head has around 150,000 hairs, and no one will have more than 500,000 hairs. So imagine in front of you are 500,000 boxes. Each box is labelled: “1 hair”, “2 hairs”, “3 hairs”, “4 hairs”, and so on, until the final boxes “499,999 hairs” and “500,000 hairs”. Now, place every single person in County Durham inside the box corresponding to the number of hairs on their head. Consequently, we have 800,000 people distributed between 500,000 boxes. This is precisely the set-up required to use the pigeonhole principle. In this example, the people of County Durham are the pigeons, and the boxes are the pigeonholes. Since we have more people than we do boxes, it follows that there exists a box with two or more people in. Therefore, these two people will have the same number of hairs on their head. This proves the statement is true. Isn’t that amazing? The complexity of a situation involving hundreds of thousands of individuals is captured by the simple statement of one number being larger than another.

Notice the use of the words “there exist” in the pigeonhole principal. This is an important point to recognise; the principle tells us nothing about the actual distribution of the shared pigeonhole. It also does not demonstrate how we can find these two people with the same number of hairs. We are only told about the existence of such an overlap.

Picture a party of *n* people, where the party is of
any size. As is customary of Durham parties, the party-goers decide to each
shake hands with a random number of people at the party. In this situation, the
pigeonhole principle can tell us that two people must have shaken the same
number of hands. Before the proof, please take a moment to convince yourself
that this is *not* an obvious statement. The hand-shaking is random, and
the size of the party is also random. Yet, within all this uncertainty, we can
absolutely guarantee that some people will have shaken the same number of
hands. The reason is as follows: for each person, it is possible for them to
have shaken hands with anywhere from 0 to *n-1* people. (Not *n*
people, since they won’t shake their own hand.) So, picture boxes labelled “0
shakes”, “1 shake”, “2 shakes”, “3 shakes”, all the way up to “n-1 shakes”.
Place each of the *n* people into the box corresponding to their number of
handshakes. This is a very similar situation as before; however, we are not
done yet. We have *n* people distributed amongst *n* boxes. We need
to eliminate a box in order to have the number of people being greater than the
number of boxes. This is easy to do: if there exists someone who didn’t shake
hands at all, then the “n-1 shakes” box is empty. Conversely, if everyone had
at least one hand shake, then the “0 shakes” box is empty. As a result of there
now being fewer boxes than people, it must be true that there exists a box with
two or more people in. Our result then follows by the pigeonhole principle.

The pigeonhole principal can be used as a gateway for
insight into much more abstract problems. For example, imagine placing all of
the whole numbers from 1 to 10, in any order, around a circle, creating a ring
of ten numbers. Then, regardless of the order you decided to place the numbers
in, there must always exist three consecutive numbers on the circle which add
up to 17 or more. For example, if your arrangement was {2, 5, 9, 10, 1, 3, 7,
8, 6, 4}, then these three numbers would be {5, 9, 10} since these add up to 24
(which is more than 17). We can prove this by demonstrating that the statement
cannot be false. Suppose the statement is wrong, namely that there exists a
circle of numbers where *no* three consecutive numbers sum to 17 or more. The
sum of all possible choices of three consecutive numbers is 3×(1+2+3+…+10)
= 165. This is because each number from 1 to 10 will appear in three different
choices of consecutive numbers. However, if we are in this case where no three
consecutive numbers add up to more than 17, then this total sum must be less than
16×10
= 160. This disagrees with our previous result that the sum must be 165, and so
we have arrived at a contradiction. Therefore, the statement cannot be false,
and so it is true.

These three examples highlight how a small change in
perspective can change seemingly impossible problems into simple counting
exercises. For further reading, if you are familiar with some standard A-Level
maths, you should look at ‘Rolle’s Theorem’ and some of its application.[1]
Rolle’s Theorem is also a very simple and obvious statement. But, it can be used
to prove some very important results about differentiable functions. A
particularly surprising application of Rolle’s Theorem is proving that, for any
differentiable functions *f *and *g*, which satisfy *f’’ + f’g – f = 0*,
the statements *f(a)=0* and *f(b)=0* imply that *f *is zero at all points between *a* and *b*.

To solve difficult problems, all that is often required is a
change in perspective.

[1] This
can be found in Michael Spivak’s *Calculus*
(Cambridge, Cambridge University Press, 2006).