Discrete Math · Undergraduate
The Pigeonhole Principle
Quick answer
If n + 1 or more objects go into n boxes, at least one box holds two or more. More generally, if N objects go into k boxes, some box holds at least ⌈N/k⌉ of them. The principle proves that something must happen without saying where: among 13 people two share a birth month, any 6 integers include two with the same remainder mod 5, and among 5 points in a unit square two lie within √2/2 of each other. The skill is choosing what the boxes are.
What you'll learn
- State the pigeonhole principle and its general form
- Choose objects and boxes to fit a problem
- Find the smallest number that guarantees an outcome
- Use the principle in number theory and geometry proofs
More pigeons than holes
If pigeons fly into holes, some hole gets at least two pigeons. That is the whole pigeonhole principle:
If more than objects are placed into boxes, some box contains at least two objects.
It sounds almost too plain to be useful, but it proves things that are hard to see any other way, because it guarantees that something happens without needing to find where.
General form. If objects go into boxes, some box holds at least objects, where rounds up.
Why it must be true
Suppose every box held at most one object. Then boxes would hold at most objects in total, fewer than we placed. The total cannot fit unless some box takes more than its share. The general form is the same argument: if every box held fewer than , the boxes together would hold fewer than . It is a proof by contradiction, in one line.
Worked examples
Common mistakes
Practice problems
-
How many people guarantee that two share a birthday, ignoring leap years?
Answer
Full solution
There are possible birthdays, so people are needed for a guaranteed match.
-
A bag has red, green, blue and yellow marbles. How many must you draw to be sure of two of the same color?
Answer
Full solution
Four colors are the boxes; four marbles could all differ.
-
How many must you draw from the bag in Exercise 2 to be sure of three of the same color?
Answer
Full solution
Eight marbles could be two of each color. The ninth makes three of one color.
-
Show that among any integers, two have the same last digit.
Answer
There are only possible last digits.
Full solution
The boxes are the digits to , and .
-
students take a test graded A to F, with possible grades. At least how many students get the same grade?
Answer
Full solution
.
-
Show that in any group of people, two have the same number of friends in the group.
Answer
The possible counts are to , but and cannot both occur, leaving boxes for people.
Full solution
If someone is friends with everyone, no one has friends, and the reverse. So only values are possible.
-
How many integers must be chosen from to to guarantee two whose sum is ?
Answer
Full solution
The boxes are the pairs . Ten numbers could take one from each pair; the eleventh completes a pair.
-
A student says people guarantee a shared birth month. Correct the claim.
Answer
Twelve people can be born in twelve different months; it takes .
Full solution
The principle needs more objects than boxes.
Frequently asked questions
What is the pigeonhole principle?
If more than n objects are placed in n boxes, at least one box contains two or more objects.
What is the generalized pigeonhole principle?
If N objects are placed in k boxes, at least one box contains at least ⌈N/k⌉ objects, where ⌈ ⌉ rounds up.
How do you choose the boxes?
Make the boxes the categories that the conclusion talks about: months for birthdays, remainders for divisibility, small regions for distances.
Does the principle say which box has two objects?
No. It guarantees that some box does, without identifying it. That is why it proves existence statements.
How many socks guarantee a matching pair from three colors?
Four. Three socks could all differ, but a fourth must match one of the three colors.