What is the Pigeon Hole Principle?

The pigeonhole principle is a straightforward but elegant and valuable concept.

Introduction

If all the pigeons fly into a pigeonhole and there are more pigeons than holes in a set A of pigeons and a set B of pigeonholes, then one of the pigeonholes must contain more than one pigeon.

Mathematically stated as:

if n items are put into m containers, with n > m, then at least one container must contain more than one item.

History

Although the pigeonhole principle first appeared in a text attributed to Jean Leurechon in 1624, it is most usually referred to as Dirichlet’s box principle or Dirichlet’s drawer principle since Peter Gustav Lejeune Dirichlet treated the idea in 1834 under the term Schubfachprinzip (“drawer principle” or “shelf principle”).

There is an indirect reference to the pigeonhole principle in George Cantor’s investigations of countability:

For practical reasons let us illustrate the finite case by imagining a classroom with 100 seats. Filled with students, one can make an inference about the size of the set of students in relation to size of the set of seats. If seats are vacant, the set of seats is larger than the set of students. If no seats are vacant and some students are standing, the size of the set of students is larger than that of seats, and so on.- Excerpt, "The Nature of Infinity and Beyond" by Veisdal (2018)

Definition

A formal definition includes thinking of the pigeon principle as a function f from domain P → PH, where pigeon n flies into pigeonhole f(n), as is shown below:

Figure 1.: More pigeons than pigeonholes |n| > |f(n)|. 2: Same number of pigeons as pigeonholes |n| = |f(n)|. 3: More pigeonholes than pigeons |n| < |f(n)|

Three types of functions that may be mapped from a domain (pigeons) to a codomain (pigeonholes) are shown in the three cases:

Case 1: If |n| exceeds |f(n)|, the function is a non-injective surjective function (not a bijection)
Case 2: In this case, if |n|= |f(n)|, the function is an injective surjective function (bijection)
Case 3:If |n| < |f(n)|, the function is an injective non-surjective function (not a bijection).

The pigeonhole principle’s core is shown by Case A, which states that if you arrange n things into m containers and n > m, at least one container must contain more than one item. Therefore, the function f that maps pigeons into pigeonholes is a surjective function.

Proof of Pigeon hole principle :
Base case: let there be just one pigeonhole, i.e. m=1. If we seek to distribute n>1 items among this one pigeonhole, then it follows that this pigeonhole contains n/m=n items.
Induction step: Now let there be m+1 pigeonholes, and suppose we want to distribute n>m+1 items among these pigeonholes. This case reduces to needing to distribute one item in one pigeonhole, and n−1 items among m+1−1=m pigeonholes, for which we know the proposition to hold true (see the base case, above.) Note that since n>m+1 , it follows that n−1>m, so the case is the exact same.

Examples and Uses

This idea might seem so obvious that it doesn’t even need its own name, yet it is quite common in math and computer science and has a lot of unanticipated, far-reaching effects. Realizing which parts of your word problem should be viewed as pigeons and which as holes might be difficult when employing the pigeonhole concept. The most frequent scenario is when you’re trying to prove that two things (or mathematical constructions) have a certain attribute in common. One may consider pigeons as things and holes as characteristics.

Think about the following questions:

1. Does there exist two people in Delhi with the same number of hair on their heads?
2. Consider all of your socks are red, yellow, and blue. The room is completely dark, so you can’t see the color of the socks as you pull them out of your sock drawer. How many socks must you pull in order to ensure that you have a matching pair when you leave your room?

At first glance, it appears that the solutions to questions may take very different approaches but these can be solved with the help of the pigeonhole principle. Let’s examine how our two introductory questions fit into the pigeonhole principle.

To answer the first question, we need to figure out what are the pigeons and what are the holes? The average human head contains 100,000–150,000 hair follicles, and even the hairiest person won’t have more than 500,000. This indicates that there are only, at most, 500,000 possible combinations of how many hairs a person may have. For example, if someone had precisely 1 hair, another had exactly 2 hairs, etc. up to 500,000, that only leaves room for 500,000 different combinations of hair counts. Meanwhile, Delhi has a population of about 19 million. We may infer that there must be at least two Delhi residents who have the exact same number of hairs on their heads since there aren’t enough holes (or possible hair counts) for all of the pigeons (citizens of Delhi).

Mathematically:

Proof of first part:
Let A be the set of all Delhites heads and B = {0,1,2,3,4, ..., 1000000} be the number of hairs one can have on ones' head. Let f be a function that maps A → B, for which f(x) equals the number of hairs on the head of x. Since |A|>|B|, the pigeonhole principle asserts that f is not injective. Thus there are two Delhites x and y for whom f(x) = f(y), meaning they have the same number of hairs on their heads.

Similarly, the second question’s solution can thought be of as we have 3 colours, and our objective is to determine the least number of socks that share at least 2 colours. Sounds recognisable? Consider the socks as pigeons and the colours as holes. In the same way, if we try to fit 4 pigeons into 3 holes, at least 2 pigeons must share a hole, if we choose 4 socks, at least 2 of them must share a colour.

The pigeon-hole principle is simple, beautiful and elegant, it shows how simple observations can be used for complex problems.