Exercise · ZW-PIGEONHOLE-PRINCIPLE-004 · ★☆☆ Basic
How many people are needed at minimum to guarantee that at least 9 share a birth month, with 12 months?
Choose one option.
Show answer
- D. \(97\)
Explanation
Without a guarantee there can be 8 per month: \(12\cdot 8=96\) people. The 97th person forces some month to have 9.
Review the concept: Pigeonhole principle
If \(n\) objects are placed in \(k\) boxes, some box holds at least \(\lceil n/k\rceil\) objects, and in particular two when \(n>k\).
\[\left\lceil \dfrac{n}{k}\right\rceil\]
More practice problems: pigeonhole principle
- ZW-PIGEONHOLE-PRINCIPLE-001 A group has 13 people. What can be stated with certainty about their birth months?
- ZW-PIGEONHOLE-PRINCIPLE-002 30 marbles are distributed into 4 boxes. What is the largest number that is guaranteed to be in som…
- ZW-PIGEONHOLE-PRINCIPLE-003 How many cards from a 52-card deck (4 suits) must be drawn at minimum to guarantee two of the same…
- ZW-PIGEONHOLE-PRINCIPLE-005 100 people are grouped by birth month (12 months). At least how many are certain to share some mont…
- ZW-PIGEONHOLE-PRINCIPLE-006 How many integers must be chosen at minimum to guarantee two with the same remainder when divided b…
- ZW-PIGEONHOLE-PRINCIPLE-007 A drawer holds loose socks of 3 colours. Without looking, how many must be taken at minimum to guar…
- ZW-PIGEONHOLE-PRINCIPLE-008 A list has 1000 distinct Spanish words. Using 26 initial letters, how many words with the same init…
- ZW-PIGEONHOLE-PRINCIPLE-009 Seven numbers are chosen from the set \1,2,dots,12\. Which statement is always true?