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