Counting / Pigeonhole Principle
Least You Need to Know: The Pigeonhole Principle
If you place more objects than boxes into the boxes, at least one box must contain more than one object. Use the ceiling idea for stronger versions.
The least you need to know
- If `n` objects go into `k` boxes, some box has at least `ceil(n/k)` objects.
- The principle proves existence, not the exact box.
- You do not need to identify which box gets crowded.
- The right boxes are part of the modeling choice.
- A weak counting estimate is often enough to force a repeat.
Key notation
⌈x⌉
ceiling of x
n
number of objects
k
number of boxes
Tiny worked example
- Put 13 students into 4 project groups.
- `13/4 = 3.25`, so some group has at least `⌈3.25⌉ = 4` students.
- You do not know which group, only that one must exist.
Common mistakes
- Students often use floor instead of ceiling.
- Students sometimes choose the wrong boxes.
- Students often think the principle only works for exact duplicates.
How to recognize this kind of problem
- The problem asks you to guarantee a repeat or a crowded category.
- You know the number of objects and the number of categories.
- The wording says 'must' or 'at least one'.
Next recommended lesson
Continue through this topic with Least You Need to Know: Product Rule and Sum Rule.
Least You Need to Know: Product Rule and Sum RuleRelated lessons
Keep going with nearby lessons in the same topic.