An urn contains $k$ balls marked with $k$, for all $k=1,2, \ldots, 2016$. What is the minimum number of balls we must withdraw, without replacement and without looking at the balls, to be sure that we have 12 balls with the same number?
Solution

Let's sum the maximum number of balls that can be drawn of each type without obtaining 12 balls of each color:

$$
1+2+3+4+5+6+7+8+9+10+11+\underbrace{11+11+\ldots+11}_{2005 \text { times }}=22121
$$

Thus, it is possible that we have bad luck and draw such a number of balls without obtaining 12 balls of each color. However, if we draw 22122 balls, we will certainly have 12 balls of the same color, as the sum above counts exactly the maximum number of balls that can be drawn without this happening. Therefore, the minimum sought is 22122.

#