7.3 The pigeonhole principle

The word “pigeonhole” can refer to a hole in which a pigeon roosts (i.e. pretty much what it sounds like) or a series of roughly square recesses in a desk in which one could sort correspondence (see Figure 7.9).

Pigeonholes in an old-fashioned roll top desk could be used to sort letters.

Figure 7.9: Pigeonholes in an old-fashioned roll top desk could be used to sort letters.

Whether you prefer to think of roosting birds or letters being sorted, the first and easiest version of the pigeonhole principle is that if you have more “things” than you have “containers”, there must be a container holding at least two things.

If we have six pigeons who are trying to roost in a coop with five pigeonholes, two birds will have to share.

If we have seven letters to sort and there are six pigeonholes in our desk, we will have to put two letters in the same compartment.

The “things” and the “containers” don’t necessarily have to be interpreted in the strict sense that the “things” go into the “containers.” For instance, a nice application of the pigeonhole principle is that if there are at least 13 people present in a room, some pair of people will have been born in the same month. In this example, the things are the people and the containers are the months of the year.

The abstract way to phrase the pigeonhole principle is:

Theorem 7.4 If \(f\) is a function such that \(|\operatorname{Dom}(f)| > |\operatorname{Rng}(f)|\) then \(f\) is not injective.

The proof of this statement is an easy example of proof by contradiction so we’ll include it here.

Proof. Suppose to the contrary that \(f\) is a function with \(|\operatorname{Dom}(f)| > |\operatorname{Rng}(f)|\) and that \(f\) is injective. Of course \(f\) is onto its range, so since we are presuming that \(f\) is injective it follows that \(f\) is a bijection between \(\operatorname{Dom}(f)\) and \(\operatorname{Rng}(f)\). Therefore (since \(f\) provides a one-to-one correspondence) \(|\operatorname{Dom}(f)| = |\operatorname{Rng}(f)|\). This clearly contradicts the statement that \(|\operatorname{Dom}(f)| > |\operatorname{Rng}(f)|\).

 

For a statement with an almost trivial proof, the pigeonhole principle is very powerful. We can use it to prove a host of existential results — some are fairly silly, others very deep. Here are a few examples:

  • There are two people (who are not bald) in New York City having exactly the same number of hairs on their heads.

  • There are two books in (insert your favourite library) that have the same number of pages.

  • Given \(n\) married couples (so \(2n\) people) if we choose \(n+1\) people we will be forced to choose both members of some couple.

  • Suppose we select \(n+1\) numbers from the set \(\{1, 2, 3, \ldots, 2n\}\), we will be forced to have chosen two numbers such that one is divisible by the other.

We can come up with stronger forms of the pigeonhole principle by considering pigeonholes with capacities. Suppose we have six pigeonholes in a desk, each of which can hold 10 letters. What number of letters will guarantee that one of the pigeonholes is full? The largest number of letters we could have without having 10 in some pigeonhole is \(9 \cdot 6 = 54\), so if there are 55 letters we must have 10 letters in some pigeonhole.

More generally, if we have \(n\) containers, each capable of holding \(m\) objects, than if there are \(n \cdot (m-1) + 1\) objects placed in the containers, we will be assured that one of the containers is at capacity. The ordinary pigeonhole principle is the special case \(m=2\) of this stronger version.

There is an even stronger version, which ordinarily is known as the “strong form of the pigeonhole principle.” In the strong form, we have pigeonholes with an assortment of capacities.

Theorem 7.5 If there are \(n\) containers having capacities \(m_1, m_2, m_3, \ldots, m_n\), and there are \(1 + \sum\limits_{i=1}^n (m_i - 1)\) objects placed in them, then for some \(i\), container \(i\) has (at least) \(m_i\) objects in it.

Proof. If no container holds its full capacity, then the largest the total of the objects could be is \(\sum\limits_{i=1}^n (m_i - 1)\).

7.3.1 Exercises

  1. The statement that there are two non-bald New Yorkers with the same number of hairs on their heads requires some careful estimates to justify it. Please justify it.

  2. A mathematician, who always rises earlier than her spouse, has developed a scheme — using the pigeonhole principle — to ensure that she always has a matching pair of socks. She keeps only blue socks, green socks and black socks in her sock drawer — 10 of each. So as not to wake her husband she must select some number of socks from her drawer in the early morning dark and take them with her to the adjacent bathroom where she dresses. What number of socks does she choose?

  3. If we select 1001 numbers from the set \(\{1, 2, 3, \ldots, 2000\}\) it is certain that there will be two numbers selected such that one divides the other. We can prove this fact by noting that every number in the given set can be expressed in the form \(2^k \cdot m\) where \(m\) is an odd number and using the pigeonhole principle. Write up this proof.

  4. Given any set of 53 integers, show that there are two of them having the property that either their sum or their difference is evenly divisible by \(103\).

  5. Prove that if 10 points are placed inside a square of side length 3, there will be 2 points within \(\sqrt{2}\) of one another.

  6. Prove that if 10 points are placed inside an equilateral triangle of side length 3, there will be 2 points within \(1\) of one another.

  7. Prove that in a simple graph (an undirected graph with no loops or parallel edges) having \(n \geq 2\) nodes, there must be two nodes having the same degree.