Soluții corecte: Jean-Henry Berevoescu, Nicu Scutaru, Vasile Trofin, Zoltan Szabo, Aurel Ionescu, Ionel-Vasile Pit-Rada.
Jean-Henry Berevoescu:
Nota referitor la valoarea patratelo negre ("0").
Am verificat toate combinatiile posibile pe o linie (pe o coloana este similar), pentru N luind valor diferite (3, 4, 5,... 7,... 9 etc). Si am observat ca daca urmarim miscarile pe o singura dimensiune (2x2 este in doua dimensiuni, pe linie va fi 1x2 [o linie X doua coloane] si pe coloana 2x1 [doua linii X o coloana]) si consideram ca initial, un patrat alb care trebuie transformat in negru are valoarea “1”, totdeauna se poate transforma o linie in negru numai pentru liniile care au initial suma o valoare para. Toate liniile care au o valoare totala a sumei impara, nu pot fi transformate prin miscari succesibe in negru complet.
Similar pentru coloane.
Nota: in calculul initial, patratele negre au valoarea “0”.
Deci conditia de rezolvare pentru un patrat NxN este sa aiba sume pare pentru toate liniile si toate coloanele.
Notam: TN tabloul initial si un subtablou este S2(x, y), cu (x, y) coordonata din TN unde cade (0, 0) a subtabloului.
Un algoritm de rezolvare va fi urmatorul:
· pornind din coltul stinga sus ((0, 0)) si fiecare miscare spre stinga avanseaza cu un patrat, pina la capat: de la S2(0, 0) la S2(0, N – 1).
o daca S2(x, y) este alb, facem tranzitia (toate celulele lui S2 se inverseaza)
o daca S2(x, y) este negru, nu facem tranzitia si trecem mai departe
· cind ajungem la capatul liniei, trecem la linia urmatoare: de la S2(0, N - 1) la S2(1, 0) si repetam bucla precedenta.
Daca TN a respectat conditiile de mai sus (sumele pe linie si coloana sint pare), TN va ajunge sa aiba toate patratele negre.
Zoltan Szabo:
Asociem valoarea 0 pentru culoarea neagră și valoarea 1 pentru culoarea albă.
Este adevărat că pornind de la o configurație și realizarea configurației “negru complet” este o activitate echivalentă cu pornirea de la “negru complet” și realizarea configurației date.
Deci este mai ușor să studiem problema inversă.
Observăm, că suma tuturor elementelor de pe oricare linie și oricare coloană în configurația “negru complet” este 0. Adică un număr par.
Pentru o configurație oarecare, în care toate liniile și toate coloanele au sumă pară, prin plasarea unui pătrat 2*2 peste o zonă a tabloului, va schimba exact patru elemente învecinate două câte două.
Observăm că sumele parțiale se vor transforma astfel
0+0=0 în 1+1=2
0+1=1 în 1+0=1
1+0=1 în 0+1=1
1+1=2 în 0+0=0
Adică nu se va schimba paritatea elementelor de pe nicio linie și nicio coloană. Știind că configurație “negru complet” are sume pare pe orice linie și coloană, rezultă că orice plasare de pătrat 2*2 va păstra paritatea tuturor liniilor și coloanelor.
Deci soluția problemei este următoarea:
Considerând că negru este 0 și alb este 1, problema va avea soluție atunci și numai atunci, dacă fiecare linie și fiecare coloană a tabloului are suma elementelor un număr par.
Aurel Ionescu:
Pentru a fi posibil trebuie ca numarul patratelor albe de pe fiecare linie sa fie par. Astfel daca aplicam o functie care inverseaza culorile, cu un tablou 2x2, numai atunci cand patratul din primul colt este alb si mutam aceasta functie spre stanga, pana la capatul liniei, obtinem numai patrate negre (pentru ca daca este indeplinita conditia de paritate ajungem sa avem la sfarsit ori doua casute albe care se vor transforma in negre, ori vom avea doua patrate negre care nu mai trebuiesc modificate).
Analog gandim si pentru coloane, si daca numarul patratelor albe de pe fiecare coloana este par, vom ajunge pe ultimele doua randuri cu un numar par de patratele albe.