Pagini: [1]   În jos
  Imprimă  
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 Deconectat

Mesaje: 1.799



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

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


Karma: 13
Deconectat Deconectat

Mesaje: 15



Vezi Profilul
« 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 Deconectat

Mesaje: 1.799



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

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

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines