The Pigeonhole Principle
The Pigeonhole principle says that:
If there are ’n’ items that are to be put into ‘m’ containers and if n>m, (no. of items > containers), atleast one of the containers will more than 1 item
In terms of pigeons: If you insist on putting N+1 or more pigeons into N pigeon holes, atleast one hole will contain more than 1 pigeon
Suppose you have 3 boxes and 4 balls. There are a lot of ways in which you can place the 4 balls in the 3 boxes. Whichever way you arrange the balls, you cannot deny one fact: Atleast one of the boxes will contain more than one ball. You can try it out for yourself if you wish.
The reason as to why this statement works is quite intuitive and simple. Let there be M pigeons and N pigeonholes (M > N)
If you start with placing one pigeon in each hole, at the end, you will be left with (N-M) pigeons that are unmatched. This is because the number of pigeons are more than the holes available. Hence, the remaining (N-M) will have to go into one of the already filled holes. This leads to the fact that atleast one hole will contain more than one pigeon
A Few Examples
Example 1:
The city of Leningrad has 5 million people. Show that at least 2 people from Leningrad must have the same number of hair in their heads, if it is known that no person has more than one million hair on their head
The most important thing in such problems is to identify which is the pigeon and which is the pigeonhole. Once this is done, half the problem is solved.
Here, the people of Leningrad are the “pigeons”, which are 5 million in number.
Since no person can have more than one million hair on their head, each person can have 0 to 1 million hair on his head. Thus, the total possibilities are 1,000,001. These are the “pigeonholes”, which are 1,000,001 in number
Since pigeons are greater than pigeonholes, we can conclude that atleast 2 people will have the same number of hairs on their head
Example 2:
A drawer consists of a mixture of Black and Red socks. What is the minimum number of socks you need to pull out so that you have atleast one pair of the same color?
This problem does not require usage of the pigeonhole principle exactly and can be solved using a little bit of common sense
Common sense and intuition will tell you that the answer is 3. Why?
If you pick 2 socks, there are 3 possibilities: Both red (or) both black (or) One of each color.
When you pick a 3rd sock, it will be either of the 2 colors. Automatically a pair will be formed in either of the 3 cases, as is evident from the bellow table:
Still, if you insist on using the pigeonhole principle just because you know it, here you go: The number of pigeonholes here are 2 (we need 2 of same color). Hence, we need >2 i.e 3 socks to make sure we have a pair of same color
The answer 3 holds for any number of socks, whether it is 10 or 100 or 1 million as long as only 2 colors are there.
If suppose there were 3 colors of socks: Black, Red & White. In this case, how many socks would need to pull out to make sure you have atleast one pair with same colour? I leave it to you to figure it out
A Slight Variation
A slight variant of the pigeonhole principle deals with the sum of numbers and their averages:
If the sum of n or more numbers is equal to S, amongst these there must be one or more numbers not greater than S/n and also one or more numbers not less than S/n
In short, it means that not all number can be above the average or all below the average. There must be atleast one number that is greater than or less than the average
For example, in a class, the average marks of the students is 50. This implies that, there must be atleast one student whose mark is greater than 50 or less than 50
The proof is quite simple. If all the numbers are greater than S/n, then their sum will be greater than S, which is a contradiction. (Same for the opposite case — if all numbers are < S/n, the sum will be less than S, a contradiction)
Suppose 5 workers earn a total of 1,000 dollars. Each one wants to buy a television worth 225 dollars. Will all of them they be able to buy it?
Turns out no. The average wage is 1000/5 = 200 dollars. Applying the above principle, we can say that the salary of atleast 1 of the workers must be less than 200 dollars. Hence, such a worker must wait for another month before being able to buy a television
Thanks for reading!!!
References
Originally published at http://infinitesimallysmallcom.wordpress.com on May 12, 2021.
