1994 AHSME Problems/Problem 19

Problem

Label one disk "$1$", two disks "$2$", three disks "$3$"$, ...,$ fifty disks "$50$". Put these $1+2+3+ \cdots+50=1275$ labeled disks in a box. Disks are then drawn from the box at random without replacement. The minimum number of disks that must be drawn to guarantee drawing at least ten disks with the same label is

$\textbf{(A)}\ 10 \qquad\textbf{(B)}\ 51 \qquad\textbf{(C)}\ 415 \qquad\textbf{(D)}\ 451 \qquad\textbf{(E)}\ 501$

Solution

We can solve this problem by thinking of the worst case scenario, essentially an adaptation of the Pigeon-hole principle. We can start by picking up all the disks numbered 1 to 9. This gives us 45 disks. From disks numbered from 10 to 50, we can pick up at most 9 disks to prevent picking up 10. There are 50-10+1 = 41 different numbers from 10 to 50. We pick up 9 from each number, therefore, we multiply $41 \cdot 9 = 369$. In total, the maximum number we can pick up without picking up 10 of the same kind is $369+45=414$. We need one more disk to guarantee a complete set of 10. Therefore, the answer is $\boxed{415}$.

Invalid username
Login to AoPS