The Pigeonhole Principle

Section 2.1 The Pigeonhole Principle

There are three kinds of mathematicians: Those who know how to count and those who don't. — Anonymous

Theorem 2.1.1.

Pigeonhole Principle: Suppose you have \(k\) pigeonholes and \(n\) pigeons to be placed in them. If \(n > k\) then at least one pigeonhole contains at least two pigeons. (See Figure 2.1.2.)

The pigeonhole principle has been attributed to German mathematician Johann Peter Gustav Lejeune Dirichlet, 1805 — 1859.

Proof.

Assume that we have \(k\) pigeonholes and \(n\) pigeons, with \(n > k\text{.}\) We view the notion of placing of \(n\) pigeons in \(k\) holes as a function

\begin{equation*} f:\{1,\ldots, n\}\to \{ 1,\ldots, k\}\text{.} \end{equation*}

The question is if it is possible for \(f\) to be an injective function, i.e., a function with the property that, for all \(x,y\in\{1,\ldots,n\}\text{,}\)

\begin{equation*} x\not= y\Rightarrow f(x)\not=f(y)? \end{equation*}

If it is, then there is a one-to-one correspondence between the set \(\{1,\ldots,n\}\) and the set

\begin{equation*} f(\{1,\ldots,n\})=\{z\in\{1,\ldots,k\}:\exists x\in\{1,\ldots,n\}, f(x)=z\}\text{.} \end{equation*}

This would mean that:

the set \(f(\{1,\ldots,n\})\) is a subset of \(\{1,\ldots,k\}\) AND
the set \(f(\{1,\ldots,n\})\) has \(n\) elements.

This contradicts the assumption that \(n>k\text{.}\) Therefore \(f\) cannot be an injective function, i.e. there are \(x,y\in\{1,\ldots,n\}\text{,}\)

\begin{equation*} x\not= y\mbox{ and } f(x)=f(y)\text{.} \end{equation*}

Example 2.1.3.

Show that among any \(5\) numbers one can find \(2\) numbers so that their difference is divisible by \(4\text{.}\)

Solution

Say that there are four pigeonholes: \(0,1,2\text{,}\) and \(3\text{.}\) We put the number \(a\) in the pigeonhole \(i\text{,}\) \(i\in\{0,1,2,3\}\text{,}\) if \(i\) is the remainder when \(a\) is divided by 4.

Since there are 5 numbers, at least two of them must be in the same pigeonhole:

\begin{equation*} a = 4k+i \text{ and } b=4n+1\text{.} \end{equation*}

It follows that

\begin{equation*} a-b =(4k+1)-(4n+i)=4(k-n) \end{equation*}

is divisible by 4.

Example 2.1.4.

Consider a chess board with two of the diagonally opposite corners removed. See Figure 2.1.5. Is it possible to cover the board with pieces of domino whose size is exactly two board squares?

Solution

Observe that there are sixty-two \(1\times1\) squares on this chess board. Hence, thirty-one \(2\times 1\) dominos would be needed to cover the board. Also observe that the new board contains 32 white squares and that each domino covers one white and one black square.

Consider 31 dominos as the pigeonholes. Since there are 32 white squares, at least one domino would have to have two white squares which is impossible.

Figure 2.1.5. Two dominos on a chess board with two of the diagonally opposite corners removed

Example 2.1.6.

There are 5 points in a square of side length 2. Prove that at least two of them are with the distance at most \(\sqrt{2}\text{.}\)

Solution

Divide the given square into for \(1\times 1\) squares. At least two points must belong to the same \(1\times 1\) square. The distance between those two points is not greater than the length of the diagonal \(\sqrt{2}\text{.}\)

Example 2.1.7.

A grid of 27 points in the plane is given. See Figure 2.1.8. Each point is coloured red or black. Prove that there exists a monochromatic rectangle, i.e., a rectangle with all four vertices of the same colour.

Solution

Observe that there are eight different ways to colour three points with two colours. Also observe that each coloured column contains two points of the same colour.

Let the nine columns be the pigeonholes and let the grid be coloured red and black in any of \(2^{27}= 13,4217,728\) ways. Since there are only eight different ways to colour a column and since there are nine columns, there must be at least two of the columns coloured in the same way.

Figure 2.1.8. 27 points in the plane; 3 rows and 9 columns

Theorem 2.1.9.

Generalized Pigeonhole Principle: If \(n\) pigeons are sitting in \(k\) pigeonholes, where \(n > k\text{,}\) then there is at least one pigeonhole with at least \(\lceil \frac{n}{k}\rceil\) pigeons and at least one pigeonhole containing not more than \(\lfloor \frac{n}{k}\rfloor\) pigeons.

Proof.

By definition \(\lceil \frac{n}{k}\rceil\) is the integer with the property

\begin{equation*} \frac{n}{k} \leq \left\lceil \frac{n}{k}\right\rceil \lt \frac{n}{k}+1\text{.} \end{equation*}

Hence, if none of the \(k\) pigeonholes contains \(\lceil \frac{n}{k}\rceil\) pigeons, i.e., if the maximum number of the pigeons per pigeonhole is less than or equal to \(\lceil \frac{n}{k}\rceil -1\) then

\begin{equation*} \text{ the number of pigeons } \leq k\cdot \left(\left\lceil \frac{n}{k}\right\rceil -1\right)\leq k\cdot \left( \left(\frac{n}{k}+1\right) -1\right) =k\cdot \frac{n}{k}=n \end{equation*}

which contradicts the assumption that there were \(n\) pigeons.

Also, by definition \(\lfloor \frac{n}{k}\rfloor\) is the integer with the property

\begin{equation*} \frac{n}{k} -1\lt \left\lfloor \frac{n}{k}\right\rfloor \leq\frac{n}{k}\text{.} \end{equation*}

This means that if each of the \(k\) pigeonholes contains more than \(\lfloor \frac{n}{k}\rfloor\) pigeons then

\begin{equation*} \text{ the number of pigeons } \geq k\cdot \left( \left\lfloor \frac{n}{k}\right\rfloor+1\right)> k\cdot \left( \left( \frac{n}{k}-1\right)+1\right)= k\cdot \frac{n}{k}=n \end{equation*}

which again contradicts the assumption that there were \(n\) pigeons.

Example 2.1.10.

There are 38 different time periods during which classes at a university can be scheduled. If there are 677 different classes, how many different rooms will be needed?

Solution

Here, \(n=677\) classes (= pigeons) and \(k=38\) different time slots (= pigeonholes). By the generalized pigeonhole principle, there is a pigeonhole (time slot) with

\begin{equation*} \left\lceil \frac{n}{k} \right\rceil=\left\lceil \frac{677}{38}\right\rceil=\left\lceil 17\frac{31}{38}\right\rceil=18 \end{equation*}

pigeons. Hence at least 18 classrooms are needed.

Resources.