Minimum number of coins to ensure 10 coins of one type are selected

Question

One coin is labelled with the number $1$, two different coins are labelled with the number $2$, three different coins are labelled with the number $3$, $\ldots$ , forty-nine different coins are labelled with the number $49$, fifty different coins are labelled with the number $50$.

All of these coins are then put into a black bag. The coins are then randomly drawn one by one. We need $10$ coins of any type. What is the minimum number of coins that must be drawn to make sure that we have at least $10$ coins of any type?

Answer 1

This is a Pigeonhole Principle problem. First select the coins labeled $\{1,2,3,...,9\}$ since none of these types can reach $10$. So we have selected $1+2+3+\cdots+9=45$ coins so far. Now we have $41$ coins left. If we select $9$ coins of each type we will have selected $41\cdot 9=369$ coins. Thus the number of coins we can select before we select $10$ of the same type is $45+369=414$ and so the very next coin that is selected will give us $10$ of the same type. Hence $415$ coins need to be selected in order to guarantee that we have $10$ of the same type.

Answer 2

Hint: We can draw all of those coins of which there are $9$ or fewer, and $9$ each of the other coins, and still not have any types with $10$ repeats.