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
|