There are people in a room. What is the largest value of such that the statement "At least people in this room have birthdays falling in the same month" is always true?
- A)
- B)
- C)
- D)
- E)
Answer
D
Key insight
Twelve months can hold at most 4 people each with 48 people total, so 52 people force some month to have at least 5, and 5 is sharp.
Solution
Think of the months as boxes and the people as objects placed in them.
If every month held at most people, there would be at most people, fewer than . So some month has at least people, no matter how the birthdays fall. The statement is always true for .
Is the largest such ? Distribute people as in four months and in each of the other eight months. Then no month has people, so "at least " can fail.
The answer is .
Why this works
This is the pigeonhole principle in its counted form: objects in boxes force some box to hold at least . A "largest guaranteed " question always has two halves, a proof that works (the pigeonhole bound) and a construction showing can fail (an even-as-possible spread).
The trap
Answering 4 from 52/12 = 4.33 rounded down, or 12 from misreading the question as the number of months.
Common mistakes
- Answering from rounded down, or from misreading the question as the number of months.
- Giving a value like or that is true but not the largest guaranteed value.
Techniques
Consider the largest/smallest element or boundary case · Pigeonhole principle