In this post, we will go through a concept which is typically asked in logical puzzles and brain teasers. Pigeonhole principle may sound a little hard to understand if one just reads the principle, but once you understand the logic, it becomes extremely simple. Read this question before we begin:
Calvin has mixed socks of 4 different colors (Green, Blue, White, Black) in a box. For every color, he has 4 pairs. What is the minimum number of socks he must remove from the box to be sure of getting a matching pair of any color?
Now, the problem is simple. The number of pairs is not really important as we want to find a pair of any color. Lets say that he removes a sock and it is Green in color. Worst case, the next sock is of Blue color. The third sock that he removes is of White color and the fourth sock is Black. Things can’t get worse than this! The fourth sock that he removes will either be Green or Blue or White or Black and that will give Calvin a matching pair. Which color is it? Doesn’t matter! The question is asking us to find the minimum number to guarantee a pair.
People find this confusing. Some people say that he can draw two or three or four socks and they may be of the same color, and hence answer is 2 or 3 or 4. If he removes 2 or 3 or 4 socks, though there is a possibility of him getting a pair there is no guarantee that he will get a pair. People who are tuned to thinking in probability sense, start looking at this as a probability question but that’s not the question! Let us understand the principle from a conceptual point.
The pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item.
If you have five chocolates and four boxes to keep these five chocolates, there will be at least one box with more than one chocolates.
It is as simple as this. And a visual example for you to remember this which is also the name of the principle: Here there are n = 10 pigeons in m = 9 holes. Since 10 is greater than 9, the pigeonhole principle says that at least one hole has more than one pigeon.
This understanding helps us in answering questions that may appear difficult or implausible when you see them for the first time. Let us look at some of the typical questions based on Pigeonhole principle. Try the questions and then scroll down to see the answers!
Questions
Q.1 Raju has a bunch of dice in his drawer. He recalls that 5 of them are green, 6 of them are blue and 7 of them are red. He reaches in and grabs several without looking. How many does he have to grab, in order to ensure that 3 of them are the same color?
Q.2 What is the minimum number of people that must be in a family, so that it’s guaranteed that two of them have the same month of birth?
Q.3 How many students do you need in a school to guarantee that there are at least 2 students who have the same first two initials?
Q.4 Babu has 13 pairs of shoes thrown around in his closet. The light has gone out, and he is unable to determine which shoe is which. What is the minimum number of shoes he must remove in order to guarantee that he has a matching pair?
Q.5 A, B, C and D run for school president. There are students in the school and each student can vote for only one candidate. The person with the largest number of votes is the winner. If every student votes, what is the minimum number of votes needed to win the election?
Q.6 How many people should be present in a room so that we know that there is at least one pair who share the same birthday?
Answers:
Q.1 7. He needs to get three of the same color. The first six can be G-B-R-G-B-R and the seventh one will make sure that there are three of the same color.
Q.2 13. Imagine a family of 12 people where every person has his or her birthday in 12 different months. The 13th person of the family must share his or her birthday month with somebody!
Q.3 677. A to Z is 26 and we want first two initials. So we will have 26*26 = 676 combinations (AA, AB, …., ZY, ZZ). The 677th person will share his or her initials with someone from the group.
Q.4 14. Imagine a case where he gets all 13 different shoes. The 14th shoe will make a pair.
Q.5 51. As there are 201 students and four candidates, the best possible scenario from candidate point of view is getting almost equal votes. So if A B C D get 50 votes each, 200 votes are out and with one vote to go. This last or 51st vote will decide the winner. Hence, 51.
Q.6 367. Ah, did you make that 365+1 mistake? As there are 366 possibilities when it comes to a birthday, 367 people will make sure at least one pair.
Hope you have understood the Pigeonhole principle. If you have any queries, do leave them in the comments section. Happy learning! 🙂
A few useful links for IIFT, SNAP, NMAT, and CAT aspirants: IIFT Mocks | SNAP Mocks | NMAT Mocks | CAT Mocks | Facebook CAT group (for serious aspirants only)
