17th Junior Turkish Mathematical Olympiad

The answer is $62$. Let us show that $k\ge 62$. Suppose that there are $62$ bags each containing one ball colored $1$, $61$ bags each containing $1$ ball colored $2$, ..., $1$ bag containing $1$ ball colored $62$. Let us show that these $1953$ bags can not be distributed into $61$ boxes. A bag containing a ball colored $l$ we call bag colored $l$. Note that if some box contains two bags colored $l$ then all remaining bags are also colored $l$. A box containing only bags colored $l$ will be called a unicolored box. Consider any distribution of these $1953$ bags. Suppose there are exactly $s$ unicolored boxes. Then there is a color $t$ so that there are at least $62-s$ bags of color $t$. These bags are in distinct boxes and the total number of boxes is at least $s+62-s=62$. Done.

Now we prove that $62$ boxes are sufficient for any arrangement of bag contents. Lemma: Suppose that there are at most $m$ bags containing a ball of the same color. Then these bags can be distributed into $m$ boxes. Proof: Let us choose a color, say $l_1$. We can distribute all bags containing balls colored $l_1$ into distinct boxes, since the number of such bags is at most $m$. Among remaining bags choose a color, say $l_2$. Similarly we can distribute all bags containing balls colored $l_2$ into distinct boxes. Similarly, by choosing a new color each time we can distribute all bags into $m$ boxes according to rule ii. The lemma is proved.

At the first step consider a ball colored $n_1$ belonging to maximal number of bags. If this number is at most $62$, by lemma we can distribute all bags into $62$ boxes. If not, put all these bags (at least $63$ bags) into one box and at the second step consider a ball colored $n_2$ belonging to maximal number of bags among all remaining bags. If this number is at most $61$, by lemma we can distribute all bags into $61$ boxes. If not, put all these bags (at least $62$) having common ball numbered $n_2$ into one box and proceed by the same way in the third step. Since $63+62+...+1=2016$, at some step, say step number $p$ among all remaining bags at most $63-p$ bags will contain a ball of the same color $n_p$. Now by lemma we can distribute remaining bags into at most $63-p$ boxes and since in the first $p-1$ steps we have used $p-1$ boxes, $62$ boxes are sufficient. Done.