Soluţii corecte: Angela Sandu, Lucian Niţă, Ionel-Vasile Pit-Rada, Marius Alecsandru, Aurel Ionescu, Claudiu Drăgan, Dan Bătalu, Emil Claudiu Man, Ştefan Gatachiu, Viorel Manta, Zoltan Szabo

 

Emil Claudiu Man, Ştefan Gatachiu, Zoltan Szabo:

Pentru fiecare găleată trebuie două mutări pentru a aduce două bile din celelalte două găleți, deci până acum trebuie cel puțin 6 mutări. Cum bilele colorate sunt deja pline, prima mutare constă în ducerea unei bile în găleata albă. Deci sunt cel puțin 7 mutări.

 

Angela Sandu:

Mut o bila albastra din galeata rosie in galeata alba.

Mut bila rosie din a doua galeata in galeata rosie unde am creat un loc.

Mut bila galbena din prima galeata in galeata galbena, apoi pun si bila rosie din a treia galeata in prima si astfel am completat galeata rosie.

Bila albastra din a doua galeata o pun in a treia, completez si galeata galbena cu bila din cea albastra si apoi mut bila albastra pusa la prima mutare din galeata alba in cea albastra.

Am terminat in 7 mutari.

 

Lucian Niţă:

Bila galbena din galeata rosie in galeata alba
Bila rosie din galeata albastra in galeata rosie
Bila albastra din galeata galbena in galeata albastra
Bila galbena din galeata albastra in galeata galbena
Bila albastra din galeata rosie in galeata albastra
Bila rosie din galeata galbena in galeata rosie
Bila galbena din galeata alba in galeata galbena

7 mutari

 

Aurel Ionescu:

                    RAG  RAG  RAG  _ _ _

1 mutare       R_G  RAG  RAG  A _ _

2 mutari        RRG  _AG  RAG  A _ _

3 mutari        RR_  GAG  RAG  A _ _

4 mutari        RRR  GAG  _AG  A _ _

5 mutari        RRR  G_G  AAG  A _ _

6 mutari        RRR  GGG  AA_  A _ _

7 mutari        RRR  GGG  AAA  _ _ _

 

Ştefan Gatachiu:

Generalizare

Fie n+1 urne numerotate de la 0 la n. În fiecare urnă de la 1 la n se află câte n bile numerotate de la 1 la n. Urna 0 este goală. Fiecare urnă poate conține cel mult n bile. O mutare constă în extragerea bile i din urna j și introducerea ei în urna k. Să se mute, printr-un număr minim de mutări, toate bilele cu numărul k în urna cu numărul k, pentru k de la 1 la n.

Soluție

Ca și în raționamentul de mai sus, pentru fiecare urnă trebuie n-1 mutări pentru a aduce bilele, deci sunt n(n-1) mutări. Prima mutare trebuie făcută în urna 0. Deci numărul minim de mutări este n(n-1)+1.

Voi introduce următoarele notații pentru mutări:

- mutare simplă (scoaterea unei bile dintr-o urnă și introducerea ei în altă urnă)

            i(j)→(k)  (bila i din urna j se mută în urna k)

- mutare dublă (două mutări succesive constând în interschimbarea bilelor din două urne)

            i(j)↔j(i) (bila i din urna j se interschimbă cu bile j din urna i)

 

n(1)→(0)

1(2)↔2(1)

1(3)↔3(1)

1(4) ↔4(1)

……………..

1(n-1) ↔n-1(1)

1(n)→(1)

Toate bilele cu numărul 1 sunt în urna 1. S-au efectuat 2(n-1) mutări

De aici încolo bila n din fiecare urnă va fi mutată (când este cazul) în urna n.

n(2)→(n)

2(3) ↔3(2)

2(4) ↔4(2)

…………..

2(n-1) ↔n-1(2)

2(n)→(2)

Acum toate bilele cu numărul 2 se află în urna 2. S-au efectuat la cest pas 2(n-2) mutări

Presupunem că am adus toate bilele cu numărul i în urna i.

Ducem bila n  din urna i+1 în urna n.

Interschimbăm bilele i+2, i+3,…..,n-1 din urna i+1 cu bilele cu numărul i+1 din urnele i+2,…,n-1.

Aducem și bila i+1 din urna n în urna i+1 și acum toate bilele cu numărul i+1 se află în urna i+1.

Ultimele mutări sunt:

n(n-1) ↔n-1(n) (2 mutări)

n(0)→n (o mutare)

În total sunt 2(n-1)+2(n-2)+….+2∙1+1=n(n-1)+1 mutări.