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 since even if we have all those disks we won't have 10 of any one disk. 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}$.

See Also

1994 AHSME (ProblemsAnswer KeyResources)
Preceded by
Problem 18
Followed by
Problem 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
All AHSME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png