Did you know that in a crowd of 367 people, there will be at least two people with the same birthday?
How do we know for sure without having to ask every single person?
Because of the Pigeonhole Principle!
Let's understand it today!
Before studying the pigeonhole principle, first read this -
Consider there is a flock of 10 pigeons that flies into 9 pigeonholes to rest happily. As there are 10 pigeons and just 9 pigeonholes, at least one of these 9 pigeonholes must have at least two pigeons in it.
This demonstrates a general principle called the pigeonhole principle, which states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with at least two pigeons in it.
Naive form of pigeon hole principle
If more than n objects are placed into n boxes, then at least one box must contain more than one object.
An example problem
(Try it yourself first before looking at the answer)
Answer -
Pick two socks - not sure if it is a matching pair
Pick three socks - not sure if it is a matching pair
Pick four socks - sure with one matching pair
Thus, the minimum no of socks to be taken to be sure that they will include a matching pair is 4.
Another problem
(Try it yourself first before looking at the answer)
Answer
No of colors (pigeons) = 3
No of marbles of the same color required (pigeonholes) = 4
If we choose 9 marbles in the extreme case we might get 3 marbles of all the 3 colors.
Therefore if we take 10 marbles we are guaranteed that we get 4 marbles of the same color.
Mathematical form of pigeon hole principle
If n objects are to be placed in k boxes then at least one box will have ⌈ n/k ⌉ where ⌈ . ⌉ denotes the ceil function.
Solution using this approach
Now solving the previous marbles problem using this approach -
No of marbles to be picked (n) =?
No of colors (k) = 3
We get at least 4 marbles of the same color i.e
⌈ n/k ⌉ > 4
⌈ n/3 ⌉ > 4
⇒ n=10
Another Problem
(Try it yourself first before looking at the answer)
Answer
No of months (k) = 12
Minimum no of students to be picked (n) =?
At least three of them are born in the same month i.e
⌈ n/k ⌉ > 3
⌈ n/12 ⌉ > 3
⇒ n=25
Observations
As of now, you could see these things clearly -
(1) In any group of 27 English words, there must be at least two words that begin with the same letter, because there are 26 letters in the English alphabet.
(2) Among any set of 21 decimal digits, there must be 3 that are the same. As here 21 objects are distributed into 10 boxes, one box must have ⌈ 21/10 ⌉ = ⌈ 2.1 ⌉ = 3 elements.
(3) If you pick five cards from a standard deck of 52 cards, then at least two will be of the same suit.
(4) If you pick five numbers from the integers 1 to 8, then two of them must add up to nine.
(5) If 51 numbers are chosen from the integers between 1 and 100 inclusively, there exists at least one pair of 2 numbers such that they are consecutive.
... etc, etc
Strong form of the pigeonhole principle
Let q1,q2,...,qn be positive integers.
If q1+q2+...+qn– n+1 objects are put into n boxes, then either the 1st box contains at least q1 objects or the 2nd box contains at least q2 objects,..., the nth box contains at least qn objects.
Example problem
(Try it yourself before looking at the answer)
Answer
We can directly apply the formula here
q1 =10, q2 =8, q3 =6, q4 =4 and n=4
Therefore the minimum number of students required to ensure a department club to be formed is
10 + 8 + 6 + 4 – 4 + 1 = 25
(This means if any 25 students are taken from the computer science department it is guaranteed that a student club is formed)
Final problem
Solution
In this problem, we cannot apply the pigeonhole principle directly.
We will neglect the blue and yellow marbles first as they are less than 9.
But we are picking randomly so we include it after we apply the pigeonhole principle.
i.e 9 red + 9 white + 9 black – 3 + 1 = 25
Since we are picking randomly so we can get all the blue and yellow marbles before the above 25 balls.
Therefore we add 6 blue + 8 yellow + 25 = 39
We can conclude that in order to pick 9 marbles of the same color randomly, one has to pick 39 marbles from the bag.
Conclusion
This is the end of the blog. Make sure to give a follow if you liked this.
Thanks💛