The Pigeonhole Principle

One of the famous (although often neglected in the instructional program) problem- solving techniques is to consider the pigeonhole principle which is a powerful tool used in combinatorial math. In its simplest form, the pigeonhole principle states that if more than n pigeons are placed into n pigeonholes, some pigeonhole must contain more than one pigeon. If you have k+1 objects that must be put into k holes, then there will be at least one hole with 2 or more objects in it. While the principle is evident, its implications are astounding. The reason is that the principle proves the existence (or impossibility) of a particular phenomenon.

Here is one illustration of the pigeonhole principle at work:

There are 50 teachers’ letterboxes in the school’s general office. One day the letter carrier delivers 151 pieces of mail for the teachers. After all the letters have been distributed, one mailbox has more letters than any other mailbox. What is the smallest number of letters it can have?

Some have a tendency to “fumble around” aimlessly with this sort of problem, usually not knowing where to start. Sometimes, guess and test may work here. However, the advisable approach for a problem of this sort is to consider extremes. Naturally, it is possible for one teacher to get all the delivered mail, but this is not guaranteed.

To best assess this situation, we shall consider the extreme case, where the mail is as evenly distributed as possible. This would have each teacher receiving three pieces of mail with the exception of one teacher, who would have to receive the 151st piece of mail. Therefore, the least number of letters that the box with the most letters received is 4.

By the pigeonhole principle, there were 50 3-packs of letters for the 50 boxes. The 151st letter had to be placed into one of those 50 boxes.

Let’s see more applications how it can be used.

If you have 10 black socks and 10 white socks, and you are picking socks randomly, you will only need to pick three to find a matching pair.

The three socks can be one of two colors. By the pigeonhole principle, at least two must be of the same color.

Another way of seeing this is by thinking sock by sock. If the second sock matches the first, then we are done. Otherwise, pick the third sock. Now the first two socks already cover both color cases. The third sock must be one of those and form a matching pair.

If you pick five numbers from the integers 1 to 8, then two of them must add up to nine.

Every number can be paired with another to sum to nine. In all, there are four such pairs: the numbers 1 and 8, 2 and 7, 3 and 6, and lastly 4 and 5.

Each of the five numbers belongs to one of those four pairs. By the pigeonhole principle, two of the numbers must be from the same pair–which by construction sums to 9.