Japan Junior Mathematical Olympiad

We will show that the smallest $n$ satisfying the condition of the problem is $2012^2$.

First, let us show that if $n=2012^2$, then there exists a method of selecting cards at each stage so as to satisfy the condition of the problem. For this purpose, let for each $k\ge 1$, select $2012$ cards to be drawn in the $k$-th stage in the following way:

Write $k=2012q+r$ for some choice of $q\ge 0$ and $1\le r\le 2012$, and choose $2012-r$ cards, each of which has the number $q$ written on it, and choose $r$ cards, each of which has the number $q+1$ written on it.

Let us check that this method to keep on choosing cards satisfies the condition of the problem. There are the following two facts to be checked:

(1) The sum of the numbers written on the cards at the $k$-th stage must equal $k$.

(2) For every integer $a\ge 0$, there are at most $2012^2$ cards with the attached number $a$ among the selected cards throughout the whole procedure.

We see that the condition (1) is satisfied, since

$$q(2012-r)+(q+1)r=2012q+r=k$$ holds, because of the way $q$ and $r$ are chosen.

To show that the condition (2) is satisfied, we first consider the case where $a\ge 1$. Then for any $r$ satisfying the condition $1\le r\le 2012$, $2012-r$ cards each with the number $a$ attached are selected at the $(2012a+r)$-th stage, and $r$ cards each with the number $a$ attached are selected at the $(2012(a-1)+r)$-th stage. Therefore, the total number of the cards with the number $a$ attached which are selected in the whole procedure equals

$$\begin{gathered} \sum _{r=1}^{2012}((2012-r)+r)=(2011+2010+\cdots +0)+(1+2+\cdots +2012) \\ =\frac{2011\cdot 2012}{2}+\frac{2012\cdot 2013}{2}=2012^2, \end{gathered}$$ which shows that the condition (2) is satisfied for each $a\ge 1$.

Finally, if $a=0$, we see that for each $r$, with $1\le r\le 2012$, $2012-r$ cards with $0$ attached are selected at the $r$-th stage so that the total number of cards with $0$ attached chosen in the whole process is

$$\sum _{r=1}^{2012}(2012-r)=\sum _{r=1}^{2011}r=\frac{2011\cdot 2012}{2}<2012^2,$$ which shows that the condition (2) is satisfied for $a=0$ as well, and this completes the proof that if $n=2012^2$, then there is a method to keep on choosing cards at each stage so as to satisfy the condition of the problem.

Next, we show that if there is a method of choosing cards at each stage so as to satisfy the condition of the problem, then we must have $n\ge 2012^2$. For this purpose, let $k$ be an arbitrary positive integer and keep on choosing the cards at each stage according to the method which is supposed to satisfy the condition of the problem. Then, the sum of all the numbers attached to $2012nk$ cards selected by the end of the $(nk)$-th stage must be, because of the condition of the problem,

$$\sum _{j=1}^{nk}j=\frac{1}{2}nk(nk+1).$$

On the other hand, since for each $j\ge 0$ there are exactly $n$ cards having the number $j$ attached, the sum of all the numbers attached to the $2012nk$ cards selected must be greater than or equal to

$$n\sum _{j=0}^{2012k-1}j=n\cdot \frac{2012k\cdot (2012k-1)}{2}.$$

Therefore, we must have

$$\frac{nk(nk+1)}{2}\ge n\cdot \frac{2012k(2012k-1)}{2},$$ which can be simplified to

$$n\ge 2012^2-\frac{2013}{k}.$$

Since $k$ can be any positive integer, we take $k=2014$ to conclude that $n\ge 2012^2$ must be satisfied.