Problem: Marble Game - Solution

Cosmin Negruseri
21 februarie 2016

Here's the statement again:

M marbles are placed in N cups which are arranged in a circle. One move consists in choosing a cup, taking all the marbles within that cup and placing them one by one in the following cups in clockwise order (since the cups are in a circle you might end up putting marbles in the original cup as well).

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)

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). (2)
We can apply one move on each cup.

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)

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.