Guaranteed Birth Month Match: Pigeonhole Principle
How many people must be in a room to guarantee that at least 5 of them share the same birth month?
Hints
- Think about the worst-case arrangement: an adversary wants to delay the outcome as long as possible by spreading people across months as evenly as they can.
- The pigeonhole principle says: if $n$ items are placed in $h$ boxes, at least one box contains $\lceil n/h \rceil$ items. You want this ceiling to reach 5.
- With 12 months, you can maintain 'at most 4 per month' for up to $4 \times 12 = 48$ people. The next person forces a month to 5.
Worked Solution
How to Think About It: This is a classic worst-case reasoning problem. The question is not 'what is the probability that 5 people share a birth month?' -- it asks for certainty. The way to guarantee something in the worst case is to ask: how could an adversary arrange the birth months to avoid the outcome for as long as possible? They would spread people as evenly as possible across all 12 months.
Quick Estimate: If we could put people evenly across 12 months, we can have at most $4 \times 12 = 48$ people with no month having 5 or more. The 49th person must go into some month, pushing it to 5. So the answer is 49.
Approach: Apply the pigeonhole principle: with $n$ people (pigeons) and 12 months (holes), the most-crowded month has at least $\lceil n/12 \rceil$ people.
Formal Solution:
We want the minimum $n$ such that, regardless of birth month distribution: $$\max_{\text{month } m} (\text{count in month } m) \geq 5$$
The adversary's best strategy is to distribute as evenly as possible: - With $n = 48 = 4 \times 12$ people: place exactly 4 in each month. Every month has 4 -- no month reaches 5. Not guaranteed yet. - With $n = 49$: by pigeonhole, at least one month must have $\lceil 49/12 \rceil = \lceil 4.08... \rceil = 5$ people. Guaranteed.
$$\boxed{49 \text{ people}}$$
Answer: 49. The general formula is $4 \times 12 + 1 = 49$ for "at least 5 in the same month." For "at least $k$ in the same month among $h$ categories," it is $(k-1) \times h + 1$.
Intuition
The pigeonhole principle is deceptively simple but shows up everywhere in combinatorics, computer science, and even trading. The key insight is the difference between 'probable' and 'guaranteed' -- a probabilistic argument would give you confidence, but the pigeonhole gives you certainty. Any time someone asks 'how many X do you need to be sure that Y?', think worst-case and the pigeonhole principle.
The general formula $(k-1) \times h + 1$ is worth remembering. In the context of trading, analogous logic appears in coverage arguments: if you have $h$ different risk scenarios and want to guarantee your hedge covers at least $k$ of them, you need your portfolio to account for at least $(k-1) \times h + 1$ scenario-instrument pairs. The same structure underlies many combinatorial bounds in algorithmic trading and mechanism design.