The pigeonhole principle

The pigeonhole principle (also called Dirichlet's box principle) is one of those simple ideas that sound obvious but are very useful in practice. Let's consider this principle in detail.

What is this principle about?

Suppose we have 4 pigeonholes (represented here by cages) and 5 pigeons, each of which needs to be put into one of the holes:

The pigeonhole principle states that after we put each pigeon in a pigeonhole, there must be at least one pigeonhole containing more than one pigeon:

Let's formulate this principle in more general terms: if we have $N$ pigeons distributed among $M$ pigeonholes, and $N>M$, there must be at least two pigeons that share a hole.

Of course, the scope of the principle is not limited to literal pigeons in holes. It can be abstracted to any situation that involves sorting things into groups:

This principle seems trivial, but it turns out to have plenty of practical applications.

Applying the pigeonhole principle to geometry

Let's consider the following problem: $$\text{Suppose we have an equilateral triangle with side 1 and there are 5 points inside it. } \\ \\ \text{Prove that the distance between some two of them is less than } \dfrac{1}{2}.$$

How can we prove this statement? To use the pigeonhole principle, we'll need to define a "pigeon" and a "pigeonhole" in this situation. Let's start by drawing 3 line segments that connect the midpoints of opposite sides of the triangle:

These line segments divide the triangle into four equilateral triangles with sides equal to $\frac{1}{2}$. In this case, the smaller triangles are "pigeonholes", and the points are "pigeons". Thus, according to the pigeonhole principle, at least two points will lie in the same triangle. The distance between these two points will be less than $\frac{1}{2}$, since a line segment with length $\ge \frac{1}{2}$ will not fit inside a small triangle.

Using the pigeonhole principle, we have successfully solved the problem.

Applying the pigeonhole principle to number theory

Suppose we want to solve the following problem:

$$\text{Prove that out of any three integers, you can choose two, the sum of which is even. }$$Let's use the pigeonhole principle again. All integers are divided into two parities: even numbers and odd numbers. It is impossible to distribute three numbers into two classes so that only one number falls into each class. This means that, among any three integers, there must be two with the same parity. Whether we have two even numbers or two odd numbers, the sum of those two must be even.

Applying the pigeonhole principle to arithmetic

Consider the following problem:

$$\text{One hundred people are sitting at a round table, and more than half of them are men.} \\ \text{ Prove that two men are sitting opposite each other. }$$Let's divide all the people sitting at the table into 50 pairs of people sitting opposite each other. So we have 50 pairs (pigeonholes), in which we need to seat at least 51 men (pigeons). From the pigeonhole principle, it follows that one of these pairs will consist of two men.

Conclusion

In this topic, we learned one of the most versatile ideas in mathematics: the pigeonhole principle. This is a fairly simple statement that can help you solve many mathematical problems. The mathematical formulation of the pigeonhole principle says that, if there are $n + 1$ or more pigeons in $n$ pigeonholes, then at least one pigeonhole will contain more than one pigeon. If you remember this principle, you can substitute whatever mathematical object you happen to be working with and use it to solve a broad range of problems.