THE DEAN'S COLUMN
The Pigeonhole Principle
By Dr. Alfred S. Posamentier
One of the famous problem-solving techniques is to consider the pigeonhole principle. This often-neglected way of thinking is an important technique in the instructional program. In its simplest form the pigeonhole principle states that if you have k+1 objects that must be put into k holes, then there will be one hole with 2 or more objects in it. This may sound confusing to the average reader, but it really should not be. It simply formalizes something that many adults might find obvious, but youngsters may not be aware of. Yet it is an important part of the logical training that we are obligated to teach students at various grade levels. Here is one illustration of the pigeonhole principle at work. Present your students with this problem to see how they will approach it.
There are 50 teacher’s 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?
Students have a tendency to “fumble around” aimlessly with this sort of problem, usually not knowing where to start. Sometimes, guess and test may work. 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 3 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 fifty 3-packs of letters for the fifty boxes. The 151st letter had to be placed into one of those 50 boxes.
Here are some other applications of the pigeonhole principle.
One selects 5 cards from a deck of playing cards (26 black and 26 red). Explain why there must be at least 3 cards of the same color.
For a set of 27 different odd numbers, each of which is less than 100, explain why there must be at least two numbers whose sum is 102.
Your students may want to try to find other problems that use the pigeonhole principle. This sort of reasoning is not reserved for mathematics alone. We use this type of reasoning in everyday life situations as well.#
Dr. Alfred S. Posamentier is Dean of the School of Education at City College of NY, author of over 40 books on math including Math Wonders to Inspire Teachers and Students (ASCD, 2003) and Math Charmers: Tantilizing Tidbits for the Mind (Prometheus, 2003), and member of the NYS Standards Committee on Math.
