Can you win the monochromatic urn game?

Question

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|$.

It also seems to me that a game instance is solvable just if you can find a perfect or near-perfect matching in a particular graph—the graph has one node for every ball in every vase, and each ball is connected to all the balls in the other vases. Rationale: Given such a matching, you can win the game as follows: iterate over the edges in an arbitrary order; for each edge, at least one of the two endpoints will belong to a legal urn; draw that one, then the other. Conversely, a winnable game has at least one winning sequence of draws. Form a [near]-perfect matching by pairing consecutively drawn balls, starting with the first and second, third and fourth, etc.

The graph matching approach seems like a potentially fruitful avenue, but I don't know much about matching or matching polynomials to do much more.

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

Answer 1

The game is winnable if and only if the largest vase has at most one more ball than the rest of them put together:

$$\max_i a_i \leq \Sigma_i (a_i) - \max_i (a_i) + 1$$

Proof ($\Rightarrow$) You can see that the condition is necessary: if it fails, then you can never empty the largest vase, even if you draw from it as often as possible, i.e. every other turn.

$(\Leftarrow)$. To see that the condition is sufficient (that every winnable game has this property), fix a specific game $\{a_i\}$ and suppose it is winnable. If it is winnable, then you can empty all the vases by drawing in some specific legal sequence of vases $v_1,v_2,v_3,\ldots$.

Now we play the game in reverse, returning the balls to the vases, and see that the invariant is maintained (the game is winnable and satisfies the condition). Initially, all the vases are empty and the condition holds. If there were one ball in a vase, the invariant would also hold.

We will be returning the balls in pairs each time, except for perhaps the first step: if the total number of balls is odd, return the first ball $v_1$ alone. In every subsequent step, return the next two balls to their vases. These balls belong to different vases, since $\{v_i\}$ is a legal sequence of moves. Hence (a) at least one of the balls belongs to a different vase than the last ball we returned so the game is still winnable, and (b) the game still satisfies the condition, since the max increases by at most one, while the sum increases by two. By induction, the game will be winnable and satisfy the condition at every step. In the final step, we have reconstructed the entire game through the invariant-preserving process, which establishes that it satisfies the condition, QED.

Answer 2

The intuitive answer looks like

Let $s=\sum\limits_{i=1}^n a_i$ and $a_{(n)}=\max\limits_{1\le i\le n} a_i$.

Then the game is winnable iff $a_{(n)} \le s - a_{(n)} +1$, i.e. iff $a_{(n)} \le \left\lceil\frac{s}2\right\rceil $

Answer 3

** Not an answer, but a suggestion **

Suppose you generalize the problem to this: A "game" is a sequence of natural numbers $$ a_1, \ldots, a_n $$ together with a number $k$ between $1$ and $n$. A move in a game consists of picking any number $i$ from $1$ to $n$ with $a_i \ne 0$ and $i \ne k$; such a move changes the game to $$ (a_1, ..., a_i - 1, \ldots, ...a_n; i) $$ i.e., the $i$th slot is reduced by $i$ and the special index is changed to $i$.

A game is bad if all $a_i = 0$ except for $a_k$, which is nonzero; a game is won if all $a_i = 0$.

You can now recursively define a function $$ W(a_1, \ldots, a_n, k) $$ that's "True" if either the current game is won, or there's an $i$ such that $$ W(a_1, \ldots, a_i - 1, \ldots n, i) = True $$ and False otherwise.

Finally, you can see the the numbers $(a_1, \ldots, a_n)$ have your special property exactly if $$ W(a_1, \ldots, a_n, 0; n+1) = True $$ i.e., if you set up a game where there's an extra vase (the $n+1$th one) that's just been emptied, and all the other vase-fullnesses are as specified.

For $n = 3$, for instance, this tells you that a 3-vase game is winnable is you can reduce it to a 2-vase game where the two vase amounts differ by $1$. Alternatively, you can construct all winnable 3-vase games by sprinkling balls into vases, without ever dropping two balls into the same vase in sequence. So because $$ (3, 4, 0) $$ is a winnable 2-vase game (expressed as a 3-vase game with an empty vase), so is $$ (93, 94, 4) $$ because you can get there by adding to each of 3, 2, 1 in sequence, four times, and then adding to each of 2,1, in sequence, 86 times.

Answer 4

The game is unwinnable iff the largest number is greater than or equal to the sum of all the others, plus 2. If the largest number is this big, then there are too few balls in the other vases to separate all the balls from this vase. If there are fewer balls than this in the largest vase we use induction to prove it is winnable.

Firstly if there is only 1 ball the game is trivially winnable,and if there are 2 balls they are in different vases so the games is again winnable. Suppose it is winnable when there are $n$ balls. If there are $n+1$ balls then remove a ball from the biggest number, and a ball from any other vase. Note that if a different vase now has the largest number it can have at most 1 more than the previous largest. The largest number still satisfies the condition and the smaller game is winnable.