Illinois State University Mathematics Department

 MAT 305: Combinatorics Topics for K-8 Teachers

### Review: Pigeonhole Principle

We used the Pigeonhole Principle (PHP) to solve a problem about students buying sodas at Blaise's Bistro and solved a problem involving the distribution of pennies into 10 labeled boxes. What key components of your solution strategies were common to your solutions? How can we generalize even further the Pigeonhole Principle?

Hint: Consider the pennies-and-boxes problem. What if the box labels were not consecutive integers 0 through 9?). Compare your response.

 Syllabus Grades & Grading Content Notes Session Outlines Assignments and Problem Sets Tests and Quizzes

The pigeonhole principle relies on filling existing spaces (pigeonholes, boxes, envelopes, and the like) with items (pigeons, coins, letters, and so on) to the point where all spaces are just one item short of being full. At this point, no matter where the next item is placed, we get a full box. The variables here are the number of spaces to fill and the number of items required in each space to assure that space is full.

A generalization of the situations we have considered is the following:

Let n represent the number of spaces to fill and use to represent the number of items needed for each of the n spaces to be considered full. Then to reach the point where each of the n spaces are just one item short of being full, we need this many items: The next item we add, no matter where we put it, will create a full space. Therefore, the number of items needed to assure that at least one of the n spaces is full is .