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 > m, then at least one hole must contain more than one pigeon. Respectively, if there are more holes than pigeons (n < m), 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 {\frac{n}{m}} \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 {\frac{n}{m}} \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.

See solved problems on Page 2.

Page 1 Page 2