Suppose you and a couple of people were shipwrecked in an island (which, for dramatic effect, we call Gilligan’s Island). Assume that none of you were friends with each other in the beginning, but over time you all managed to be friends with at least one other person. What is the probability that two of you have the same number of friends? Now suppose that the initial number of people shipwrecked, including you is 60, what is the least number of people whose surnames start with the same letter?
This kind of problem is an instance of what is known as the Pigeonhole Principle.
If pigeons fly into pigeonholes, where , then one pigeonhole has at least 2 or more pigeons in it.
This principle is so intuitive that even a child will agree with you on this. Now the question is why are the 2 problems in the previous paragraph an instance of the Pigeonhole Principle?
In the first problem, let be the number of people shipwrecked in Gilligan’s Island. Then the maximum number of friends anyone can have is therefore and the minimum number of friends anyone can have is 1 ( each person has at least one friend). Imagine the pigeonholes to be the possible number of friends anyone can have. The number of such pigeonholes is . By assigning each person to a pigeonhole, you are in effect assigning the number of friends a person has. Since , by the Pigeonhole Principle, one pigeonhole has at least 2 or more pigeons ( or at least 2 people have the same number of friends). Therefore, the probability of at least 2 persons having the same number of friends is equal to 1.
In general, the Pigeonhole Principle can be stated as
If pigeons fly into pigeonholes such that , for some integer , then there is a pigeonhole with at least pigeons in it.
For example, suppose pigeons flying into pigeonholes. By letting , we have and by the generalized Pigeonhole Principle, there is one pigeonhole that has at least pigeons in it.
Going back to the second problem, we know that there are only 26 letters in the English alphabet. If we imagine the letters to be pigeonholes and the people to be pigeons, then by the generalized Pigeonhole Principle, we have
Solving for the minimum integer that satisfies this, we get . This means that there are at least persons whose surnames begin with the same letter.
Now try this problem for size. Suppose you have 20 black socks and 20 white socks in a dark room. Since you cannot see clearly in the dark, you decided to pick any sock at random. What is the minimum number of socks you need to pick in order to get a pair with the same color?