infoarena

Comunitate - feedback, proiecte si distractie => Blog => Subiect creat de: Cosmin Negruseri din Februarie 21, 2016, 23:59:25



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 :).