colors

Colors

== include(page="template/taskheader" task_id="colors") ==

!{float:right; margin-right:250px}problema/colors?graph2.png!

Mara a primit in dar un nou set de acuarele. Spre surprinderea ei, a observat că, atunci când se combină culorile G şi V se obţine un rezultat neobişnuit. A încercat toate combinaţiile posibile şi a observat că:

* dacă toarnă V peste V obţine G;
* dacă toarnă G peste G obţine V;
* dacă toarnă G peste V obţine V;
* dacă toarnă V peste G obţine G.

Curioasă, Mara, făcut următorul experiment: a pus în n cutii alăturate, la întâmplare, doar culorile V şi G şi a început să le amestece. Ca să nu se murdărească, varsă întotdeauna o cutie peste cea mai apropiată cutie care nu este goala, aflată în stânga ei. Experimentul se încheie atunci când toată vopseaua s-a adunat în prima cutie din stânga. Fiecare modalitate de a aduna toată vopseaua în prima cutie din stânga poate fi caracterizată de n-1 operaţii de forma [i,j], cu 1≤i≤j≤n, cu semnificaţia: cutia j a fost turnată în cutia i. Două modalităţi sunt considerate identice dacă folosesc aceleaşi operaţii chiar dacă acestea nu au fost efectuate în aceeaşi ordine.
De exemplu, dacă în 4 cutii avem culorile: VVGV, şirul operaţiilor [1,2][3,4][1,3] indică succesiunea operaţiilor: toarnă cutia 2 peste cutia 1 (cutia 2 devine goală), apoi cutia 4 peste cutia 3 (cutia 4 devine goală) şi la final cutia 3 peste cutia 1. Această modalitate este identică cu cea definită de şirul operaţiilor [3,4][1,2][1,3]. .

# [1,2][1,3][1,4] pentru $VVGV → G-GV → V--V → G---$
# [1,2][3,4][1,3] pentru $VVGV → G-GV → G-G- → V---$
# [2,3][1,2][1,4] pentru $VVGV → VV-V →G--V → G---$

# [2,3][2,4][1,4] pentru $VVGV → VV-V → VG-- → V---$

# [2,3][2,4][1,2] pentru $VVGV → VV-V → VG-- → V---$

# [3,4][1,2][1,3] pentru $VVGV → VVG- → G-G- → V---$
# [3,4][2,3][1,2] pentru $VVGV → VVG- → VV-- → G---$