combinatorics – Can you win the monochromatic urn game?


In the (monochromatic) urn depletion game, you are given $n$ vases, each containing some number of balls $a_1,ldots, a_n geq 0$. You win the game if you can remove all of the balls from the vases; you must draw them one at a time, and the only rule is that you cannot draw from the same vase twice in a row.

The problem is to decide, given the occupancy numbers $a_1, ldots, a_n$, whether the game is winnable.

Example: The game (AAA, A) (three in one vase; one in another) is unwinnable.


I’ve already got an efficient algorithm for winning the game: at each step, draw from the vase with the largest number of balls $a_i$ (among vases you can legally choose). If the game is winnable at all, this algorithm will win it.

So instead of an algorithm, I am looking for a property of the numbers $a_1,ldots, a_n$ which would enable someone to calculate whether the game is winnable. Evidently there’s a formula implicit in the algorithm above, but I wonder if it’s possible to find an explicit and simple one.

I’ve tried establishing the result for small $n$: if $n=1$, $a_1$ must be 0 or 1. If $n=2$, then $|a_1-a_2|$ must be 0 or 1. If $n=3$, the condition is slightly more complicated but might be expressible in terms of the differences $|a_i-a_j|$.

(I previously asked a related question about the multicolor version of this game)