The pigeonhole principle

Picture a scenario where you possess two boxes and randomly place three identical socks into them, oblivious of their identities. The situation is such that two of these socks are a matching pair, while the third is a singleton. Could it ever be possible that the two matching socks end up in the same box? This intriguing phenomenon is known as the pigeonhole principle.

Could it ever be possible that the matching pair ends up in one box and the singleton ends up in another? Alas, this isn't guaranteed by the principle; it only guarantees that if we have more items than containers and distribute them randomly, at least one container must contain more than one item. Formally:

If $n+1$ or more objects are placed into $n$ boxes, then at least one box must contain more than one object.

This principle is fundamental in combinatorics and discrete mathematics. It is used to prove the existence of repetitions, collisions, or certain outcomes in various scenarios where objects are allocated to limited spaces.

Proof:  Assume that our proposition is false, i.e., $n+1$ objects can be placed into $n$ boxes and no box would contain more than one object. For the second fact to be true, the number of objects should be $n$, which is a contradiction to the given fact that there are $n+1$ objects.

Generalized pigeonhole principle#

If $n$ objects are distributed into $m$ holes, then at least one hole must contain at least $\lceil \frac{n}{m} \rceil$ objects.

Note: The terms “holes” and “pigeonholes” are used interchangeably throughout this blog.

Fun problems#

Let's go through some interesting problems solved using this principle.

Deck of cards:  If we pick 5 cards from a standard deck of 52 cards, we’re guaranteed to have at least two of the same suit.

There are 13 cards belonging to 4 different suits. So the 5 cards we’ve picked must belong to these 4 suits. By the pigeonhole principle, 2 or more must belong to the same suit.

Socks problem: If we have 10 black socks and 10 white socks, picking up just 3 socks guarantees us a pair.

Imagine there are two holes, each containing socks of a single color. Therefore, picking 3 socks from either hole will ensure a matching pair.

Rolling a die: How many times should we roll a die to get the same number twice?

There are 6 faces on a die. Rolling it 7 times would guarantee we get a repeated number.

The elevator problem: 12 people enter an elevator that goes to 10 floors. How many people will go to the same floor?

The 10 floors can be considered pigeonholes. As$\lceil \frac{12}{10} \rceil=2$, at least 2 of them get off on the same floor.

Application in graph theory#

Consider the following statement:

Prove that in any simple graph containing a minimum of 2 vertices, there must exist at least 2 vertices with the same degree.

Proof#

Consider a connected graph with $n$ vertices. The degree of any vertex has a  range of $0, 1, \dots, n-1$. Also, there can never be a vertex with $n-1$ degrees and another vertex of 0 degrees because these two need to be adjacent to meet the condition of $n-1$ degrees. So the range of degrees can either $\{ 1, 2, \dots, n-1\}$ or $\{ 0, 1, 2, \dots, n-2\}$, and both sets have $n-1$ elements. There are $n$ vertices, so at least two would have the same degree.

Conclusion#

This blog introduced us to the very interesting pigeonhole principle and its generalized form. We also discussed and solved some fun problems using this principle. Also, we were introduced to an interesting theorem of graph theory, which used this principle in its proof.

If you want to learn more about the pigeonhole principle, look no further! Check out the exciting new course Basic Mathematical Logic available now on the Educative platform.