Pigeonhole Principle

Theory:-

let us say there are k boxes and we have to put k+1 pigeons in those boxes but the condition is one box can have at most one pigeon at a time.

So in order to put all the pigeons in the boxes, there is at least one box that has more than one pigeon.

Examples

1.  In a group of 367 people, there must be at least two people such that their birthday is the same.

2. In a group of 27 words, there must be at least two words such that their starting letter is the same.

Why these given examples are true. You please think and tell us.

 

Formal definition:-

If N objects are placed in K boxes then there is at least one box that will contain  \left \lceil N/K \right \rceil objects.

This is the Pigeonhole Principle. 

 Example:1

What is the minimum no. of students must be in the class to guarantee that at least two students have the same grades in the final exam if the exam is having a total of 6 grades?

Solution:-

let's breakdown the question: They are asking about the total number of student so that is our N and  K is our total grade. 

So according to the question:

\left \lceil N/K \right \rceil =2

\left \lceil N/6 \right \rceil =2

Now any number such 'N' that  6< N< 11 , the equation is satisfied.

They are asking for minimum So N= 7 

 

Example 2:-

What is minimum no. of student register in a class to be sure that at least 11 students will get receive the same grade if total available grades are 5?

Solution:- 

It's a simple just question :

\left \lceil N/K \right \rceil = 11

\left \lceil N/5\right \rceil = 11

Now N can have values like : 56 < N< 60

The minimum one is 56

 

 

 

0Comment