IMO Team Selection Test 2

Answer: $M_n=3n-4$ and $f(a_1,a_2,\dots ,a_n)=3n-4$ if and only if $a_1=a_2=\cdots =a_n=3$.

First of all, we note that for every distribution, there exists a move such that $\max (a_1,\dots ,a_n)$ increases by at least 1, unless all the stones are in a single box. To see this, pick a box containing the highest number of stones, pick a different non-empty box and distribute the stones from that box such that at least one stone goes into the box containing the highest number of stones. It follows that $f(a_1,a_2,\dots ,a_n)\le 3n-\max (a_1,\dots ,a_n)$. Specifically, if $\max (a_1,\dots ,a_n)\ge 5$, then $f(a_1,a_2,\dots ,a_n)\le 3n-5$. The rest of the proof will follow from the following four claims.

Claim 1. If $\max (a_1,\dots ,a_n)=4$, then $f(a_1,a_2,\dots ,a_n)\le 3n-5$. Proof. Let $A_1$ be the box containing the highest number of stones, and $A_2$ be the box containing the second-highest number of stones. Note that we must have $a_1=4$ and $a_2\ge \frac{3n-4}{n-1}=3-\frac{1}{n-1}$. Since $a_2$ is integer and $n\ge 3$, that means $a_2\ge 3$. While there exists a box other than $A_1$ or $A_2$ containing 2 or more stones, do the move consisting of distributing the stones in that box in such a way that $A_1$ and $A_2$ each receive a stone. The distribution $b_1,\dots ,b_n$ we obtain by performing these moves has the properties that $b_3+\cdots +b_n\le n-2$ and that $b_1-b_2=a_1-a_2\le 1$. Therefore we have $b_1+b_2\ge 3n-(n-2)=2n+2$, from which it follows that $b_2=\frac{1}{2}(b_2+b_1)\ge \frac{1}{2}(b_1+b_2-1)\ge \frac{1}{2}(2n+1)=n+\frac{1}{2}$. Since $b_2$ is integer, we therefore have $b_2\ge n+1$. Now we can do a move consisting of distributing $A_2$'s stones in such a way that $A_1$ receives 2 stones. After that, while there exists a box other than $A_1$ that contains stones, we do a move consisting of distributing the stones in that box in such a way that $A_1$ receives 1 stone. Since $A_1$ receives at least two stones during one of the moves, and at least one during each of the other moves, the number of moves needed to make all boxes except $A_1$ empty is at most $3n-5$. $\square$

Claim 2. If $\max (a_1,\dots ,a_n)=3$, then $f(a_1,a_2,\dots ,a_n)\le 3n-4$. Proof. We make a random move and apply Claim 1 to the result. Then we are done in at most $1+(3n-5)=3n-4$ moves. $\square$

Claim 3. There are no moves so that the maximum $\max (a_1,\dots ,a_n)$ increases by 3 or more. Proof. We proceed by contradiction. To make a move in which a box receives more than 3 stones, the box that was distributed from in that move would have to contain at least $3n+1$ stones. This contradicts the fact that there are only $3n$ stones. To make a move in which a box receives exactly 3 stones, the box that was distributed from should contain at least $2n+1$ stones. Any box that contains the highest number of stones after this move, must contain at least $2n+4$ stones, as the maximum has increased by at least 3. That box therefore must also have contained at least $2n+1$ stones before this move. This requires $4n+2$ stones and is therefore a contradiction. $\square$

Claim 4. If $\max (a_1,\dots ,a_n)=3$, then $f(a_1,a_2,\dots ,a_n)\ge 3n-4$. Proof. Suppose for a contradiction that we can move all the stones into a single box in $3n-5$ or fewer moves. Because of Claim 3, there are no moves where the maximum increases by 3 or more. That means there are at least two moves where the maximum increases by 2. Such moves we will call large moves. Note that each box receives at least 1 stone on a big move. Let move $i$ be the first large move, and let move $j$ be the last large move. Since a large move can only be performed with a box containing at least $n+1$ stones and each box starts with 3 stones $i-1\ge (n+1)-3$, or equivalently $i\ge n-1$. Let $m$ be the number of empty boxes at the beginning of move $j$. Since each box contains at least 1 stone after move $i$, we must have made at least one move per box that is empty by the beginning of move $j$. Therefore $(j-1)-i\ge m$. Since each box receives at least 1 stone again, after move $j$ there are at most $m$ boxes containing exactly 1 stone; the other boxes contain at least 2 stones each. Since we don't make any more large moves after move $j$, it therefore takes at least $m+2(n-1-m)=2(n-1)-m$ moves afterwards to empty $n-1$ of the boxes. So the total number of moves is at least $$i+(j-i)+2(n-1)-m\ge (n-1)+(m+1)+2(n-1)-m=3n-2,$$ which contradicts our assumption that we could put all the stones into a single box in $3n-5$ or fewer moves. $\square$