9
$\begingroup$

In the urn depletion game, you are given several transparent urns containing various colored balls. (For the purposes of this problem, let us assume there are $k=2$ different available ball colors, red and blue.) You can easily see all of the contents of all of the urns, and pick out any ball from them at will. You win the game if you can remove all of the balls from the urns, subject to the following constraints:

  1. You may only remove one ball at a time.
  2. You may not pick from the same urn twice in a row.
  3. I will tell you, each time, what color of ball you must remove. Concretely, assume I give you a list in advance describing what color you must pick out each turn.

The decision problem is: Given a setup of urns and colored balls, and given the ordered list of color requirements, is it possible to win?


Example: You have urns containing [RB] [RB]. If the instructions are to remove them in the order red, blue, blue, red you can win. In contrast, if you must remove them in the order red, blue, red, blue, there is no way to win because you cannot draw from the same urn twice in a row.


I am wondering whether this problem is in P, or whether, for example, it's NP-complete. It's a little similar to some other NP-complete problems, but it also seems at least superficially less expressive and I haven't been able to find a reduction.

I've found several special cases that are in P.

  • I know that if there's only one ball color ($k=1$), then the problem is in P. My algorithm is to always remove a ball from the urn with the most balls (among the urns you're allowed to pick), breaking ties arbitrarily. If it's possible to win, this algorithm will win. (Note that it's still possible to have an unwinnable game even if $k=1$, if there's too great a discrepancy in urn contents. For example, the game [R] [RRRR] is unwinnable.)

  • I also know that if all balls have a unique color, then the problem is also in P. This is because then the color list uniquely determines the path you take (no branching factors), and you can check whether it's valid in polynomial time. More generally, if the color of the ball uniquely determines the urn it's in, then the problem is in P.

  • And if there are only two urns, then no matter how many colors $k$ there are, the path must zigzag between them, and there are only two possible paths. You can check in polynomial time whether either path is legal.

But I haven't solved the $k=2$ case, and I'm stumped on an algorithm or reduction.

Edit: I've found if we allow for an unlimited number of colors, the problem becomes NP-complete, but I'm not sure about just two colors.

Edit: As @Artimis points out below, if we restrict to problems where the number of urns is at most U, or where the number of balls per urn is at most B, this special case can be shown to be in P, as there are a polynomial number of things to check. Hence if we are to show that the problem is NP-complete, the reduction must reasonably employ an unbounded number of urns and balls per urn.

$\endgroup$

1 Answer 1

1
$\begingroup$

This is not a complete solution.

However, I do have 2 sub-cases that are in P for trivial reasons. Perhaps these can give a base case for someone else to show the problem is in P, or inspire some similarity with another NP-complete problem. In both cases, we will reduce to a polynomially sized graph of possible settings of balls in urns.

If we bound the number of urns to be $\leq U,$ then this problem can be solved in polynomial time. Let $R_i, B_i$ be the number of red and blue balls respectively in the $i$th urn. In this case, we make a vertex for every tuple $(r_1, b_1, r_2, b_2, \ldots, r_U, b_U, j),$ with $r_i < R_i, b_i < B_i,$ and $j < U.$ Think of each tuple as indicating how many balls of each color remains in each urn, with the last entry indicating what urn we last took from.

We then put a directed edge between $2$ vertices if we can get from one state to the other by removing a ball of the right color (note we can compute what step we're on, simply by checking the number of balls already removed. ie $\sum_i R_i - r_i + \sum_i B_i - b_i$).

If we have $n$ balls, there are at most $U n^{2U}$ vertices in our graph. A solution consists of a path from any of the vertices $(R_1, B_1, \ldots, R_U, B_U, i)$ to $(0, 0, \ldots, j).$ So we can just create the graph and perform depth first search. It's in P, QED.

A very similar argument works if the number of balls in any urn is at most $B.$ This time, we note that there are only a finite number $M$ of ways to put $\leq B$ balls (of any color) into an urn, number these possible states $u_1, \ldots u_M.$ (So, for example, $u_1$ may indicate an urn with just $1$ red ball. $u_2$ might indicate an urn with $3$ red and $2$ blue balls, etc).

If there are $n$ balls, create a vertex for each tuple $(a_1, \ldots, a_M, j)$ with $a_i < n.$ The values $a_i$ indicates the number of urns of type $u_i$ (ie, if $a_1=2$ and we use the numbering above, that means we have $2$ urns with just $1$ red ball in them.). We add an edge between two vertices if we can get from one to the other by removing a ball (and, again, we know how many balls have been removed from our initial state, so we can restrict to just those removals that agree with our given ordering).

This gives us a directed graph with $M n^M$ vertices, and hence we can just look for a path from our initial set of urns to one of the $(0, \ldots, 0, i)$ vertices. So, again, we just create the graph and run depth first search.

So, restricting either the number of urns or the number of balls per urn gives us easy problems. Any reduction with a known NP-complete problem will need to use both arbitrarily many urns and balls per urn. Hope that helps.

$\endgroup$
2
  • $\begingroup$ I see! With urns bounded by U, the problem size is determined by the total number of balls n. There are ~$n^2$ possible contents per urn, hence polynomial number of game states ~$n^{2U}$ (# balls of each color per urn). We can efficiently check whether the all-empty state is legally reachable. Or with balls per urn bounded by B, the problem size is determined by the total number of urns u. There are M ~ $B^2$ possible contents for any urn, hence again polynomial number of game-states $u^M$ (count the # of urns of each content type) which we can efficiently check. With either bound, it's in P. $\endgroup$
    – user326210
    Jul 18, 2020 at 11:34
  • $\begingroup$ @user326210 exactly! Add a little bit of extra data to track what urn you last took from and that's the entire idea above. $\endgroup$ Jul 18, 2020 at 13:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .