Calculus

Set Theory

Set Theory Logo

Pigeonhole Principle

The pigeonhole principle states that if \(n\) pigeons (or any other items) are placed into \(m\) holes and \(n \gt m,\) then at least one hole must contain more than one pigeon. Respectively, if there are more holes than pigeons \(\left( {n \lt m} \right),\) some holes are empty.

Pigeonhole principle
Figure 1.

If \(A\) is a set of pigeons and \(B\) is a set of pigeonholes, then the mapping of pigeons to pigeonholes can be described by a function \(f: A \to B.\) It is clear that \(A\) and \(B\) can be arbitrary finite sets.

The following statements are true:

  1. If \(\left| A \right| \gt \left| B \right|,\) then the function \(f: A \to B\) is not injective.
  2. If \(\left| A \right| \lt \left| B \right|,\) then the function \(f: A \to B\) is not surjective.

A more general version of the pigeonhole principle is formulated as follows:

For any \(n,m \in \mathbb{N},\) if \(n\) objects are distributed among \(m\) sets, then at least one set must hold at least \(\left\lceil {\large{\frac{n}{m}}\normalsize} \right\rceil\) objects, where \(\lceil \cdot \rceil\) denotes the ceiling function.

Examples

Birthday Problem

Suppose there are \(40\) students in a class. Is there a month in the year in which at least \(4\) students were born?

There are \(40\) students for \(12\) months. Let the students be “items”, and the months be “boxes”. So we have \(n = 40,\) \(m = 12.\) By the generalized pigeonhole principle, there exists at least one box (month) containing at least \(\left\lceil {\large{\frac{n}{m}}\normalsize} \right\rceil\) items (students). Substituting \(n\) and \(m,\) we get

\[\left\lceil\frac{n}{m}\right\rceil = \left\lceil\frac{{40}}{{12}}\right\rceil = \left\lceil3\frac{1}{3}\right\rceil = 4.\]

Thus, there is a month in which at least \(4\) students have a birthday.

Apples in Boxes

There are \(25\) boxes with three varieties of apples. Each box contains only one kind of apples. Prove that there are at least \(9\) boxes with apples of the same variety.

Apples in boxes on a market.
Figure 2.

Let the boxes be “pigeons” and the variety of apples be “holes”. Using the generalized pigeonhole principle with \(n = 25\) and \(m = 3,\) we obtain:

\[\left\lceil\frac{n}{m}\right\rceil = \left\lceil\frac{{25}}{{3}}\right\rceil = \left\lceil8\frac{1}{3}\right\rceil = 9.\]

Hence, there are at least \(9\) crates of the same apple variety.

Football Tournament

Suppose there are \(n\) teams participating in a football tournament where each team plays with every other team. Prove that, at any intermediate moment of the tournament, there are always two teams that have played the same number of matches.

A football tournament. The Camp Nou stadium in Barcelona, Spain.
Figure 3.

We will consider the teams as “pigeons” and the number of matches played as “pigeonholes”. It is obvious that the number of games played by a team can vary from \(0\) to \(n – 1.\) Note that if there is a team that has played \(n – 1\) matches, then no other team will be idle. So, we have \(n\) pigeons and \(n – 1\) holes, where \(n \ge 1.\)

By the pigeonhole principle, there will always be two teams that have played an identical number of matches.


Solved Problems

Click or tap a problem to see the solution.

Example 1

Prove that any set of \(6\) distinct natural numbers contains two numbers whose difference is divisible by \(5.\)

Example 2

The cells of a \(3 \times 3\) array contain numbers \(-1, 0, 1.\) Prove that at least two of the eight sums on rows, columns and main diagonals are equal.

Example 3

Consider an equilateral triangle with side length \(a = 1.\) Prove that among any \(5\) points inside the equilateral triangle, there always exist two points that are within \(\large{\frac{1}{2}}\normalsize\) units of each other.

Example 4

A \(5 \times 6\) chessboard has 19 squares colored black. Prove that there exists a \(2 \times 2\) square in which at least three cells are colored black.

Example 5

Prove that if \(7\) natural numbers are chosen at random, then the sum of three of them is divisible by \(3.\)

Example 6

Prove that if the integers \(m\) and \(n\) are coprime, then there is a natural number \(k\) such that \(m^k – 1\) is divisible by \(n.\)

Example 1.

Prove that any set of \(6\) distinct natural numbers contains two numbers whose difference is divisible by \(5.\)

Solution.

When a number is divided by \(5,\) it can have \(5\) different remainders: \(0,1,2,3,4.\) We have \(6\) distinct numbers. Therefore, by the pigeonhole principle, at least two of them have the same remainder. The difference of these two numbers has remainder \(0\) when divided by \(5,\) that is, it is divisible by \(5.\)

Example 2.

The cells of a \(3 \times 3\) array contain numbers \(-1, 0, 1.\) Prove that at least two of the eight sums on rows, columns and main diagonals are equal.

Solution.

Each of these \(8\) sums can take the following \(7\) values:

\[ – 3, – 2, – 1,0,1,2,3.\]

According to the pigeonhole principle, at least two sums must coincide.

Example 3.

Consider an equilateral triangle with side length \(a = 1.\) Prove that among any \(5\) points inside the equilateral triangle, there always exist two points that are within \(\large{\frac{1}{2}}\normalsize\) units of each other.

Solution.

The midlines of the equilateral triangle divide it into four regular triangles with side \(q = \large{\frac{1}{2}}\normalsize.\)

An equilateral triangle with 5 random points.
Figure 4.

By the pigeonhole principle, at least two of the five points will lie inside one of the four triangles.

It is known that the length of a line segment inside a triangle is less than the length of its longest side. Therefore the distance \(d\) between the two points inside the small triangle is less than \(q:\)

\[d \lt q = \frac{1}{2}.\]

Example 4.

A \(5 \times 6\) chessboard has 19 squares colored black. Prove that there exists a \(2 \times 2\) square in which at least three cells are colored black.

Solution.

We divide the rectangle into \(6\) equal parts, \(5\) cells each.

A 5x6 chessboard with 19 black squares
Figure 5.

By the generalized pigeonhole principle, there is a part of the chessboard with \(4\) black cells since

\[\left\lceil\frac{n}{m}\right\rceil = \left\lceil\frac{{19}}{{6}}\right\rceil = \left\lceil3\frac{1}{6}\right\rceil = 4.\]

Then the \(2 \times 2\) square in this part has either \(3\) or \(4\) cells colored black.

Example 5.

Prove that if \(7\) natural numbers are chosen at random, then the sum of three of them is divisible by \(3.\)

Solution.

When divided by \(3,\) the remainders can be equal to \(0,1,2.\) So, using the generalized pigeonhole principle, we find that

\[\left\lceil\frac{n}{m}\right\rceil = \left\lceil\frac{{7}}{{3}}\right\rceil = \left\lceil2\frac{1}{3}\right\rceil = 3.\]

This means that there are \(3\) numbers of \(7\) that have the same remainders. Denote this remainder by \(r.\) The sum of the three numbers has the combined remainder \(3r,\) which is divisible by \(3.\) Hence, these numbers are also divisible by \(3.\)

Example 6.

Prove that if the integers \(m\) and \(n\) are coprime, then there is a natural number \(k\) such that \(m^k – 1\) is divisible by \(n.\)

Solution.

Consider \(n + 1\) numbers

\[{{m^0} – 1,\;{m^1} – 1,\;{m^2} – 1,\; \ldots ,\;}\kern0pt{{m^n} – 1.}\]

By the pigeonhole principle, there are \(2\) numbers that have the same remainder when divided by \(n.\) Let these numbers be

\[{m^a} – 1 \text{ and } {m^b} – 1,\]

where \(a \lt b.\)

Then their difference

\[{\left( {{m^b} – 1} \right) – \left( {{m^a} – 1} \right) }={ {m^b} – {m^a} }={ {m^a}\left( {{m^{b – a}} – 1} \right)}\]

is also divisible by \(n.\) The first factor \(m^a\) is not divisible by \(n\) because \(m\) and \(n\) are coprime. Hence, the number \(m^k – 1 = m^{b – a} – 1\) is divisible by \(n.\)