Why is it called pigeonhole principle?

The Pigeonhole Principle is a really simple concept, discovered all the way back in the 1800s. It has explained everything from the amount of hair on people's heads to fundamental principles of computing. Here's how it works.

The Pigeonhole Principle

Peter Gustav Lejeune Dirichlet was a man with a lot of names and a lot of brains. He gave his name to his kids, and his brains - in a metaphorical sense - to the world. The youngest member of the Prussian Academy of Sciences, he worked at number theory and analysis, cranking out some quite difficult theories. He also came up with a simple little thing that he called The Drawer Principle, but that we now call The Pigeonhole Principle.

Imagine fifteen pigeonholes and sixteen pigeons. A storm comes along, and all of the pigeons take shelter inside the pigeonholes. They could be arranged any number of ways. For all we know, all sixteen pigeons could be inside one hole, and the rest of the holes could be empty. What we know for sure, no matter what, is that there is at least one hole that contains more than one pigeon. The principle works no matter what the particular number of pigeons and pigeonholes, of course. As long as there are (N - 1) number of pigeonholes, and (N) number of pigeons, we know there will always be at least two pigeons in one hole.

G/O Media may get a commission

An ultra-smart air monitor
or Black Friday, uHoo is $140 off its original price, plus you’ll get one year of uHoo’s Premium plan, with customized alerts about air quality.

So What?

This doesn't sound like the kind of stuff that sets the world on fire, but it can be a powerful way to look at different mathematical problems, like the hair of New Yorkers. Are there two New Yorkers out there with the exact same number of hairs on their heads? There definitely are. Leaving aside all of the bald New Yorkers (who would all have no hair), there are about 8 million people in total in New York, and only about 150,000 hairs on a person's head. That's eight million pigeons and only 150,000 hutches. At least two have to be in the same place - and two people in New York have to have the same number of hairs.

We can also apply the principle to groupings. In every group of N friends, at least two people have the same amount of friends. How do we know? In a group of, for example, 20 friends, the most friends one person can have is 19. (We are assuming all friendships are mutual.) That's 20 pigeons, and 19 holes, or N pigeons and N - 1 holes. Some pigeons have to be in the same hole, having the same amount of friends. It even works with behavior. There are N people in a room, and they go around shaking hands. No one shakes hands with the same person twice. Have two of them shaken the same number of hands? Yes, because there are N people and N - 1 amounts of handshakes to be had by each person. Two people have to have the same number of handshakes.

No, Really. So What?

Now let's say you have a group of around seven billion - the population of the world. And you want to find similarities in ancestral DNA. As the world's human population is currently as high as it's ever been - that is, until tomorrow - and we all have family trees that branch out into four grandparents, eight great grandparents, 16 great great grandparents, and so on, it's obvious that there are plenty of shared ancestors. This means that people will share certain mutations, markers, or sequences when it comes to DNA. Go even farther back, to non-human ancestors, and we'll still find these similar sequences of DNA.

Wouldn't it be great if there were some kind of principle that allowed a computer to lump these similar sequences together, letting us know that they overlapped? This kind of analysis, which allows us to identify similar data, is a great strength of the pigeonhole principle when it comes to computers.

The principle has its drawbacks, though. Sometimes we want a distinct answer for every possibility. Input a wide range of data, and get a wide range of output. The pigeonhole principle shows that this is not always possible. In many situations, no matter how extensive the number of outputs, there are going to be collisions, in which distinct input data gets stuffed into the same pigeonhole.

[Via Pigeonhole Principle, The Pigeonhole Principle, Proof of Complexity of Pigeonhole Principles.]

A key step in many proofs consists of showing that two possibly different values are in fact the same. The Pigeonhole principle can sometimes help with this.

Theorem 1.6.1 (Pigeonhole Principle) Suppose that $n+1$ (or more) objects are put into $n$ boxes. Then some box contains at least two objects.

Proof. Suppose each box contains at most one object. Then the total number of objects is at most $1+1+\cdots+1=n$, a contradiction. $\qed$

This seemingly simple fact can be used in surprising ways. The key typically is to put objects into boxes according to some rule, so that when two objects end up in the same box it is because they have some desired relationship.

Example 1.6.2 Among any 13 people, at least two share a birth month.

Label 12 boxes with the names of the months. Put each person in the box labeled with his or her birth month. Some box will contain at least two people, who share a birth month. $\square$

Example 1.6.3 Suppose 5 pairs of socks are in a drawer. Picking 6 socks guarantees that at least one pair is chosen.

Label the boxes by "the pairs'' (e.g., the red pair, the blue pair, the argyle pair,…). Put the 6 socks into the boxes according to description. $\square$

Some uses of the principle are not nearly so straightforward.

Example 1.6.4 Suppose $a_1,\ldots,a_n$ are integers. Then some "consecutive sum'' $a_k+a_{k+1}+a_{k+2}+\cdots+a_{k+m}$ is divisible by $n$.

Consider these $n$ sums: $$\eqalign{ s_1&=a_1\cr s_2&=a_1+a_2\cr s_3&=a_1+a_2+a_3\cr &\vdots\cr s_n&=a_1+a_2+\cdots+a_n\cr }$$ These are all consecutive sums, so if one of them is divisible by $n$ we are done. If not, dividing each by $n$ leaves a non-zero remainder, $r_1=s_1\bmod n$, $r_2=s_2\bmod n$, and so on. These remainders have values in $\{1,2,3,\ldots,n-1\}$. Label $n-1$ boxes with these $n-1$ values; put each of the $n$ sums into the box labeled with its remainder mod $n$. Two sums end up in the same box, meaning that $s_i\bmod n=s_j\bmod n$ for some $j>i$; hence $s_j-s_i$ is divisible by $n$, and $s_j-s_i=a_{i+1}+a_{i+2}+\cdots+a_j$, as desired. $\square$

A similar argument provides a proof of the Chinese Remainder Theorem.

Theorem 1.6.5 (Chinese Remainder Theorem) If $m$ and $n$ are relatively prime, and $0\le a< m$ and $0\le b< n$, then there is an integer $x$ such that $x\bmod m=a$ and $x\bmod n=b$.

Proof. Consider the integers $a,a+m,a+2m,\ldots a+(n-1)m$, each with remainder $a$ when divided by $m$. We wish to show that one of these integers has remainder $b$ when divided by $n$, in which case that number satisfies the desired property.

For a contradiction, suppose not. Let the remainders be $r_0=a\bmod n$, $r_1=a+m\bmod n$,…, $r_{n-1}=a+(n-1)m\bmod n$. Label $n-1$ boxes with the numbers $0,1,2,3,\ldots,b-1,b+1,\ldots n-1$. Put each $r_i$ into the box labeled with its value. Two remainders end up in the same box, say $r_i$ and $r_j$, with $j>i$, so $r_i=r_j=r$. This means that $$a+im=q_1n+r\quad\hbox{and}\quad a+jm=q_2n+r.$$ Hence $$\eqalign{ a+jm-(a+im)&=q_2n+r-(q_1n+r)\cr (j-i)m&=(q_2-q_1)n.\cr }$$ Since $n$ is relatively prime to $m$, this means that $n\divides(j-i)$. But since $i$ and $j$ are distinct and in $\{0,1,2,\ldots,n-1\}$, $0< j-i< n$, so $n\nmid(j-i)$. This contradiction finishes the proof. $\qed$

More general versions of the Pigeonhole Principle can be proved by essentially the same method. A natural generalization would be something like this: If $X$ objects are put into $n$ boxes, some box contains at least $m$ objects. For example:

Theorem 1.6.6 Suppose that $r_1,\ldots,r_n$ are positive integers. If $X\ge(\sum_{i=1}^n r_i) -n + 1$ objects are put into $n$ boxes labeled $1,2,3,\ldots,n$, then some box labeled $i$ contains at least $r_i$ objects.

Proof. Suppose not. Then the total number of objects in the boxes is at most $(r_1-1)+(r_2-1)+(r_3-1)+\cdots+(r_n-1)=(\sum_{i=1}^n r_i) -n < X$, a contradiction. $\qed$

This full generalization is only occasionally needed; often this simpler version is sufficient:

Corollary 1.6.7 Suppose $r>0$ and $X\ge n(r-1)+1$ objects are placed into $n$ boxes. Then some box contains at least $r$ objects.

Proof. Apply the previous theorem with $r_i=r$ for all $i$. $\qed$

Here is a simple application of the Pigeonhole Principle that leads to many interesting questions.

Example 1.6.8 Suppose 6 people are gathered together; then either 3 of them are mutually acquainted, or 3 of them are mutually unacquainted.

We turn this into a graph theory question: Consider the graph consisting of 6 vertices, each connected to all the others by an edge, called the complete graph on $6$ vertices, and denoted $K_6$; the vertices represent the people. Color an edge red if the people represented by its endpoints are acquainted, and blue if they are not acquainted. Any choice of 3 vertices defines a triangle; we wish to show that either there is a red triangle or a blue triangle.

Consider the five edges incident at a single vertex $v$; by the Pigeonhole Principle (the version in corollary 1.6.7, with $r=3$, $X=2(3-1)+1=5$), at least three of them are the same color, call it color $C$; call the other color $D$. Let the vertices at the other ends of these three edges be $v_1$, $v_2$, $v_3$. If any of the edges between these vertices have color $C$, there is a triangle of color $C$: if the edge connects $v_i$ to $v_j$, the triangle is formed by $v$, $v_i$, and $v_j$. If this is not the case, then the three vertices $v_1$, $v_2$, $v_3$ are joined by edges of color $D$, and form a triangle of color $D$. $\square$

The number 6 in this example is special: with 5 or fewer vertices it is not true that there must be a monochromatic triangle, and with more than 6 vertices it is true. To see that it is not true for 5 vertices, we need only show an example, as in figure 1.6.1.

Figure 1.6.1. An edge coloring with no monochromatic triangles.

The Ramsey number $R(i)$ is the smallest integer $n$ such that when the edges of $K_n$ are colored with two colors, there is a monochromatic complete graph on $i$ vertices, $K_i$, contained within $K_n$. The example shows that $R(3)=6$.

More generally, $R(i,j)$ is the smallest integer $n$ such that when the edges of $K_n$ are colored with two colors, say $C_1$ and $C_2$, either there is a $K_i$ contained within $K_n$ all of whose edges are color $C_1$, or there is a $K_j$ contained within $K_n$ all of whose edges are color $C_2$. Using this notion, $R(k)=R(k,k)$. More generally still, $R(i_1,i_2,\ldots,i_m)$ is the smallest integer $n$ such that when the edges of $K_n$ are colored with $m$ colors, $C_1,…,C_m$, then for some $j$ there is a $K_{i_j}$ contained in $K_n$ all of whose edges are color $C_j$.

Ramsey proved that in all of these cases, there actually is such a number $n$. Generalizations of this problem have led to the subject called Ramsey Theory.

Computing any particular value $R(i,j)$ turns out to be quite difficult; Ramsey numbers are known only for a few small values of $i$ and $j$, and in some other cases the Ramsey number is bounded by known numbers. Typically in these cases someone has exhibited a $K_m$ and a coloring of the edges without the existence of a monochromatic $K_i$ or $K_j$ of the desired color, showing that $R(i,j)>m$; and someone has shown that whenever the edges of $K_n$ have been colored, there is a $K_i$ or $K_j$ of the correct color, showing that $R(i,j)\le n$.

Exercises 1.6

Ex 1.6.1 Assume that the relation "friend'' is symmetric. Show that if $n\ge2$, then in any group of $n$ people there are two with the same number of friends in the group.

Ex 1.6.2 Suppose that 501 distinct integers are selected from $1\ldots1000$. Show that there are distinct selected integers $a$ and $b$ such that $a\divides b$. Show that this is not always true if 500 integers are selected. (hint)

Ex 1.6.3 Each of 15 red balls and 15 green balls is marked with an integer between 1 and 100 inclusive; no integer appears on more than one ball. The value of a pair of balls is the sum of the numbers on the balls. Show there are at least two pairs, consisting of one red and one green ball, with the same value. Show that this is not necessarily true if there are 13 balls of each color.

Ex 1.6.4 Suppose we have 14 red balls and 14 green balls as in the previous exercise. Show that at least two pairs, consisting of one red and one green ball, have the same value. What about 13 red balls and 14 green balls?

Ex 1.6.5 Suppose $(a_1,a_2,\ldots,a_{52})$ are integers, not necessarily distinct. Show that there are two, $a_i$ and $a_j$ with $i\ne j$, such that either $a_i+a_j$ or $a_i-a_j$ is divisible by 100. Show that this is not necessarily true for integers $(a_1,a_2,\ldots,a_{51})$.

Ex 1.6.6 Suppose five points are chosen from a square whose sides are length $s$. (The points may be either in the interior of the square or on the boundary.) Show that two of the points are at most $s\sqrt2/2$ apart. Find five points so that no two are less than $s\sqrt2/2$ apart.

Ex 1.6.7 Show that if the edges of $K_6$ are colored with two colors, there are at least two monochromatic triangles. (Two triangles are different if each contains at least one vertex not in the other. For example, two red triangles that share an edge count as two triangles.) Color the edges of $K_6$ so that there are exactly two monochromatic triangles.

Ex 1.6.8 Suppose the edges of a $K_5$ are colored with two colors, say red and blue, so that there are no monochromatic triangles. Show that the red edges form a cycle, and the blue edges form a cycle, each with five edges. (A cycle is a sequence of edges $\{v_1,v_2\},\{v_2,v_3\},\ldots,\{v_k,v_1\}$, where all of the $v_i$ are distinct. Note that this is true in figure 1.6.1.)

Ex 1.6.9 Show that $8< R(3,4)\le 10$.

Ex 1.6.10 Show that $R(3,4)=9$.