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:
- You may only remove one ball at a time.
- You may not pick from the same urn twice in a row.
- 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.
from Hot Weekly Questions - Mathematics Stack Exchange
user326210
Post a Comment