# The Pigeonhole Principle

The Pigeonhole Principle (or Dirichlet drawer principle)

If k + 1 or more objects are placed into k containers, then there is at least one container with two or more of the objects in it.

Example 1: True or False, if there were 32 people who all had their birthdays during the month of January, at least two of the people would have the same birthday.

Solution

Example 2: How many people must be in a group before it is certain that at least one pair were born on the same day of the week?

Solution

Example 3: In a local high school district, there are eight high schools. How many people would have to play on an all-star soccer team to guarantee that there are at least 3 people from a single high school?

Solution

The Generalized Pigeonhole Principle

If N objects are placed into k containers, then there is at least one container with at least ceiling(N / k) objects.

Example 1: Among 150 people, there are at least ceiling(150 / 12) = 13 who were born in the same month.

Example 2: If there are 12 classes in a new school, how many students must attend for there to be at least one class with 15 students (each student only attends 1 class)?

Solution

Click here to see our Pigeonhole Principle Java Applet

 previous page home next page