Author:
Amanda Hager
Subject:
Mathematics
Material Type:
Lesson
Level:
Academic Lower Division
Provider:
University of Texas at Austin
Tags:
  • D2S2
  • Mindset
  • Not Reviewed
  • License:
    Creative Commons Attribution
    Language:
    English
    Media Formats:
    Text/HTML, Video

    Education Standards

    1.4 Pigeonhole Principle

    1.4 Pigeonhole Principle

    Overview

    TCCNS CourseMATH 1332: Contemporary Mathematics
    UT Austin CourseM 302: Introduction to Mathematics

    Introduction

    Suggested Resources and Preparation

    Materials and Technology

    • For the instructor: Manipulatives such as dice, cards, marbles, coins, colorful craft sticks which can be used to visualize problems. Computer and/or projector will also be helpful for videos.

    Prerequisite Assumptions

    Part 2 requires some facility with estimation, which is covered in Section 1.3.

    Overview and Student Objectives

    Lesson Length

    50 minutes

    Lesson Objectives

    Students will understand that:

    • The Pigeonhole Principle can be used to prove that certain things are guaranteed to occur, even if they seem difficult or impossible to directly measure.
    • To prove that something is guaranteed to occur, you can prove that the opposite situation is impossible (i.e. to prove a statement is true, you can prove its negation is false).
    • To prove that something is not guaranteed to occur, you can prove that the opposite situation is possible (i.e. to prove a statement is not true, you can prove its negation is not false).

    Students will be able to:

    • Create the negation of a logical statement.
    • Apply the Pigeonhole Principle to prove that at least two objects out of n will share a particular characteristic, so long as the number of characteristics is smaller than the number of objects
    • Generalize the Pigeonhole Principle to prove that at least m objects out of n will share a particular characteristic, given proper conditions.

    Pigeonhole Principle Part I

    Are there two people on Earth who have the exact same number of hairs on their bodies?

    nine people facing away from camera with arms around each other

    This is not a probability question! The answer is yes. There is a way to prove this is true using just math and logic.

    What makes this so hard?

    There are about 7.8 billion people on the planet. Hairs are small and hard to count. We all lose hairs every day (long-haired people know this to be true for sure), and we sprout new hairs all the time. By the time you counted the hairs on just one arm, you could have lost a few hairs on your head and the number would change. And let's not even get into the horrible awkwardness about how the problem says all body hair, not just hair on their head.

    So, this is impossible to count on one person, let alone 7.8 billion. What do we do?

    How do we get started?

    The statement we are trying to prove is: There exist two people who have the exact same number of hairs on their bodies.

    The strategy here is to write down the logical opposite of that statement and prove that the opposite statement is impossible. In this case, the opposite statement is: There do not exist two people who have the exact same number of hairs on their bodies.

    Notice how it's either-or, one of those statements has to be true and both cannot be true. That's key. Now, logic time! If no two people on Earth are allowed to have the same numbers of hairs, then that means: Everybody on Earth has a unique hair count.

    The math

    If the statement isn’t true, that means every single individual has a unique number of hairs on their body. It helps to imagine everybody walking around with a Sims(TM) plumbob over their head and the exact number of hairs they have at that moment. If they brush their hair and some hairs come out, that number will instantly fall. If they sprout a new hair, the number will go up.

    same nine people as above, only with plumbobs and numbers above their heads. Numbers range from 180,414 to 523,410

    If every person has their own unique hair count, what are the numbers that get used up? Imagine that there is one poor soul out there with a single hair sticking out of their head and nothing else. Nobody else on Earth gets to have 1 hair. Then imagine somebody has two hairs, somebody has 3 hairs, somebody has 4 hairs, etc.

    Five cartoon smiley faces, with one hair, two hairs, three hairs, four hairs, five hairs respectively.

    Logically, this means that the hairiest person on earth has 7.8 billion hairs. Is this even possible? 

    This took a bit of digging, but in Flindt and Rainer's Amazing Numbers in Biology, it was found that on average adults have 150,000 head hairs and 25,000 body hairs for a total average of 175,000. But average isn't good enough...we wanted the hairiest. Look at it this way: a person who had 7.8 billion hairs would have over 44,000 times the average number for an adult.

    Here's a second argument: that same textbook says that on average adults have 1.8 square meters of skin and at the hairiest point we have 320 hairs per square centimeter. What would happen if somebody were 100% covered in hair that dense and that person were ten times as large as the average adult? Now, 1.8 square meters is the same as 18,000 square centimeters. The calculation is:

    \(18000\mbox{ cm}^2\times10\times320\frac{\mbox{hairs}}{\mbox{cm}^2}=57,600,000\mbox{ hairs}\)

    That's still 100 times less than this theoretical super-hairy beast-person has.

    It's time for the write-up!

    The proof

    Claim: There are at least two people who have exactly the same number of hairs on their bodies.

    Proof: Let's pretend that everybody has their own unique hair count. Because there are about 7.8 billion people on the planet (cite a source), that means there is somebody out there with 7.8 billion hairs. But this can't happen! According to Flindt and Rainer's Amazing Numbers in Biology, adult men have 18,000 cm2 of skin and a maximum of 320 hairs per square centimeter. That means that even if there were some person out there that was ten times as big as the average and was completely covered in head hair, they'd only have \(\begin{equation*} 18,000\times10\times320=57,600,000 \end{equation*}\) hairs. There is no possible way for somebody to have 7.8 billion hairs. Therefore, hair counts must repeat, and some people have to share. Done!

    Now, there are several things to unpack and practice here. Writing good arguments, the strategy of proving that the opposite statement can't be true, the units and multiplication. But the part I want to focus on right now is the Pigeonhole Principle.

    Pigeonhole Principle Part II

    Pigeonhole Principle

    If you have a set of pigeons that you are trying to stuff into holes, and if there are more pigeons than there are holes, then some pigeons must share. 

    In other words: If you have a set of \(n\) objects that you are putting into \(m\) containers, and if \(n>m\), then some objects must share a container.

    Now for some examples showing how this principle gets used in math. The hardest one addressed in this video is: if I have a list of 70 English words, what is the highest number of words that I can guarantee will start with the same letter (there are 26 letters in the alphabet)?

    Video: Pigeonhole Principle examples

    More Examples

    Example 1

    In a standard deck of 52 cards, what is the smallest number of cards you must draw to guarantee that you will have at least one pair matching in suit? (A standard deck of cards has four suits with 13 cards in each suit, aces through kings.)

    Deck of playing cards

    A: The answer is 5. If you drew 4 cards, you might have a pair matching in suit, but you might not. For example, you might draw one heart, one spade, one diamond, one club. But if you draw five cards, no matter what, there will be at least one suit with at least two cards. In this case there are five pigeons or cards, and four pigeonholes or suits.

    Example 2

    In a standard deck of 52 cards, what is the smallest number of cards you must draw to guarantee that you will have at least three cards matching in suit? 

    A: The answer is 9. If you only allow two cards per suit, then there are 2x4=8 pigeonholes. So if you draw 8 cards, you can fit all the cards or pigeons in, but if you draw 9 cards, there are too many pigeons.

    Example 3

    I have a deck of cards. I shuffle them and draw 15. What is the largest number of cards that I can guarantee will share a suit?

    A: Four. We can guarantee that four will share because if only three at a time are allowed to share, then three cards will be left over.

    Fifteen playing cards, three diamonds, three spades, three hearts, three clubs, three facedown.

    No matter what happens, those three cards have to go in one of those piles, so there will be at least four cards of at least one of the suits.

    Fifteen cards, three diamonds, three spades, four hearts, five clubs.

    Note that even distribution is not guaranteed. You could have tons of cards in one suit, but then there's a suit with more than four cards, right?

    Fifteen playing cards, 3 clubs, 11 diamonds, one spade.

    We cannot guarantee that five will share because it’s possible to have something like four each of hearts, spades, and diamonds, and three clubs.

    A Cool Hack

    Example 4

    This problem is the same as Example 3. I have a deck of cards. I shuffle them and draw 15. What is the largest number of cards that I can guarantee will share a suit?

    A: Hack: 15/4 = 3.25. Round up 3.25 to get the answer 4. In a full sentence, you'd say "4 because if only three cards at a time are allowed to share a suit, there is only room for 3x4=12 cards, so there are leftover cards. At least one suit has at least four cards."

    Example 5

    400 people are in a lecture hall. What is the largest number n where you can guarantee that at least \(n\) people out of that group will share a birthday month?

    A: 400/12 = 33.333. Round up to get 34. Your response: "We know that at least 34 people in that room will share a birthday month because if only 33 people are allowed to share each month, that only accounts for 33 × 12 = 396 people. At least one date has at least 34 people in it."

    This trick only works if you remember to always round up instead of rounding to the nearest whole number.

    Solving Messy Problems with Pigeonhole Principle

    Combining estimation and Pigeonhole Principle, you are often able to solve problems in the real world that are messier and more complicated than "math class problems."

    Video: Solving messy problems with Pigeonhole Principle

    Quiz Questions

    QuestionAnswer
    11
    23
    33
    41

     

    Question 1

    We shuffle a deck of 52 standard playing cards and draw 11 cards. Is it guaranteed that at least six of the cards will be the same color?

    1. Yes because if we only allow 5 cards of each color there will be one left over.
    2. Yes because there must be six of one color and five of the other.
    3. No because you could have eleven of one color and zero of the other.
    4. No because there will be six of one color but only five of the other color.

    Question 2

    We shuffle a deck of cards and draw 11 cards. Is it guaranteed that there will be at least six red cards?

    1. Yes because if we only allow 5 cards of each color there will be one left over.
    2. Yes because there will be six of one color and five of the other.
    3. No because there can be anywhere from 0-11 red cards, all cards could be black.
    4. No because there will be six black cards and only five red cards.

    Question 3

    I flip ten coins. What is the highest number where I can guarantee that at least that many coins will match?

    US penny with obverse (heads) and reverse (tails) shown
    U.S. Penny, obverse/heads (left) and reverse/tails (right). Source: Wikipedia
    1. 2
    2. 5
    3. 6
    4. 10

    Question 4

    17 people get on an elevator. They can stop on floors 2, 3, 4, or 5. Can you guarantee that at least five people will get off the elevator on at least one of those floors?

    1. Yes because if you have a limit of four people per floor that's only 4x4=16 people.
    2. Yes because you can have all 17 people get off on the same floor.
    3. No because you can have all 17 people get off on the same floor.
    4. No because you can have 1-1-1-14 so three floors can have fewer than five poeple.

    Homework Questions

    Question 1.4.1

    1. You need 3. If you pull 2 you could get a pair or you could get one blue and one black. In every case, the third sock will complete a pair.
    2. You need 5. If you pull 4 you could get two matching pairs, but you could get three of one color and one of the second color. The fifth sock will in both cases complete a second pair.
    3. You need 12. You could draw all ten black socks if you had bad luck. But then the next two are guaranteed to be blue.

    Question 1.4.2

    1. They would need 4. If they pull 3 it's possible to get one of each color. The fourth one is then guaranteed to complete a pair.
    2. They need 6. If they pull 5 they'll probably get two pairs, but it's possible to get three of one color and one of the other two colors, in which case you only have one pair. The sixth sock in that case is guaranteed to complete the second pair.
    3. If they had terrible luck, they'd draw all the blue socks and all the gray socks before drawing any green socks. That means they must draw 6+6+2=14.

    Question 1.4.3

    In a group of people, let's assume that the "friend" relationship is symmetric. That means that if Abby is friends with Braedon, then Braedon is friends with Abby. No one-sided relationships allowed.

    1. Assume the opposite, that each person has a different number of friends. The least number of friends one can have is 0 and the most is 9, so that implies that one person has each number of friends 0 through 9. The person who has 9 friends must be friends with all the other people, but that implies that no one has 0 friends. This is a contradiction, so at least two people have the same number.
    2. Assume the opposite, that each person has a different number of friends. The least number of friends one can have is 0 and the most is \(n-1\), so that implies that one person has each number of friends 0 through \(n-1\). The person who has \(n-1\) friends must be friends with all the other people, but that implies that no one has 0 friends. This is a contradiction, so at least two people have the same number.

    Question 1.4.4

    If we represent the partiers visually in a circle, we can use a graph to represent handshakes. Since we know someone shook 8 hands, we can simply assign an 8 to one of the people (we just don't know which person it is). This implies that this person shook every person's hand except their partner's because there are only 8 people available to shake hands with. This implies that everybody in the room has at least one handshake except 8's partner. This implies that 8 must be partnered with 0. We can continue this by assigning someone a 7, drawing out the necessary handshakes, and deducing that 7 must be partnered with 1. Similarly, 6 is partnered with 2, 5 is partnered with 3. This implies that the last two people are 4 and 4. At first glance, this is problematic, until we remember that Jordan was asking the question and did not answer it! This means that Taylor and Jordan have to be the four and four.

    Step 1 Someone shook 8 hands. Step 2 Person 8 must be partnered to Person 0. Step 3 someone shook 7 hands. Step 4: 7 must be partnered with 1. Last step: completed network with all handshakes represented.
    A graph with nodes representing the partiers edges representing handshakes. 

    Question 1.4.5

    1. Answers will vary. At the time of this writing the population was about 7.8 billion.
    2. Answers will vary. The longest any person has ever lived is 122 years (Jeanne Calment, France). It would be reasonable to claim that no one can live more than 125 years; any number higher than 122 will do.
    3. The worst case scenario is that less than 60 million people die every year for the next 120 years. There are never 60 million deaths in a calendar year, in other words.
    4. We can conclude that less than 7,200,000,000 people will die in the next 120 years. This means that over 600,000,000 will live past age 120, which is impossible. 

    Question 1.4.6

    We can guarantee at least 4. If only 3 people get off on every stop, that adds up to 18 people. Two people are left over.

    We cannot guarantee at least 5. We could conceivably see the people get off in this pattern: 4-4-3-3-3-3. 

    Therefore the answer is 4.

    Question 1.4.7

    Answers vary

    Question 1.4.8

    Answers var

    Question 1.4.1

    You own five pairs of black socks and five pairs of blue socks. You keep them in a drawer but you don't fold them, so there are just twenty loose socks in this drawer. You're getting dressed early in the morning when it's still dark, and you don't want to turn the lights on, so you're fishing around for socks and hoping you get a matching pair.

    1. How many socks do you have to pull out to guarantee that you will have one matching pair (either blue or black)?
    2. How many socks do you have to pull out to guarantee that you will have two matching pairs?
    3. How many socks do you have to pull out to guarantee that you will have a blue pair of socks?
    Three possibilities for "two good pairs:" two blue pairs, two black pairs, and one of each.
    Three possibilities for "two good pairs:" two blue pairs, two black pairs, and one of each.

    Question 1.4.2

    Your sibling owns three pairs of blue socks, three pairs of green socks, and three pairs of gray socks. They also do not fold their socks, so all 18 socks are just loose in their drawer. 

    1. If they were pulling socks randomly in the dark, how many socks would they have to pull to guarantee a matching pair?
    2. How many socks would they have to pull to guarantee two matching pairs?
    3. How many socks would they have to pull to guarantee a green pair of socks?
    Six different possibilities for "two good pairs:" two blue pairs, two green pairs, two gray pairs, one blue and one gray, one blue and one green, and one green and one gray.
    Six different possibilities for "two good pairs:" two blue pairs, two green pairs, two gray pairs, one blue and one gray, one blue and one green, and one green and one gray.

    Question 1.4.3

    In a group of people, let's assume that the "friend" relationship is symmetric. That means that if Abby is friends with Braedon, then Braedon is friends with Abby. No one-sided relationships allowed.

    1. Show that in a group of ten people, there are at least two people with the same number of friends in that group.
    2. (Challenge) Show that in a group of \(n\) people, there are at least two people with the same number of friends in that group.

    Question 1.4.4

    Taylor and Jordan threw a party. Five couples were present including Taylor and Jordan, and some of the partiers shook hands with others. We have no idea who shook hands with whom, but we do know that no one shook hands with themselves and no one shook hands with his or her own partner.

    At the end of the party, Jordan gathered the crowd and asked the nine other people how many hands each of them had shaken. Each person gave a different answer! That is, someone didn't shake any hands, someone else shook one hands, someone else shook two hands, someone else shook three hands, and so forth, down to the last person, who shook eight hands. Your mission: determine the exact number of hands that Taylor shook.

    Question 1.4.5

    Show that in at least one calendar year in the next 120 years that there will be at least 60 million human deaths.

    1. What is the human population right now?
    2. What is the absolute longest amount of time a person can live?
    3. What is the "worst case scenario?" In other words, what is true if we don't see 60 million deaths in any year?
    4. What can you conclude from these steps?

    Question 1.4.6

    20 people get on an elevator on floor 1. They can get off on floors 2, 3, 4, 5, 6, or 7. What is the largest number \(n\) where you can honestly say "I guarantee that at least \(n\) people will get off on at least one floor?"

    Question 1.4.7

    Name a goal that you are currently working on with your learning?

    Question 1.4.8

    Name something that you have done recently to make progress towards your goal. If you can't think of anything, you might do a few browser searches for techniques or practices that could help you progress towards your goals (if you do this, remember to cite your sources!).