Skip to main content

Discrete Mathematics An Active Approach to Mathematical Reasoning

Jennifer Firkins Nordstrom

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.
🔗
🔗
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}. 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}. 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, 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}. If 5 integers are selected from A, must at least one pair have a sum of 9? If 4 integers are selected from A, 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.
🔗

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.
🔗
Must at least one box contain at least two books?
🔗
Answer 2.
🔗
Must at least one box contain at least six books?
🔗
Answer 3.
🔗
Must at least one box contain at least seven books?
🔗
Answer 4.
🔗
What is the most books that can be in a box?
🔗
Answer 5.
🔗
What is the fewest books that can be in a box?
🔗
Answer 6.
🔗
🔗

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?
🔗
🔗
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.

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?
🔗
  • 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.
🔗
🔗

Exercises Exercises

1.

Consider a standard deck of 52 cards.
🔗
  1. If 13 cards are selected from the deck, must at least 2 be of the same denomination?
    🔗
    🔗
  2. If 20 cards are selected from the deck, must at least 2 be of the same denomination?
    🔗
    🔗
  3. 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}. If six integers are selected from S, must at least one pair have a sum of 15? Why?
🔗
🔗

6.

If n+1 integers are chosen from the set {1,2,3,…2n}, 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.
🔗
PrevTopNext