Not sure how to apply pigeon hole beyond most simple example

Question

You have a jar of 20 pennies, 8 nickels, 10 dimes, and 15 quarters. How many coins must you pull to be certain you have 12 of the same kind?

• I understand that only the pennies and the quarters are eligible. This can't be as simple as $${20 \choose 12} + {15 \choose 12}$$ I'm not sure if I need to divide it by the total number of ways to pick 12 out of the 53 total coins?

• That is a lot harder for me to think about than "How many coins to guarantee two of the same denomination"? Which is clearly pigeon hole principle and the answer is the ceiling of n/2 = 2 which is 3

Answer 1

You're over-complicating. You know that just the pennies and quarters are eligible. So just imagine a scenario where you have $20$ pennies, $15$ quarters, and nothing else. How many coins do you need to ensure there are 12 of one type?

The answer should be obvious: $23$. You can have $22=11+11$, but once you reach $23=2(11)+1$ you must have $12$ pigeons in one "hole," so to speak.

Hopefully, this is enough of a hint to solve the problem you're asking. :-)

Answer 2

This is neither a combinatorics question nor (arguably) a pigeonhole question. Neither the 8 nickels nor the 10 dimes help getting 12 of the same kind of coin. Therefore, for starters, you must select all 18 of those coins. Then, you have to select (worst case) an additional 22 coins, which could be 11 quarters and 11 pennies. Then the next coin that you pick will have to be either a satisfying quarter or a satisfying penny.

Final Answer:

$$8 + 10 + 11 + 11 + 1.$$