Skip to main content

Section 3.1 The Pigeonhole Principle

Let's kick off this chapter with a claim that seems suspect:

Claim. There are two people in Toronto with the exact same number of hair follicles on their head.

In your mind you're probably going ‘Even if this were true…how would we prove it??’ And yes, we wouldn't be able to actually count the number of hair follicles on anyone's head. But the beauty of the Pigeonhole Principle is that we don't need to!

I'm going to let Kyne of Canada's Drag Race Season 1 explain why this claim holds true (link to video).

@onlinekyne

#####

♬ original sound - onlinekyne

As you've seen, the Pigeonhole Principle is not a counting technique per se, but a way to prove that a set of objects satisfies some existence or extremal property. Before we state the principle formally let's look at two more examples.

If six friends order and finish eating a pizza that is divided into 8 slices, show that one of them gets at least 2 slices.

Solution

Towards a contradiction, suppose that each person gets at most one slice only. Then they will eat at most only 6 slices among them, leaving the pizza unfinished. This is a contradiction, so there must be one person who eats at least two slices.

Observe that this proof does not deny the possibility of multiple people getting two slices: it is quite possible that four of the friends ate a slice each, and the two others ate two slices each. It is also possible that one person ate three slices, while the five remaining friends ate a slice each.

In either case, one person ate at least two slices.

A pizza cut into eight slices and six mini-people around the pizza.

That's one big pizza!

A class of 20 students got their quiz scores back, and their instructor told them the average for the test was 8 out of a maximum of 10. Prove that someone in the class must have scored at least an 8/10.

Solution

Denote the scores of the students by \(x_1\text{,}\) \(x_2\text{,}\) and so on until \(x_{20}\text{.}\)

Assume that nobody scored at least an 8/10; that is, \(x_i \lt 8\) for all \(i = 1,2,\ldots, 20\text{.}\) Adding all these inequalities and dividing by 20, we obtain

\begin{align*} x_1 + x_2 + \cdots + x_{20} \amp \lt 160\\ \Rightarrow \dfrac{x_1+x_2+\cdots+x_{20}}{20} \amp \lt \dfrac{160}{20}\\ \Rightarrow \text{class average } \amp \lt 8\text{,} \end{align*}

which contradicts the assumption that the average was 8 out of 10.

For the previous examples, we argued that there is no other way but for the required property to hold, regardless of how the pizza slices/points are actually distributed among people. We call this kind of proof a non-constructive proof or an existence proof, since it shows that the property holds without actually giving an example (or an algorithm to create an example). Like the hair follicle example, this is typical of proofs that utilize the Pigeonhole Principle.

Video: Pigeonhole Principle

Setting \(k = 1\) in the statement of the principle results in the classic version:

Given any set of eleven natural numbers, prove that there must be two of them with the same last digit.

Hint

How many digits are possible?

Given any set of eleven natural numbers, prove that there must be a pair of elements whose difference is divisible by 10.

Hint

Use Checkpoint 3.1.6.

Often it is not immediately obvious what the pigeons and pigeonholes should be when we attempt to apply Theorem 3.1.3 to a problem. Moreover one needs also to give a rule that assigns pigeons to pigeonholes, such that:

  • There are fewer pigeonholes (\(n\)) than pigeons (\(\gt kn\)).
  • The desired property is satisfied when more than \(k\) objects is put into any class.

When using Theorem 3.1.3 one must explicitly state what the pigeons and pigeonholes are, and explain how the assignment is done.

If five numbers are selected from the set \(\{1,2,3,4,5,6,7\}\text{,}\) prove that two of these numbers must sum to 8.

Solution

Define pigeonholes to be the sets \(\{1,7\}\text{,}\) \(\{2,6\}\text{,}\) \(\{3,5\}\text{,}\) \(\{4\}\text{,}\) and pigeons to be the five numbers selected. Then picking five numbers from \(\{1,2,\ldots,7\}\) is the same as placing 5 pigeons into these 4 pigeonholes.

\(\{1,7\}\) \(\{2,6\}\) \(\{3,5\}\) \(\{4\}\)

Note that the last pigeonhole by definition can only contain at most one pigeon—this does not affect the proof. By PHP, there is a pigeonhole with two pigeons. That is, two numbers are selected from one of these sets; these two numbers must sum to 8.

We say that the number five is best possible in Example 3.1.8 since it is possible to select four numbers and not have any pair sum to 8 (for instance, pick 1, 2, 3, and 4). But selecting any five numbers from \(\{1,2,\ldots,7\}\) guarantees the property is satisfied.

Generalize Example 3.1.8. That is, if \(n+1\) numbers are selected from the set \(\{1,2,\ldots,2n-1\}\text{,}\) prove that two of these numbers must sum to \(2n\text{.}\)

The next example is slightly different in that we're not given a fixed set of numbers to work with. Instead, the result being proven holds for any set of six integers. (Convince yourself it works and try proving it yourself first before expanding the solution!)

Given any set of six integers, show that there is a pair among them whose sum or difference is divisible by 8.

Hint

Use remainders modulo 8.

Solution

If a pair of integers \(a, b\) among the six have the same remainder when dividing by 8, then their difference \(a-b\) is divisible by 8, and we are done.

So assume that all six integers have distinct remainders when dividing by 8. Construct the five pigeonholes \(\{0\},\{1,7\},\{2,6\},\{3,5\},\{4\}\) and place each of the six numbers in the pigeonhole corresponding to its remainder.

By PHP, one of these pigeonholes must have two numbers. That is, summing those two numbers gives a sum that is divisible by 8.

Show that Example 3.1.10 is best possible by constructing a set of five integers for which no pair has sum or difference divisible by 8.

Prove this generalization of Example 3.1.10:

Given any set of \(n+2\) integers, there is a pair among them whose sum or difference is divisible by \(2n\text{.}\)

A few more applications to conclude this section.

Prove that in any group of people, there must be two of them with the same number of friends in the group.

Solution

Suppose there are \(n\) people in the group. Then each person can have \(0, 1, \ldots, \text{ or } n-1\) friends among the group. This is still \(n\) pigeonholes, so we cannot apply PHP yet.

Observe that it cannot happen that someone has no friends, and someone else has \(n-1\) friends. (If a person has \(n-1\) friends, then every other person has at least one friend.) Hence there are only \(n-1\) possible numbers of friends among the \(n\) people, which means two of them must have the same number of friends, by the PHP.

Prove that any \((n+1)\)-subset of \(\{1,2,\ldots,2n\}\) contains two numbers such that one divides the other.

Hint

Pigeonholes are \(\{1\},\{3\},\{5\},\ldots,\{2n-1\}\text{;}\) assign each number to the pigeonhole that contains its largest odd divisor. If two numbers are in the same pigeonhole, why should one divide the other?

Over a two-week period (14 days), you kept track of how many showers you took. Your records show that you showered at least once every day, and that you showered a total of 17 times.

By following the steps below, prove that there was a period of consecutive days during which you showered exactly 10 times.

  1. Define variables \(x_i\) to be the number of times you took a shower on day \(i\) (\(1 \leq i \leq 14\)), and define \(y_i = x_1 + x_2 + \cdots + x_i\) to be the partial sums. Explain why it suffices to prove \(y_i = y_j + 10\) for some \(i,j\text{.}\)
  2. Explain why the set
    \begin{equation*} \{y_1,y_2,\ldots,y_{14},y_1+10,y_2+10,\ldots,y_{14}+10\} \end{equation*}
    can only contain numbers from 1 to 27.
  3. Apply Theorem 3.1.3 to prove the desired property. What are the pigeons and pigeonholes?
Hint

In part c., you may want to use the fact that the \(y_i\)'s are all distinct since \(x_i > 0\) for all \(i\text{.}\)