Rezolvare:
Soluţia 1 (Vasile Vilvoiu):
Pentru o secventa x = (x1, x2, x3), o pozitie a lacatului, putem identifica doua tipuri de transformari:
· T, adica T(x) = ((x1+1) mod 3, (x2+1) mod 3, x3)
· U, adica U(x) = (x1, (x2+1) mod 3, (x3+1) mod 3)
unde "mod" este operatorul modulo.
Observam ca:
· T(U(x)) = U(T(x)) = ((x1+1) mod 3, (x2+2) mod 3, (x3+1) mod 3)
· T(T(T(x))) = x, respectiv U(U(U(x))) = x
· T(x) <> U(x) <> x
Vom nota transformari compuse precum T(U(x)) ca (T+U)(x) si transformari compuse precum T(T(x)) ca (2T)(x)
Astfel putem identifica multimea secventelor la care putem ajunge pornind de la x:
· x
· T(x)
· U(x)
· (2T)(x)
· (2U)(x)
· (T+U)(x)
· (T+2U)(x)
· (2T+U)(x)
· (2T+2U)(x)
Cum aplicarea altor transformari pe oricare din secventele de mai sus vor duce (prin compunere sau simplificare) la secvente din aceeasi multime, putem concluziona ca exista familii de 9 secvente intre care se poate ajunge folosind T si U.
Cum domeniul secventelor este de 33, avem 3 astfel de familii. Se pune problema daca (3,3,3) si (2,2,1) se afla in aceiasi familie.
Prima solutie ar fi sa consideram secventele din familie ca noduri ale unui graf, in care muchiile sunt transformarile T si U. Avand in vedere ca vom avea doar 9 noduri, putem folosi Lee pentru a ajunge, in cateva minute, la solutie.
Pentru a doua solutie vom considera:
· x = (x1, x2, x3)
· y = (y1, y2, y3)
· Q transformare compusa din una sau mai multe transformari T si U, astfel incat Q(x)=y
Q(x) = (aT)(x) + (bU)(x) = ((x1+a) mod 3, (x2 + a + b) mod 3, (x3 + b) mod 3) = (y1, y2, y3)
Din enunt preluam constrangerile:
· x1=x2 (1)
· y1=y2 (2)
· x3<>y3 (3)
Din (1) si (2) obtinem:
Q(x) = ((x1+a) mod 3, (x1+a+b) mod 3, (x3+b) mod 3) = (y1, y1, y3)
=> (x1+a) mod 3 = (x1+a+b) mod 3 => b mod 3 = 0
Din (3) obtinem:
(x3+b) mod 3 <> x3 => b mod 3 <> 0
Concluzionam ca nu exista un astfel de Q, deci nu se poate ajunge de la (3, 3, 3) la (2, 2, 1).
Soluţia 2 (Ady Nicolae):
Plecând de la varianta inițială 3-3-3 avem două opțiuni, să învârtim primele 2 rotițe (1-1-3) sau ultimele 2 rotițe (3-1-1).
Varianta 1-1-3 se poate transforma în 2-2-3 sau 1-2-1.
Varianta 3-1-1 se poate transforma în 1-2-1 sau 3-2-2.
Varianta 2-2-3 se transformă în 3-3-3 (varianta inițială) sau 2-3-1.
Varianta 1-2-1 se transformă în 2-3-1 sau 1-3-2.
Varianta 3-2-2 se transformă în 1-3-2 sau 3-3-3 (varianta inițială).
Ne rămân doar două variante: 2-3-1 şi 1-3-2.
Varianta 2-3-1 se transformă în 3-1-1 sau 2-1-2.
Varianta 1-3-2 se transformă în 2-1-2 sau 1-1-3.
Ne rămâne o singură variantă, variantele 3-1-1 şi 1-1-3 au intrat în buclă.
Varianta 2-1-2 se transformă în 3-2-2 sau 2-2-3, ambele variante apărând şi mai sus.
Deci, de la combinația 3-3-3 NU se poate ajunge la 2-2-1.
Soluţia 3 (Ştefan Muntean):
Deci ideea este că pornim de la 3-3-3 şi ajungem la 2-2-1.
Să numim rotaţie de stînga (RS) rotirea simultană a primelor două rotiţe, şi rotire de dreapta (RD) rotirea simultană a utlimelor două rotiţe.
Putem folosi o logică ce aduce a reducere la absurd. Presupunem că am reuşit trecerea de la 3-3-3 la 2-2-1.
Ne uităm la cifra din stînga: pentru a ajunge de la 3 la 2 este nevoie de două RS (sau cinci, sau opt, etc.): de la 3 la 1 apoi de la 2 la 3. Practic e nevoie de 2 + 3 * M de astfel de RS.
Ne uităm la cifra din dreapta: pentru a ajunge de la 3 la 1 este nevoie o singură RS (sau patru, sau şapte, etc.): de la 3 la 1. Practic e nevoie de 1 + 3 * N de astfel de RD.
Acum ne uităm la cifra din mijloc. Ea s-a rotit atît în cazul unei RS cît şi în cazul uei RD, deci a făcut ( 2 + 3 * M) + (1 + 3 * N) rotaţii. Asta însemană un total de 3 + 3 * M * 3 + N rotaţii, deci un multiplu de 3 (adică 3, 6, 9 etc. rotaţii). Pornind de la cifra 3, un număr de 3 rotaţii (sau 6, sau 9 etc.) ne duce tot la cifra 3 (3->1, apoi 1->2 apoi 2->3), deci nu e posibil nicicum să obţinem cifra 2 aşa cum cere problema.
Am dat peste o contradicţie, ca atare ceea ce cere problema nu este posibil.
Soluţia 4 (Szabo Zoltan):
Pentru simplitate să considerăm că în locul cifrei 3 avem cifra 0. Această problemă este echivalentă cu cea iniţială, dar ne permite folosirea împărţirii cu rest modulo 3, care are cifrele 0,1,2).
Pornind cu cifrele 0,1,2 şi combinaţia iniţială 0-0-0 (în loc de cifrele 3,1,2 şi combinaţia 3-3-3), putem vedea ce se întâmplă dacă aplicăm operaţii asupra a două rotiţe vecine.
Să codificăm mişcarea primelor două rotiţe cu S, iar mişcarea ultimelor două rotiţe cu D.
Observăm, că:
1a. aplicarea unei operaţii de tip S de x ori afectează ambele rotiţe cu x unităţi (x mod 3) şi o vom nota cu xS;
1b. aplicarea unei operaţii de tip D de y ori afectează ambele rotiţe cu y unităţi (y mod 3) şi o vom nota cu xD;
1c. (consecinţă la 1a şi 1b) dacă x mod 3 = 0, operaţia xS sau xD nu are efect (nu schimbă configuraţia)
2a. nu contează ordinea efectuării a două rotiri distincte, adică şirul de rotiri S D este identic D S;
2b. (consecinţă la 2a) rotirile alternative au efect cumulativ asupra tuturor rotiţelor asupra cărora au efect. De exemplu ţirul de rotiri S D D S S D D S S este identic cu S S S S S D D D D, pe care o putem nota cu 5S 4D
2c. (consecinţă la 2b) pentru orice şir de rotiri există câte un număr natural m şi n, pentru care şirul de rotiri să fie echivalent cu mS nD
2d. (consecinţă la 2c) pentru orice şir de rotiri există câte un număr natural m’<3 şi n’<3, pentru care şirul de rotiri să fie echivalent cu m’S n’D. (m’=m mod 3, n’=n mod 3)
3. La un şir de rotiri de tip mS nD, prima rotiţă va fi învârtită de m (mod 3) ori, a doua rotiţă de m+n (mod 3) ori, iar rotiţa a treia de n (mod 3) ori
Rezolvarea 1.
Cunoscând proprietăţile de mai sus, observăm că avem configuraţia inniţială 0-0-0 peste care trebuie să aplicăm un şir de rotiri mS nD.
Prima rotiţă va fi mişcată de m ori şi va avea valoarea (m+0) mod 3;
a doua rotiţă se va mişca de m+n ori, şi va avea valoarea (m+n+0) mod 3;
a treia rotiţă se va mişca de n ori, şi va avea valoarea (n+0) mod 3;
unde cifrele 0 sunt valorile rotiţelor din configuraţia ini