How to play the following game?

Question

Let $n,k\in\mathbb N$, $x\in(0,1/2)$.

You start $n$ empty bins; each can accommodate at most $k$ balls.

At each iteration, you choose an $x$ fraction of the non-full bins and add one ball to each. (if this number is not an integer, pick a subset that is larger than an $x$ fraction.)

How to maximize the number of iterations until all bins are full?

---

Intuitively, it seems that every time you should pick a subset of bins and add balls to it $k$ times in a row. This would give a bound of $\approx\Omega(k\log_{1/x} n)$ iterations. Is it possible to make more iterations? How can we prove that this is optimal?

---

Answer 1

I don't have a proof at the moment that your strategy is the optimum one--I suspect that it is though. For now at least though, We can show your bound is at least, asymptotically optimum.

On the one hand, if $m$ is the number of non-full bins at the start of round $i$, then you will be adding $xm$ balls. But at most $km$ balls are needed to be added to end the game. So at each round you are reducing the number of balls by at least a $u = x/k$ fraction--The number of balls you need to add to finish the game at the end of Round $i$ is now $(1-u)$ times what it was at the beginning of Round $i$ where $u$ is at least $x/k$. So this gives an upper bound of the most number of rounds.

On the other hand, if you pick your strategy, then $x<1/2$ implies that until you are left with at most one unfilled bin, then you are reducing the number of balls by no more than a $2u$-fraction. Indeed, as long as you have $m \geq 2$ unfilled bins, you will have at least $(1-\lfloor xm \rfloor) \geq m/2$ completely empty bins. So you are adding $xm$ balls that round but you will need to add at least $k(1-\lfloor xm \rfloor) \geq km/2$ balls to finish the game. So at each round you will have added at most only a $\frac{xm}{km/2} =\frac{2x}{k}$-fraction of the balls you need to add to finish the game.

So your strategy will at least come close to the most number of rounds possible.