Titlul: Problem: Marbles Game - solution Scris de: Cosmin Negruseri din Februarie 21, 2016, 23:59:25 http://www.infoarena.ro/blog/marble-game
Titlul: Răspuns: Problem: Marbles Game - solution Scris de: Teodorescu Andrei-Marius din Februarie 24, 2016, 01:56:38 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? Titlul: Răspuns: Problem: Marbles Game - solution Scris de: Cosmin Negruseri din Februarie 28, 2016, 20:47:39 Yes. Actually I didn't think through the 2. There is no 0 case :).
|