Theorem 9.4.1. Pigeonhole Principle.
A function from one finite set to a smaller finite set cannot be one-to-one. There must be at least two elements in the domain that have the same image in the codomain.
Section 9.4 Pigeonhole Principle
In this section we look at a method of counting that uses a correspondence between two sets. We can think of one set as a set of objects and the other as a set of boxes. The name of the principle comes from thinking of a set of letters and pigeonholes, which is what they used to call rows of letterboxes. Though it is also fun to think about correspondences between pigeons and pigeonholes.
The Pigeonhole Principle really just says that if there are more objects (pigeons) than boxes (pigeonholes) then there must be at least one box with more than one object.
When working with pigeonhole problems
- identify the objects (pigeons)
- identify the boxes (pigeonholes)
- show the number of objects is bigger than the number of boxes.
Beware:
- You can still have a box with no objects.
- You do not know which box has more than one object.
- A box could have all the objects.
- You do not know how many objects are in any particular box.
Example 9.4.2. Counting Socks.
In a drawer with 5 pairs of red socks and 5 pairs of blue socks, how many socks do you need to randomly pull out of the drawer to be certain that you have a pair?
Note, there are 10 socks of each color.
Answer 1.
3 socks, since the first two might be different colors. If that happens the third sock must match one of the first two.
In this example, the socks are the objects and the colors are the boxes.
Now, what if you need to make sure you have a red pair?
Answer 2.
12 socks.
It is important to note that pigeonhole problems are not about probability. We want to know when we are guaranteed to have a pair of socks, not when it is likely that we have a pair.
Activity 9.4.1.
In a group of 10 people, must 2 be born in the same month? What is the most people that can be born in the same month?
Activity 9.4.2.
In a group of 13 people, must at least 2 be born in the same month? Must at least one person be born in January?
Example 9.4.3. Finding Sums of Integers.
Let \(A=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\text{.}\) How many integers do you need to choose from \(A\) to guarantee that 2 numbers will sum to 11?
Since we are looking for sums of 11, our boxes can be pairs of numbers that sum to 11: \(\{1, 10\}, \{2, 9\}, \{3, 8\}, \{4, 7\}, \{5, 6\}\text{.}\) Then our objects are the numbers themselves. We need the number of numbers to be greater than the number of boxes, which is 5. Thus, if we choose 6 numbers from \(A\text{,}\) we are guaranteed to have 2 from the same subset. This means with 6 numbers we must have two numbers that sum to 11.
Activity 9.4.3.
Let \(A=\{1, 2, 3, 4, 5, 6, 7, 8\}\text{.}\) If 5 integers are selected from \(A\text{,}\) must at least one pair have a sum of 9? If 4 integers are selected from \(A\text{,}\) must at least one pair have a sum of 9?
Activity 9.4.4.
How many integers from 0 to 60 must you choose in order to get at least one that is odd? How many integers from 0 to 60 must you choose in order to get at least one that is even?
We can generalize the Pigeonhole Principle. If we have enough objects, we can guarantee more than two objects in one box.
Theorem 9.4.4. Generalized Pigeonhole Principle.
If there are \(n\) objects mapped to \(m\) boxes, and for some \(k\text{,}\) we have \(n>km\text{,}\) then at least one box contains \(k+1\) or more objects.
Example 9.4.5. Generalized Pigeonhole.
Suppose you have 23 books that are placed in 4 boxes.
Must at least one box contain at least one book?
Answer 1.
Yes
Must at least one box contain at least two books?
Answer 2.
Yes
Must at least one box contain at least six books?
Answer 3.
Yes
Must at least one box contain at least seven books?
Answer 4.
No
What is the most books that can be in a box?
Answer 5.
23
What is the fewest books that can be in a box?
Answer 6.
0
Activity 9.4.5.
If you have 8 books and want to place them in 3 boxes, must at least one box have 4 books? Must at least one box have 3 books?
Activity 9.4.6.
In a group of 2000 people, must 5 have the same birthday?
Theorem 9.4.6.
Let \(X, Y\) be finite sets with the same number of elements. Suppose \(f\) is a function from \(X\) to \(Y\text{.}\) Then \(f\) is one-to-one if and only if \(f\) is onto.
The Pigeonhole Principle can be used to prove the theorem, but it is more technical than we need. If you try a few examples of functions from a set of \(n\) elements to another set of \(n\) elements, you can probably convince yourself that a one-to-one function must be onto and vice versa.
Reading Questions Check Your Understanding
1.
What is the fewest number of digits you need to randomly select from \(A=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\) to guarantee you have either two even or two odd numbers?
2.
What is the fewest number of digits you need to randomly select from \(A=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\) to guarantee you have two even numbers?
3.
What is the fewest number of digits you need to randomly select from \(A=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\) to guarantee you have a sum of 9?
4.
What is the fewest number of digits you need to randomly select from \(A=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\) to guarantee you have two with the same remainder when divided by 3?
5.
- Yes
- For example, you could have selected 1, 2, 4, 5, none of which have remainder 0.
- No
- Correct. Now think about how many you would have to select to get 2 with remainder 0.
If you randomly select 4 digits from \(A=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\) are you guaranteed to have two with remainder 0 when divided by 3?
Exercises Exercises
1.
Consider a standard deck of 52 cards.
- If 13 cards are selected from the deck, must at least 2 be of the same denomination?
- If 20 cards are selected from the deck, must at least 2 be of the same denomination?
- How many cards must you pick from the deck to be sure of getting at least 1 red card?
2.
A small town has only 500 residents. Must there be 2 residents who have the same birthday?
3.
Given any set of four integers, must there be at least two that have the same remainder when divided by 3? Why?
4.
Given any set of three integers, must there be at least two that have the same remainder when divided by 3? Why?
5.
Let \(S=\{3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}\text{.}\) If six integers are selected from \(S\text{,}\) must at least one pair have a sum of 15? Why?
6.
If \(n+1\) integers are chosen from the set \(\{1, 2, 3,\ldots 2n\}\text{,}\) where \(n\) is a positive integer, must at least one of them be even? Why?
7.
Suppose six pairs of similar-looking boots are thrown together in a pile. How many individual boots must you pick to be sure of getting a matched pair? Why?
8.
How many integers from 1 to 100 must you choose in order to be sure to get at least one that is divisible by 5?
9.
How many integers must you pick in order to be sure that at least two of them have the same remainder when divided by 15?
10.
In a group of 30 people, must at least 3 have been born in the same month? Why?
You have attempted of activities on this page.
