Given two placements A and B of marbles in cups, how can we tell if we can reach B starting from A.
Solution:
The state with all marbles in the first cup can always be reached. (1)
*Solution:*
*The state with all marbles in the first cup can always be reached. (1)*
While we can find another cup with marbles, we apply one move on that cup. Marbles will move around the circle and from time to time fall into the first cup. Since we never make a move on the first cup, eventually all the marbles will end up in it. You guys figured this part in the comments.
Every state A has n outgoing edges (they can be self edges), since we can apply a move on each cup. (2)
*Every state A has n outgoing edges (they can be self edges). (2)*
We can apply one move on each cup.
Every state A has n incoming edges (self edges included).(3)
*Every state A has n incoming edges (self edges included). (3)*
Here's an example: Let A be 0 1 2 1 0 0.
We can reach this state from 3 0 1 0 0 0 applying a move on cup 1, 2 0 1 1 0 0 applying a move on cup 1, 1 0 2 1 0 0 applying a move on cup 1, 0 1 2 1 0 0 applying a move on cup 5 (self edge), 0 1 2 1 0 0 applying a move on cup 6 (self edge)
We can reach this state from 0 1 2 1 0 0 applying a move on cup 1 (self edge), 3 0 1 0 0 0 applying a move on cup 1, 2 0 1 1 0 0 applying a move on cup 1, 1 0 2 1 0 0 applying a move on cup 1, 0 1 2 1 0 0 applying a move on cup 5 (self edge), 0 1 2 1 0 0 applying a move on cup 6 (self edge)
From (2), (3) the graph is eulerian, from (1) the graph is also connected. It follows that we have a cycle that goes through all edges and nodes. Which means we can reach any state from any other state.
From (2), (3) the graph is Eulerian, from (1) the graph is also connected. It follows that we have an *Eulerian cycle* that goes through all edges and nodes. Which means we can reach any state from any other state.
Thanks Andrei Dragus for the neat problem.
Thanks *Andrei Dragus* for the neat problem.
