Top

# Pigeonhole Principle

The word "pigeonhole" literally refers to the shelves in the form of square boxes or holes that were utilized to place pigeons earliar in the United States. In mathematics, there is a concept, inspired by such pigeonholes, known as pigeonhole principle which was introduced in 1834 by a German mathematician Peter Gustav Lejeune Dirichlet. On his name, this principle is also termed as Dirichlet principle.

Pigeonhole principle roughly states that if there are few boxes available; also, there are few objects that are greater than the total number of boxes and one needs to place objects in the given boxes, then at least one box must contain more than one such objects.

## Definition

The definition of pigeonhole principle is that:
If "$n$" number of pigeons or objects are to placed in "$k$" number of pigeonholes or boxes; where $k < n$, then there must be at least one pigeonhole or box which has more than one object.We can also define pigeonhole principle as:
If $n$ items are to be put in $k$ boxes, then there must be an empty hole if and only if there exists at least one hole containing more than one pigeon.

Pigeonhole principle gives rise to many useful, but simple and quite evident extensions. According to the more formal definition of an extension of this principle:

Let us suppose that $|A|$ and $|B|$ represent the total number of members in two finite sets $A$ and $B$ respectively, then there will be one-one correspondence, such that:
$f : A$ $\Rightarrow$ $B$ $\Leftrightarrow$ $|A| = |B|$
Generalized Pigeonhole Principle:
It states that when there are n pigeons to be placed into m pigeonholes, such that $n > m$ ; there will be one pigeonhole with at least $\frac{n}{k}$ pigeons.

## Proof

Proof of Generalized Pigeonhole Principle
In order to prove generalized pigeonhole principle, we shall use the method of induction. According to which we will assume the contradiction and prove it wrong.
Let us suppose that total "$n$" number of pigeons are to be put in "$m$" number of pigeonholes and $n > m$.

Let us assume that there is no pigeonhole with at least $\frac{n}{m}$ pigeons.

In this case, each and every pigeonhole will have less than $\frac{n}{m}$ pigeons.

Therefore, we have
Number of pigeons in each pigeonhole < $\frac{n}{m}$

Total number of pigeons < number of pigeonhole $x$ $\frac{n}{m}$

Total number of pigeons < $m$ $\times$ $\frac{n}{m}$

Total number of pigeons < $n$
But given that number of pigeons are strictly equal to n.
Which is a contradiction to our assumption.
Hence there exists at least one pigeonhole having at least $\frac{n}{m}$ pigeons.

This proves the generalized form of pigeonhole principle.

## Applications

Pigeonhole principle is widely applicable to many fields. It is fairly applied in computer science. It is quite useful in computer programming and in various algorithms. Pigeonhole principle plays a vital role in mathematical analysis also. It is used in different problems related to arithmetic, geometry, economics, finance etc. This principle is very commonly used in practical problems related to probability theory and statistics.

Not only in subjects related to mathematics and science, pigeonhole principle is applied to many other fields, such as:  in sports in order to choose the team members.

The extensions of pigeonhole principle are applied to many areas related to arts, like: geology, mining, geography etc.