Team Selection Test for EGMO 2019

Answer: 45.

The maximal value of $k$ can not be greater than 45. Indeed, if $k\ge 46$, then since $45\cdot k>2019$ it is possible that at the beginning there are $k$ heaps each containing at most 45 beads. Obviously in this case one can not get $k$ heaps with pairwise distinct number of beads, since the heap with most beads should contain at least 46 beads.

Lemma. If $k$ heaps contain at least $k(k-1)+1$ beads in total, then we can get $k$ heaps containing $1,2,\dots ,k$ beads.

Proof by induction on $k$. $k=1$ is obvious. Suppose that the lemma is true for $k=n$. Consider $n+1$ heaps with $n(n+1)+1$ beads in total. Then the heap with maximal number of beads contains at least $n+1$ beads. If the heap with maximal number of beads contains exactly $n+1$ beads, the remaining $n$ heaps contain $n(n+1)+1-(n+1)=n^2\ge n(n-1)+1$ and by inductive hypothesis we can get $n$ heaps containing $1,2,\dots ,n$ beads. Since we also have a heap having $n+1$ beads we are done. If the heap with maximal number of beads contains more than $n+1$ beads, let us divide it into two heaps so that one of these two new heaps, say $H(n+1)$, contains $n+1$ beads. There are $n+1$ heaps except $H(n+1)$ containing $n(n+1)+1-(n+1)=n^2$ beads in total. The smallest heap among these $n+1$ heaps contains at most $n-1$ beads. If we remove it then the remaining $n$ heaps contain at least $n^2-(n-1)=n(n-1)+1$ beads in total. By inductive hypothesis we can get $n$ heaps containing $1,2,\dots ,n$ beads. Since we also have a heap $H(n+1)$ we are done.

Since $2019>45\cdot 44+1$ by lemma one can get heaps containing $1,2,\dots ,45$ beads. Done.