Pigeonhole Principle

Hello Readers

Hope you are doing well.

Today i am writing on very important mathematical tool based on combinatorics that is pigeonhole principle.

What actually `Pigeonhole‘ word refers?

It refers to the square boxes or holes utilized to place pigeons in the united states. pigeons2

Inspiring by this concept,  a mathematical principle was introduced in  1834 by a German mathematician Peter Gustav Lejeune Dirichlet.

In easy way we can understand his principle as:

The idea is basically if you imagine 4 pigeons inside 3 holes. Can it be done? Of course yes, No matter how these pigeons are placed inside these holes but at least one holes out of 3 must contain more than 1 pigeons out of 4.

 

With this roughly idea, now we are ready to understand definition. Consider holes as boxes and pigeons as objects.

Definition:

Suppose we are having few boxes ( say m) and few objects (say n) such that total number of objects is greater than or equal to total number of boxes i.e. m<n. Now if we want to put these objects inside the boxes then at least one box must contain more than one objects.

This principle can also be stated as:

If n objects are needed to be put in m boxes, then there must be an empty box if and only if there exists at least one box containing more than one objects.

Set theoretic definition: 

This definition gives the extension of Pigeonhole principle..

Let A and B are two finite sets having m and n elements respectively. You can imagine A as set of boxes/holes and B as set of  objects/pigeons. Then there will be one-one correspondence between boxes and objects such that f: A → B ⇔ m=n.

Generalized definition: 

If n objects are to be placed in m boxes where m<n then there will be one box with at least n/m objects.

Proof: By contrary, Let us assume that there are m boxes and n objects such that m<n and

there is no box with at least n/m objects.

⇒ each box will have less than n/m objects.

⇒ no of objects in each box < n ⁄m

⇒ Total number of objects in m boxes < m×(n/m)

⇒ n<n (as given that number of pigeons are strictly equal to n)

which is a contradiction.

Hence our assumption is wrong.

⇒ There will be one box with at least n/m objects.



Applications:

  1. Computer Programming
  2. Mathematical Analysis
  3. Probability theory & Statistics
  4. Economics
  5. Finance
  6. Geometry

Examples:  

We can understand the following examples with the simplest form of pigeonhole principle as:

If n + 1 objects are put into n boxes, then at least one box contains two or more objects.

e.g.

  1. If we have a sequence of 27 words, that can start with 26 different English letters, so by pigeonhole principle, two of the words must start with the same letter.
  2. Among 8 people there are two who have their birthdays in the same day.
  3. If you pick five cards from a standard deck of 52 cards, then at least two will be of the same suit.
  4.  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.
  5.  If a number of people in a party handshake with one another, then according to pigeonhole principle, there must exist two people who shake hands with same people.

Hope this post is helpful to understand the pigeonhole principle

If Yes then please like and comment.

Thank you

Namita Tiwari

One thought on “Pigeonhole Principle

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s