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.

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

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.

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:

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.

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.