Balkan Mathematical Olympiad

The required minimum is $n=2^k+k-1$.

In this case the game can be played indefinitely by choosing the last $k+1$ boxes, $b_{2^k-1},b_{2^k},\dots ,b_{2^k+k-1}$, at each step: At step $r$, if box $b_{2^k+i-1}$ has exactly $m_i$ coins, then $\lceil m_i/2\rceil$ coins are removed from that box, unless $i\equiv r-1(\mathrm{mod}k+1)$, in which case $2^k+i-1$ coins are added. Thus, after step $r$ has been performed, box $b_{2^k+i-1}$ contains exactly $\lceil m_i/2\rceil$ coins, unless $i\equiv r-1(\mathrm{mod}k+1)$, in which case it contains exactly $m_i+2^k+i-1$ coins. This game goes on indefinitely, since each time a box is supplied, at least $2^k-1$ coins are added, so it will then contain at least $2^k$ coins, good enough to survive the $k$ steps to its next supply.

We now show that no smaller value of $n$ works. So, let $n\le 2^k+k-2$ and suppose, if possible, that a game can be played indefinitely. Notice that a box currently containing exactly $m$ coins survives at most $w=\lceil {\log }_{2}m\rceil$ withdrawals; this $w$ will be referred to as the weight of that box. The sum of the weights of all boxes will referred to as the total weight. The argument hinges on the lemma below, proved at the end of the solution.

Lemma. Performing a step does not increase the total weight. Moreover, supplying one of the first $2^k-2$ boxes strictly decreases the total weight.

Since the total weight cannot strictly decrease indefinitely, $n>2^k-2$, and from some stage on none of the first $2^k-2$ boxes is ever supplied. Recall that each step involves a $(k+1)$-box choice. Since $n\le 2^k+k-2$, from that stage on, each step involves a withdrawal from at least one of the first $2^k-2$ boxes. This cannot go on indefinitely, so the game must eventually come to an end, contradicting the assumption.

Consequently, a game that can be played indefinitely requires $n\ge 2^k+k-1$.

Proof of the Lemma. Since a withdrawal from a box decreases its weight by at least 1, it is sufficient to show that supplying a box increases its weight by at most $k$; and if the latter is amongst the first $2^k-2$ boxes, then its weight increases by at most $k-1$. Let the box to be supplied be $b_i$ and let it currently contain exactly $m_i$ coins, to proceed by case analysis:

If $m_i=1$, the weight increases by $\lfloor {\log }_2(i+1)\rfloor \le \lfloor {\log }_2(2^k+k-1)\rfloor \le \lfloor {\log }_2(2^{k+1}-2)\rfloor \le k$; and if, in addition, $i\le 2^k-2$, then the weight increases by $\lfloor {\log }_2(i+1)\rfloor \le \lfloor {\log }_2(2^k-1)\rfloor =k-1$.

If $m_i=2$, then the weight increases by $\lfloor {\log }_2(i+2)\rfloor -\lfloor {\log }_{2}2\rfloor \le \lfloor {\log }_2(2^k+k)\rfloor -1\le k-1$.

If $m_i\ge 3$, then the weight increases by $$\begin{array}{rl}\lfloor {\log }_2(i+m_i)\rfloor -\lfloor {\log }_2{m}_i\rfloor & \le \lfloor {\log }_2(i+m_i)-{\log }_2{m}_i\rfloor +1\\ & \le \lfloor {\log }_2\left(1+\frac{2^k+k-2}{3}\right)\rfloor +1\le k,\end{array}$$ since $1+\frac{1}{3}(2^k+k-2)=\frac{1}{3}(2^k+k+1)<\frac{1}{3}(2^k+2^{k+1})=2^k$.

Finally, let $i\le 2^k-2$ to consider the subcases $m_i=3$ and $m_i\ge 4$. In the former subcase, the weight increases by $$\lfloor {\log }_2(i+3)\rfloor -\lfloor {\log }_{2}3\rfloor \le \lfloor {\log }_2(2^k+1)\rfloor -1=k-1,$$ and in the latter by $$\begin{array}{rl}\lfloor {\log }_2(i+m_i)\rfloor -\lfloor {\log }_2{m}_i\rfloor & \le \lfloor {\log }_2(i+m_i)-{\log }_2{m}_i\rfloor +1\\ & \le \lfloor {\log }_2\left(1+\frac{2^k-2}{4}\right)\rfloor +1\le k-1,\end{array}$$ since $1+\frac{1}{4}(2^k-2)=\frac{1}{4}(2^k+2)<2^{k-2}+1$. This ends the proof and completes the solution.