Let $n$ be a positive integer. We have $n$ boxes where each box contains a nonnegative number of pebbles. In each move we are allowed to take two pebbles from a box we choose, throw away one of the pebbles and put the other pebble in another box we choose. An initial configuration of pebbles is called solvable if it is possible to reach a configuration with no empty box, in a finite (possibly zero) number of moves. Determine all initial configurations of pebbles which are not solvable, but become solvable when an additional pebble is added to a box, no matter which box is chosen.

Proposed by Dan Schwarz, ROU

The answer is any configuration with $2 n-2$ pebbles which has even numbers of pebbles in each box.
Number the boxes from 1 through $n$ and denote a configuration by $x=\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ where $x_{i}$ is the number of pebbles in the $i$ th box. Let

$$
D(x)=\sum_{i=1}^{n}\left\lfloor\frac{x_{i}-1}{2}\right\rfloor
$$

for a configuration $x$. We can rewrite this in the form

$$
D(x)=\frac{1}{2} N(x)-n+\frac{1}{2} O(x)
$$

where $N(x)$ is the total number of pebbles and $O(x)$ is the number of boxes with an odd number of pebbles for the configuration $x$.

Note that a move either leaves $D$ the same (if it is made into a box containing an even number of pebbles) or decreases it by 1 (if it is made into a box with an odd number of pebbles). As $D$ is nonnegative for any configuration which does not have any empty boxes, it is also nonnegative for any solvable configuration. On the other hand, if a configuration has nonnegative $D$, then making $m_{i}=\left\lfloor\left(x_{i}-1\right) / 2\right\rfloor$ moves from the $i$ th box into $m_{i}$ empty boxes for each $i$ with $m_{i}>0$ fills all boxes as $D(x) \geq 0$ means $\sum_{m_{i}>0} m_{i} \geq$ (number of empty boxes).

As $N(x)$ and $O(x)$ have the same parity, a configuration $x$ is solvable exactly when $O(x) \geq 2 n-N(x)$, and unsolvable exactly when $O(x) \leq 2 n-2-N(x)$. In particular, any configuration with $2 n-1$ pebbles is solvable, and a configuration with $2 n-2$ pebbles is unsolvable if and only if all boxes contain even numbers of pebbles.

Suppose that $x^{\prime}$ is obtained from $x$ by adding a pebble in some box. Then $O\left(x^{\prime}\right)=$ $O(x)+1$ or $O\left(x^{\prime}\right)=O(x)-1$. If $x$ is unsolvable and $x^{\prime}$ is solvable, then we must have $O(x) \leq 2 n-2-N(x)$ and $O\left(x^{\prime}\right) \geq 2 n-N\left(x^{\prime}\right)=2 n-1-N(x)$, and hence $O\left(x^{\prime}\right)=O(x)+1$. That is, the pebble must be added to a box with an even number of pebbles. This can be the case irrespective of where the pebble is added only if all boxes contain even numbers of pebbles, and $0=O(x) \leq 2 n-2-N(x)$ and $1=O\left(x^{\prime}\right) \geq 2 n-1-N(x)$; that is, $N(x)=2 n-2$.