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.

In this page below, we shall go ahead and learn about pigeonhole principle and its applications.

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.

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:

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.

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.

Pigeonhole principle is widely applicable to many fields. It is fairly applied in

Not only in subjects related to mathematics and science, pigeonhole principle is applied to many other fields, such as: in

The extensions of pigeonhole principle are applied to many areas related to arts, like:

Related Topics | |

Math Help Online | Online Math Tutor |