What is the pigeonhole principle?
Jenn, Founder Calcworkshop®, 15+ Years Experience (Licensed & Certified Teacher)
That’s exactly what you’re going to learn about in today’s discrete class.
Let’s jump on in!
So, did you know that in a crowd of 367 people, there will be at least two people with the same birthday?
How do we know for sure without having to ask every single person?
Because of the Pigeonhole Principle!
How To Use Pigeonhole Principle
The idea is this.
If there are n number of pigeonholes and (n+1) pigeons, and if all the pigeons come home to roost, then there will be a pigeonhole that contains more than one pigeon, as noted by the University of Maryland.
Pigeonhole Principle Diagram
The pigeonhole principle, also known as the Dirichlet principle, originated with German mathematician Peter Gustave Lejeune Dirichlet in the 1800s, who theorized that given m boxes or drawers and n > m objects, then at least one of the boxes must contain more than one object.
Dirichlet Drawer Principle
So, going back to our first question, how do we know that in a crowd of 367 people, there will be at least two people with the same birthday?
Because if there are 367 people (pigeons) and only 366 possible days in a year, including leap year (pigeonholes), there must be at least two people with the same birthday because there are more people than possible birthdates.
Interestingly enough, we can generalize the pigeonhole principle using the ceiling function to determine either the number of pigeons or pigeonholes that fit a scenario.
Pigeonhole Definition
Example – Class Schedule
For instance, suppose there are 35 different time periods during which classes at the local college can be scheduled. If there are 679 different classes, what is the minimum number of rooms that will be needed?
Pigeonhole Problem
Therefore, the local college will need 20 different rooms to accommodate the different classes and periods.
Example – Student Grades
Likewise, let’s suppose we want to know the minimum number of students required in a math class so that at least six students will receive the same letter grade (A, B, C, D, or F).
This means that if we let n represents the number of students (pigeons), m is the number of letter grades (pigeonholes), and 6 is the desired outcome (objects), then:
Find Minimum Objects — Dirchlet Example
Consequently, using the extended pigeonhole principle, the minimum number of students in the class so that at least six students receive the same letter grade is 26.
Together we will work through countless problems and see how the pigeonhole principle is such a simple but powerful tool in our study of combinatorics.
Let’s go!
Video Tutorial w/ Full Lesson & Detailed Examples (Video)
48 min
Get access to all the courses and over 450 HD videos with your subscription
Monthly and Yearly Plans Available
Still wondering if CalcWorkshop is right for you?
Take a Tour and find out how a membership can take the struggle out of learning math.