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.
جو کم از کم جاننا ضروری ہے
- 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.
اہم علامتیں
⌈x⌉
ceiling of x
n
number of objects
k
number of boxes
مختصر حل شدہ مثال
- 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.
عام غلطیاں
- Students often use floor instead of ceiling.
- Students sometimes choose the wrong boxes.
- Students often think the principle only works for exact duplicates.
اس قسم کے سوال کو کیسے پہچانیں
- 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.