Consider the following ball games, which looks like very intuitive and simple but I have tried for a long time.
Assuming we have $M$ identical boxes and $N$ identical balls, we distribute these $N$ balls among the $M$ boxes in some way. Then we start removing balls (without replacement) according to the following rules: First, we observe which boxes contain balls. From those boxes, we randomly select one box with equal probability and remove a ball from it (each ball within the same box has an equal probability of being selected). We stop removing balls when only one box remains with balls.
Question: How should we distribute these $N$ balls among the $M$ boxes initially in order to maximize the expected number of balls we remove?
The intuition is that average distribution is the optimal, and I have not found the counterexample.
What I have tried: We can formulate this problem as MDP. Let $X = (x_1,x_2,\ldots,x_M)\in \mathbb N^M,$ where $x_i$ denotes the number of balls contained by the $i-$th box, $\mathbf e_i = (0,\ldots,0,1,0,\ldots,0)\in \mathbb R^M $, where the $i-$th element is $1$, and $\mathcal{T}$ denotes the number of balls we totally remove. Next, we observe that since the boxes are homogeneous, the order in which the boxes are arranged does not affect the result. Therefore, we can assume that the boxes are sorted in descending order based on the number of balls they contain. Therefore, we can assume that $x_1\ge x_2 \ge \dots \ge x_M$.
Then we can formulate this question as a Markov process $\{X_t, t\ge 0\},$ where $X_t = (x_{1t},\ldots,x_{Mt})\in \mathbb N^M$ and $x_{it}$ denotes the number of balls in the $i-$th box after the $t-$th ball is taken out. Moreover, denote $\Delta(N,M) \triangleq \left\{X\triangleq (x_1,\ldots,x_M)\in \mathbb{N}^M\bigg|\displaystyle\sum\limits_{i = 1}^M x_i = N, x_1\ge x_2 \ge \dots \ge x_M\right\}$, then the question we are interested about is the following optimization problem: Given any $N\ge M\ge 2,$
$\max\limits_{X\in \Delta(N,M)}V(X)\triangleq\mathbb E[\mathcal T\mid X_0 = X],$
with boundary condition
$V(m\cdot \mathbf e_k) = 0,\quad \forall\, k = 1,\ldots,M, m\in\mathbb N$
Let's start by analyzing the objective function. Using the law of iterated expectation, \begin{align*} V(X) & = \mathbb E_{X_1}[\mathbb E[\mathcal{T}\mid X_0 = X, X_1]]\\ &= \displaystyle\sum\limits_{k = 1}^M \frac{1}{\sum\limits_{k = 1}^M\mathbb 1\{x_{k}\ge 1\}}\bigg( 1+\mathbb E[\mathcal T\mid X_1 = X-\mathbf{e}_k] \bigg)\cdot \mathbb 1\{x_k\ge1\}\\ &= 1+\frac{1}{\sum\limits_{k = 1}^M\mathbb 1\{x_{k}\ge 1\}}\cdot\displaystyle\sum\limits_{k = 1}^M V(X-\mathbf{e}_k)\cdot \mathbb1\{x_k\ge 1\}. \end{align*} We further establish the boundary conditions by
$V(X) = 0, \exists\, k = 1,\ldots,M, x_k<0.$
Then, we can obtain the following recursion
$V(X) = 1+\frac{1}{\sum\limits_{k = 1}^M\mathbb 1\{x_{k}\ge 1\}}\cdot\displaystyle\sum\limits_{k = 1}^M V(X-\mathbf{e}_k), $
with the boundary condition
$V(X) = 0, \exists\, k = 1,\ldots,M, x_k<0, \text{and},V(m\cdot \mathbf e_k) = 0,\quad \forall\, k = 1,\ldots,M, m\in\mathbb N.$
Then, I have tried to prove some useful propositions by this recursion. However, I only managed to prove that $V(X)<V(X+\mathbf e_k), \forall k=1,\dots,M$, which is quite intuitive. I guess the desired result ---- "distributing averagely is the optimal" may not be proved by induction, but I still write down what I tried for your reference.
