Marbles Elimination
Marbles is a solitaire game played on an undirected graph $G$, where each vertex has zero or more marbles. A single move in this game consists of removing two marbles from a vertex $v$ and adding one marble to an arbitrary neighbor of $v$. Note that the vertex $v$ must have at least two marbles on it before the move.
The Marbles Elimination problem asks: given a graph $G=(V, E)$ and a marble count $p(v)$ for each vertex $v$, is there a sequence of valid moves that removes all but one marble?
Example: Consider a triangle graph with vertices $A, B, C$ and edges $\{A,B\}, \{B,C\}, \{C,A\}$.
If we start with marbles $A=2, B=1, C=1$ (total = 4):
- Move from $A$ to $B$: now $A=0, B=2, C=1$
- Move from $B$ to $C$: now $A=0, B=0, C=2$
- Move from $C$ to $A$: now $A=1, B=0, C=0$
We end with exactly 1 marble.
Part A
Consider a path graph $P_4$ with vertices $A - B - C - D$ (edges $\{A,B\}, \{B,C\}, \{C,D\}$).
Starting configuration: $A=1, B=2, C=1, D=1$ (total = 5 marbles).
Can the game be won (reduced to exactly 1 marble)?
Part B
Consider a cycle graph $C_4$ with vertices $A - B - C - D - A$ (edges $\{A,B\}, \{B,C\}, \{C,D\}, \{D,A\}$).
Starting configuration: $A=2, B=1, C=1, D=1$ (total = 5 marbles).
Can the game be won (reduced to exactly 1 marble)?
Part C
Consider the general Marbles Elimination decision problem with the following setup:
- Input: A graph $G$ with $n$ vertices, where one designated vertex $w$ has 2 marbles and all other vertices have 1 marble each.
- Output: TRUE if we can reduce to exactly 1 marble, FALSE otherwise.
What is the complexity of this problem?
Hints
Try a few move sequences. What happens when marbles get pushed to the endpoints?
Follow the cycle: move from $A$ to $B$, then from $B$ to $C$, and so on.