Mathematics Exam  >  Mathematics Notes  >  Mathematics for IIT JAM, GATE, CSIR NET, UGC NET  >  Pigeonhole Principle - Algebra, CSIR-NET Mathematical Sciences

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:

If "nn" 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 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|

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

The document Pigeonhole Principle - Algebra, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET is a part of the Mathematics Course Mathematics for IIT JAM, GATE, CSIR NET, UGC NET.
All you need of Mathematics at this link: Mathematics
556 videos|198 docs

FAQs on Pigeonhole Principle - Algebra, CSIR-NET Mathematical Sciences - Mathematics for IIT JAM, GATE, CSIR NET, UGC NET

1. What is the Pigeon-Hole Principle in algebra?
Ans. The Pigeon-Hole Principle is a fundamental concept in mathematics that states that if you have more pigeons than pigeonholes, then at least one pigeonhole must contain more than one pigeon. In algebra, this principle is often used to prove certain results or establish the existence of solutions.
2. How does the Pigeon-Hole Principle apply to CSIR-NET Mathematical Sciences exam?
Ans. The Pigeon-Hole Principle is highly relevant to the CSIR-NET Mathematical Sciences exam as it is a powerful tool for solving problems related to counting, combinatorics, and probability. Many questions in the exam may require the application of this principle to arrive at the correct answer.
3. Can you provide an example of how the Pigeon-Hole Principle is used in algebra?
Ans. Certainly! Let's consider an example: If there are 13 people in a room, then there must be at least two people who were born in the same month. This can be proved using the Pigeon-Hole Principle by considering the 12 months as pigeonholes and the 13 people as pigeons. Since there are more pigeons than pigeonholes, at least one month must have more than one person born in it.
4. How can the Pigeon-Hole Principle be used in the CSIR-NET Mathematical Sciences exam to solve problems?
Ans. To apply the Pigeon-Hole Principle in the exam, you need to identify a situation where there are more objects to be distributed than the number of options available for distribution. By recognizing this, you can conclude that at least two objects must be assigned to the same option. This can then be used to prove a result, find a solution, or eliminate incorrect options in multiple-choice questions.
5. Can the Pigeon-Hole Principle be extended to more than two objects and options?
Ans. Yes, the Pigeon-Hole Principle can be extended to any number of objects and options. The principle remains the same - if you have more objects than options, then at least one option must have more than one object assigned to it. This extension is particularly useful in solving complex problems involving permutations, combinations, or distributions.
556 videos|198 docs
Download as PDF
Explore Courses for Mathematics exam
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

Exam

,

practice quizzes

,

CSIR-NET Mathematical Sciences | Mathematics for IIT JAM

,

UGC NET

,

Sample Paper

,

Previous Year Questions with Solutions

,

CSIR NET

,

Important questions

,

CSIR NET

,

Pigeonhole Principle - Algebra

,

GATE

,

CSIR-NET Mathematical Sciences | Mathematics for IIT JAM

,

GATE

,

UGC NET

,

mock tests for examination

,

pdf

,

MCQs

,

CSIR NET

,

UGC NET

,

study material

,

Pigeonhole Principle - Algebra

,

Free

,

video lectures

,

Extra Questions

,

shortcuts and tricks

,

GATE

,

Semester Notes

,

CSIR-NET Mathematical Sciences | Mathematics for IIT JAM

,

Pigeonhole Principle - Algebra

,

past year papers

,

Viva Questions

,

Summary

,

ppt

,

Objective type Questions

;