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.
Least you need to know
- If
nobjects go intokboxes, some box has at leastceil(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
Worked example
- Put 13 students into 4 project groups.
13/4 = 3.25, so some group has at least⌈3.25⌉ = 4students.- 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 it
- 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'.
บทเรียนถัดไปที่แนะนำ
เรียนต่อในหัวข้อนี้ด้วย Least You Need to Know: Product Rule and Sum Rule
Least You Need to Know: Product Rule and Sum Ruleบทเรียนที่เกี่ยวข้อง
เรียนต่อด้วยบทเรียนใกล้เคียงในหัวข้อเดียวกัน