Pagini: [1]   În jos
 Ajutor Subiect: Problem: Marbles Game - solution  (Citit de 3332 ori) 0 Utilizatori şi 1 Vizitator pe acest subiect.
Cosmin
Echipa infoarena
Nu mai tace

Karma: 351
Deconectat

Mesaje: 1.799

 « : Februarie 21, 2016, 23:59:25 »

http://www.infoarena.ro/blog/marble-game
 Memorat
andreitheo87
Strain

Karma: 13
Deconectat

Mesaje: 15

 « Răspunde #1 : 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?
 Memorat
Cosmin
Echipa infoarena
Nu mai tace

Karma: 351
Deconectat

Mesaje: 1.799

 « Răspunde #2 : Februarie 28, 2016, 20:47:39 »

Yes. Actually I didn't think through the 2. There is no 0 case .
 Memorat
 Pagini: [1]   În sus
Schimbă forumul: