The best way to put balls into boxes

Question

There are $36$ identical balls, $12$ boxes numbered $1$ to $12$, and two $6$-sided dice.

You start by placing each of the balls into one of the boxes. You then repeatedly roll the dice and take a ball from the box numbered with their sum. If there isn't any ball in that box, you just skip the round.

What is the best strategy to assign the balls to minimize the expected number of rounds needed to take all balls out?

I know how to use min-max Inclusion–exclusion principle to solve the problem which the balls are already assigned. But is there an effecient way to find out the best strategy?

And if there is a way to answer the question when the possibility to take a ball from the i-th box is $p_i$.

Thank you for your time.

Answer 1

You know that rolling two dices has 36 different outcomes and 12 different sums.
You should try to see how many different rolls has $i$ as sum and put that many balls in the box number $i$.
For example in the box number $7$ you should put $6$ different balls becuse rolling the dices you can get a $7$ in $6$ different ways $\{(1,6),\dots,(6,1)\}$.
In this way you are more likely to always remove a ball when you throw the dices.

Answer 2

You can solve the problem recursively as follows. Let $V(n_2,n_3,\dots,n_{12})$ be the expected number of rounds if there are $n_i$ balls in box $i$. Then $V(0,0,\dots,0)=0$ and otherwise \begin{align}V(n_2,n_3,\dots,n_{12}) = 1 &+ p_2 V((n_2-1)^+,n_3,\dots,n_{12}) \\ &+ p_3 V(n_2,(n_3-1)^+,\dots,n_{12}) \\ &+ \dots + p_{12} V(n_2,n_3,\dots,(n_{12}-1)^+), \end{align} where $x^+ = \max(x,0)$. Equivalently, \begin{align}V(n_2,n_3,\dots,n_{12}) = \left(1\right. &+ [n_2>0]p_2 V(n_2-1,n_3,\dots,n_{12}) \\ &+ [n_3>0]p_3 V(n_2,n_3-1,\dots,n_{12}) \\ &+ \dots + \left.[n_{12}>0]p_{12} V(n_2,n_3,\dots,n_{12}-1)\right) \\ &/ \left(1 - \sum_{i: n_i=0} p_i\right) \end{align} Now take the minimum of $V(n_2,n_3,\dots,n_{12})$ over $(n_2,n_3,\dots,n_{12})$ such that $\sum_{i=2}^{12} n_i=36$.

Here are optimal results for up to $18$ balls: \begin{matrix} n_2 &n_3 &n_4 &n_5 &n_6 &n_7 &n_8 &n_9 &n_{10} &n_{11} &n_{12} &\sum_i n_i &V \\ \hline 0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0.0000 \\ 0 &0 &0 &0 &0 &1 &0 &0 &0 &0 &0 &1 &6.0000 \\ 0 &0 &0 &0 &1 &1 &0 &0 &0 &0 &0 &2 &9.9273 \\ 0 &0 &0 &0 &1 &1 &1 &0 &0 &0 &0 &3 &12.5045 \\ 0 &0 &0 &1 &1 &1 &1 &0 &0 &0 &0 &4 &15.4760 \\ 0 &0 &0 &1 &1 &1 &1 &1 &0 &0 &0 &5 &17.7678 \\ 0 &0 &0 &1 &1 &2 &1 &1 &0 &0 &0 &6 &19.7617 \\ 0 &0 &0 &1 &2 &2 &1 &1 &0 &0 &0 &7 &22.2788 \\ 0 &0 &0 &1 &2 &2 &2 &1 &0 &0 &0 &8 &24.3058 \\ 0 &0 &1 &1 &2 &2 &2 &1 &0 &0 &0 &9 &26.4305 \\ 0 &0 &1 &1 &2 &3 &2 &1 &0 &0 &0 &10 &28.2668 \\ 0 &0 &1 &1 &2 &3 &2 &1 &1 &0 &0 &11 &29.8650 \\ 0 &0 &1 &2 &2 &3 &2 &1 &1 &0 &0 &12 &31.9219 \\ 0 &0 &1 &2 &2 &3 &2 &2 &1 &0 &0 &13 &33.6995 \\ 0 &0 &1 &2 &3 &3 &2 &2 &1 &0 &0 &14 &35.4759 \\ 0 &0 &1 &2 &3 &3 &3 &2 &1 &0 &0 &15 &37.0159 \\ 0 &0 &1 &2 &3 &4 &3 &2 &1 &0 &0 &16 &38.4390 \\ 0 &0 &1 &2 &3 &5 &3 &2 &1 &0 &0 &17 &40.6388 \\ 0 &0 &1 &2 &4 &5 &3 &2 &1 &0 &0 &18 &42.6650 \\ \end{matrix}