Illinois State University Mathematics Department

 MAT 305: Combinatorics Topics for K-8 Teachers

### The Pigeonhole Principle

An Initial Problem
Generalizing the Principle
Another Pigeonhole Principle Problem

We will first explore a problem situation designed to illustrate the Pigeonhole Principle and then use that illustration to discuss the principle.

How many students would be required to place soda orders, one soda per student, in order to insure that at least one of the six listed sodas would be ordered by at least two students?

The phrase "worst-case scenario" helps us determine the maximum number of students that could place orders without meeting the condition and then consider what must be done from there to meet the condition.

Next, consider two variables in the original problem situation: (1) the number of sodas available, and (2) the number of repeat orders desired. We can use n (here, n=6) to represent the first value and k (here, k=2) to represent the second. You are challenged to use n and k to write a statement that characterizes the principle used to solve the problem with these variables in place.

Does the following statement describe the principle behind the solution to the original problem, using the context of boxes and pigeons? Is so, how? If not, why not?

When placing pigeons into n boxes, the number of pigeons required to insure that at least one of the boxes has at least two pigeons is n+1 pigeons.

We may generate similar statements to describe the more general case with n boxes and at least k pigeons in one of the boxes. You may be asked to write and solve a problem, different from the sodas-and-students context, with which to test your general statements. Here are some sample problems from other students. Are they all accurate?

We'll exchange your problems and solve them. We'll use any questions to help address misunderstandings about the Pigeonhole Principle.

Here is another problem we're likely to explore for which we can apply the pigeonhole principle:

We have 10 boxes labeled 1 through 10 into which we place pennies. How many pennies are required to insure that at least one box contains at least as many pennies as the label on the box?

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