Pigeonhole Principle (Medium)

AMC 10/12 mid (≈Q9–16) — multi-step.

Pigeonhole Principle: core idea

Strong form.

What is the minimum number of people needed to **guarantee** that **three** share a birth month?

Hint: At most $2$ per month without a triple → $2\cdot12+1$ . Answer: 25.

1. What is the minimum number of people needed to **guarantee** that **four** share a birth month?
2. What is the minimum number of integers you must pick to **guarantee** that **three** share the same remainder modulo $7$ ?
3. What is the minimum number of integers you must pick to **guarantee** that **four** share the same remainder modulo $5$ ?
4. A drawer has socks in $5$ different colors, unlimited supply of each. What is the minimum number to **guarantee** **three** socks of the same color?
5. Choose from $\{1,2,\ldots,10\}$ . What is the minimum subset size that **guarantees** two numbers summing to $11$ ?
6. What is the minimum number of people needed to **guarantee** that **five** share a birth month?
7. Pick integers from $\{1,2,\ldots,14\}$ . What is the minimum size guaranteeing **three** with the same remainder mod $4$ ?
8. Pick integers from $\{1,2,\ldots,9\}$ . What is the minimum size guaranteeing **three** with the same remainder mod $3$ ?
9. What is the minimum number of people needed to **guarantee** that **four** share the same birth season (spring, summer, fall, winter)?