Problem: Marbles Game - solution

[•Cosmin]

http://www.infoarena.ro/blog/marble-game

[•andreitheo87]

Very neat! I would have never thought of self-edges.

(3) seems non-trivial (unless I miss something). I will try to sketch my idea of the proof:

1. Assume there is at least one 0.
Let X be the number of 0s and (N-X) the number of non 0s.
There are X self-edges (positions with 0 marbles).
Any Y consecutive non 0s give Y incoming edges  - the previous 0 position could have had 1..Y marbles. So in total N-X incoming non-self edges.
That gives a total of "at least" N incoming edges. If we consider (1) we get "at least" == "exactly".

2. There is no 0.
Let MIN=the minimum number of marbles in any cup.
Subtract MIN marbles from each cup (that's N*MIN marbles in total), apply 1. and add N*MIN marbles to each starting position for a move.

Cosmin, did you have a similar idea in mind?

[•Cosmin]

Yes. Actually I didn't think through the 2. There is no 0 case .