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).