Pigeonhole Principle - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

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.

Definition

The definition of pigeonhole principle is that:

We can also define pigeonhole principle as:

If nn items are to be put in kk 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 ⇒ B ⇔ |A|=|B|

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 n/m pigeons.

In this case, each and every pigeonhole will have less than n/m pigeons

Therefore, we have

Number of pigeons in each pigeonhole 

Total number of pigeons < number of pigeonhole 

Total number of pigeons

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 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.

Examples

There are many examples which use pigeonhole principle. Few of the examples are given below:

1) Golf: Let us suppose that there are 8 balls and 7 holes. If balls are to be put in different holes, then at least one hole must have more than one ball.

2) Handshake: If a number of people does handshake with one another, then according to pigeonhole principle, there must exist two people who shake hanks with same people.

3) Birthday: Let us consider that n people are chosen at random from a group of people. Then, in order to find the probability of having same birthday, pigeonhole principle is applied. It says that at least two people will have same birthday.

4) Marble picking: Consider that we have a mixture of different color marbles in a jar. In order to find at least how many marbles will be picked before two same color marbles are guaranteed. It can be calculated using pigeonhole principle assuming one pigeonhole per color will be assumed.