h3. Soluţie:

Prima întrebare care ne vine în minte este dacă aria ce trebuie acoperită este divizibilă cu $3$. Aria este $4^n^ – 1 = (4 – 1)(4^n-1^ + 4^n-2^ + … + 4 + 1)$, deci este multiplu de trei. Să trecem acum la ideea rezolvării.
Împărţim pătratul în patru pătrate de dimensiuni egale. Unul dintre ele are un pătrat lipsă, facem ca celelalte trei pătrate să aibă şi ele un pătrat lipsă prin plasarea unei piese care sa acopere câte un colţ al fiecăruia dintre cele trei pătrate rămase dupa cum observăm în figură.

* Prima întrebare care ne vine în minte este dacă aria ce trebuie acoperită este divizibilă cu $3$. Aria este $4^n^ – 1 = (4 – 1)(4^n-1^ + 4^n-2^ + … + 4 + 1)$, deci este multiplu de trei. Să trecem acum la ideea rezolvării.
* Împărţim pătratul în patru pătrate de dimensiuni egale. Unul dintre ele are un pătrat lipsă, facem ca celelalte trei pătrate să aibă şi ele un pătrat lipsă prin plasarea unei piese care sa acopere câte un colţ al fiecăruia dintre cele trei pătrate rămase dupa cum observăm în figură.

p=. !probleme-de-acoperire?OlimpBuc2.jpg!

Astfel am redus problema la patru noi probleme de dimensiuni mai mici.

* Astfel am redus problema la patru noi probleme de dimensiuni mai mici.

p=. !probleme-de-acoperire?OlimpBuc3.jpg!

Se vede clar acum, cum prin metoda $divide et impera$ putem să acoperim întreg pătratul cu piesele cerute.

* Se vede clar acum, cum prin metoda $divide et impera$ putem să acoperim întreg pătratul cu piesele cerute.

h3. *Problema 2* (lot 2001 şi [1])

h3. Soluţie:

Să vedem întâi cum rezolvăm cazul minim în care $N = 1$.

* Să vedem întâi cum rezolvăm cazul minim în care $N = 1$.

p=. !probleme-de-acoperire?P21.JPG!

În aceste trei figuri am epuizat toate cazurile pentru table de dimensiune $7$ unde lipseşte un pătrat. În fiecare desen am lăsat un pătrat de latură doi liber pentru a trata astfel cele patru cazuri în care pătrăţelul lipsă ar face parte din acest pătrat. Recurgând şi la rotaţiile acestor soluţii acoperim toate cazurile posibile pentru pătrăţelul lipsă. Menţionăm că cele trei soluţii au fost găsite cu uşurinţă de mână de autor.
Să presupunem că ştim cum să acoperim un pătrat de latură $6N + 1$. Să vedem acum cum acoperim un pătrat de latură $6N + 7$. În acest nou pătrat putem plasa într-un colţ de al lui un pătrat de latură $6N + 1$, care are un pătrăţel lipsă. Pătratul acesta îl ştim acoperi şi după cum arată şi figura următoare ne mai rămâne să acoperim două dreptunghiuri de dimensiuni $6 x 6n$, respectiv $6n x 6$ şi un pătrat de latură $7$ cu patrăţelul din colţ lipsă. Dreptunghiurile le putem acoperi cu dreptunghiuri de dimensiuni $2 x 3$ formate din câte două piese, iar pătratul de $7 x 7$ cu un colţ lipsă este un caz pentru $N = 1$ al problemei noastre.

* În aceste trei figuri am epuizat toate cazurile pentru table de dimensiune $7$ unde lipseşte un pătrat. În fiecare desen am lăsat un pătrat de latură doi liber pentru a trata astfel cele patru cazuri în care pătrăţelul lipsă ar face parte din acest pătrat. Recurgând şi la rotaţiile acestor soluţii acoperim toate cazurile posibile pentru pătrăţelul lipsă. Menţionăm că cele trei soluţii au fost găsite cu uşurinţă de mână de autor.
* Să presupunem că ştim cum să acoperim un pătrat de latură $6N + 1$. Să vedem acum cum acoperim un pătrat de latură $6N + 7$. În acest nou pătrat putem plasa într-un colţ de al lui un pătrat de latură $6N + 1$, care are un pătrăţel lipsă. Pătratul acesta îl ştim acoperi şi după cum arată şi figura următoare ne mai rămâne să acoperim două dreptunghiuri de dimensiuni $6 x 6n$, respectiv $6n x 6$ şi un pătrat de latură $7$ cu patrăţelul din colţ lipsă. Dreptunghiurile le putem acoperi cu dreptunghiuri de dimensiuni $2 x 3$ formate din câte două piese, iar pătratul de $7 x 7$ cu un colţ lipsă este un caz pentru $N = 1$ al problemei noastre.

p=. !probleme-de-acoperire?P22.jpg!

h3. Soluţie:

Observăm că fiecare piesă este formată din patru pătrăţele. De aici deducem că $N^2^$ este multiplu de $4$ deci $N$ e multiplu de $2$. Pentru $N = 6$ avem următoarea soluţie:

* Observăm că fiecare piesă este formată din patru pătrăţele. De aici deducem că $N^2^$ este multiplu de $4$ deci $N$ e multiplu de $2$. Pentru $N = 6$ avem următoarea soluţie:

p=. !probleme-de-acoperire?P32.jpg!

Pentru $N > 6$ putem împărţi pătratul într-un pătrat de latură $6$ şi două dreptunghiuri de dimensiuni $6 x (N – 6)$ şi $(N – 6) x N$, după cum observăm în figura următoare. Dreptunghiurile pot fi acoperite cu piese de tip $3$.

* Pentru $N > 6$ putem împărţi pătratul într-un pătrat de latură $6$ şi două dreptunghiuri de dimensiuni $6 x (N – 6)$ şi $(N – 6) x N$, după cum observăm în figura următoare. Dreptunghiurile pot fi acoperite cu piese de tip $3$.

p=. !probleme-de-acoperire?P33.jpg!

h3. Soluţie:

Prima observaţie pe care o facem este aceea că $N$ trebuie să fie par pentru ca tabla să poată fi acoperită. Este evident pentru cazurile $N = 2$ sau $N = 4$ că problema nu are soluţie, dar pentru cazuri mai mari demonstraţia faptului că există sau nu există soluţie pare dificilă, şi valorile lui $N$ pentru care o abordare exhaustivă a posibilităţilor de  acoperire a tablei cu dominouri ar fi eficientă sunt destul de mici.
O idee interesantă este aceea de a colora pătratele tablei în acelaşi mod în care se colorează o tablă de şah, aşa cum vedem în figura următoare.

* Prima observaţie pe care o facem este aceea că $N$ trebuie să fie par pentru ca tabla să poată fi acoperită. Este evident pentru cazurile $N = 2$ sau $N = 4$ că problema nu are soluţie, dar pentru cazuri mai mari demonstraţia faptului că există sau nu există soluţie pare dificilă, şi valorile lui $N$ pentru care o abordare exhaustivă a posibilităţilor de  acoperire a tablei cu dominouri ar fi eficientă sunt destul de mici.
* O idee interesantă este aceea de a colora pătratele tablei în acelaşi mod în care se colorează o tablă de şah, aşa cum vedem în figura următoare.

p=. !probleme-de-acoperire?P41.jpg!

Orice domino amplasat pe tablă va acoperi două pătrăţele de culori diferite, deci tabla trebuie să aibă un număr egal de pătrăţele colorate alb şi negru, fapt care nu se întâmplă în problema noastră. De aici deducem că nu putem acoperi tabla din care au fost eliminate două colţuri opuse. O problemă ce se poate aborda cu o tehnică asemănătoare este următoarea: „Se dă un dreptunghi de dimensiuni $7 x 10$. Din colţurile lui scoatem câte un pătrat de latură $1$. Să se arate că figura rămasă nu poate fi pardosită cu dreptunghiuri de laturi $3$ şi $1$. Pentru probleme de acelaşi gen şi soluţia la această problemă puteţi să consultaţi în [1] secţiunea 1.1 $Invariant$, sau în [2] secţiunea $Probleme de colorare şi acoperire$. Problema în care eliminăm două pătrate de aceiaşi culoare sau chiar cazul generalizat în care eliminăm un număr mai mare de pătrăţele o vom discuta în numărul viitor.

* Orice domino amplasat pe tablă va acoperi două pătrăţele de culori diferite, deci tabla trebuie să aibă un număr egal de pătrăţele colorate alb şi negru, fapt care nu se întâmplă în problema noastră. De aici deducem că nu putem acoperi tabla din care au fost eliminate două colţuri opuse. O problemă ce se poate aborda cu o tehnică asemănătoare este următoarea: „Se dă un dreptunghi de dimensiuni $7 x 10$. Din colţurile lui scoatem câte un pătrat de latură $1$. Să se arate că figura rămasă nu poate fi pardosită cu dreptunghiuri de laturi $3$ şi $1$. Pentru probleme de acelaşi gen şi soluţia la această problemă puteţi să consultaţi în [1] secţiunea 1.1 $Invariant$, sau în [2] secţiunea $Probleme de colorare şi acoperire$. Problema în care eliminăm două pătrate de aceiaşi culoare sau chiar cazul generalizat în care eliminăm un număr mai mare de pătrăţele o vom discuta în numărul viitor.

h3. *Problema 5*

h3. Soluţie:

Pentru $N = 1$ avem o posibilitate, pentru $N = 2$ avem două posibilităţi, iar în cazul general daca notăm cu <tex> $F[n]$ </tex> numărul de posibilităţi avem, aşa cum putem observa şi din figură, <tex> $F[n] = F[n – 1] + F[n – 2]$ </tex>, deci exact şirul lui Fibonacci.

* Pentru $N = 1$ avem o posibilitate, pentru $N = 2$ avem două posibilităţi, iar în cazul general daca notăm cu <tex> $F[n]$ </tex> numărul de posibilităţi avem, aşa cum putem observa şi din figură, <tex> $F[n] = F[n – 1] + F[n – 2]$ </tex>, deci exact şirul lui Fibonacci.

p=. !probleme-de-acoperire?P51.jpg!

h3. Soluţie:

Şi în această problemă $N$ trebuie să fie par pentru ca tabla să poată fi acoperită. Avem următoarele posibilităţi la început:

* Şi în această problemă $N$ trebuie să fie par pentru ca tabla să poată fi acoperită. Avem următoarele posibilităţi la început:

p=. !probleme-de-acoperire?P61.jpg!

Observăm că în ultimele două cazuri pătrăţelul rămas gol poate fi acoperit într-un singur mod de un nou domino, aşa cum ne arată dominoul haşurat. Numim $A[n]$ numărul de moduri în care poate fi acoperit un dreptunghi de dimensiune $3 x n$ de dominouri, şi $B[n]$ numărul de moduri în care putem acoperi un dreptunghi de $3 x n$ dominouri la care se mai lipeşte pe margine un domino vertical aşa cum vedem în figura următoare.

* Observăm că în ultimele două cazuri pătrăţelul rămas gol poate fi acoperit într-un singur mod de un nou domino, aşa cum ne arată dominoul haşurat. Numim $A[n]$ numărul de moduri în care poate fi acoperit un dreptunghi de dimensiune $3 x n$ de dominouri, şi $B[n]$ numărul de moduri în care putem acoperi un dreptunghi de $3 x n$ dominouri la care se mai lipeşte pe margine un domino vertical aşa cum vedem în figura următoare.

p=. !probleme-de-acoperire?P62.jpg!

Putem observa uşor că <tex> $A[2n + 2] = 3A[2n] + 2B[2n – 2]$ </tex>, iar <tex> $B[2n] = A[2n] + B[2n – 2]$ </tex>. Aceste două recurenţe ar fi fost de ajuns pentru a rezolva problema în concurs. În cartea [3] rezolvarea continuă pentru a determina un număr explicit: <tex> $A[2n + 2] = 3 A[2n] + 2A[2n – 2] + 2B[2n – 4]$ </tex> (am înlocuit pe <tex> $B[2n – 2]$ </tex>). Mai departe obţinem <tex> $A[2n + 2] = 4 A[2n] – A[2n – 2]$ </tex>. Putem uşor afla că <tex> $A[2] = 3$ </tex> şi <tex> $A[4] = 11$ </tex>. Ecuaţia caracteristică a ecuaţiei liniare este $x^2^ – 4x + 1 = 0$, iar de aici obţinem că <tex> $A[2n] = 1/{2\sqrt{3}} * ((\sqrt{3} + 1) * (2 + \sqrt{3}){^n^} + (\sqrt{3} - 1) * (2 - \sqrt{3}){^n^})$ </tex>. (metoda rezolvării recurenţelor liniare este prezentată în manualul de clasa a 11-a de matematică). Un astfel de răspuns nu ne prea ajută pe noi ca programatori pentru că ar trebui să putem efectua operaţii cu numere reale cu o precizie destul de mare pentru a ajunge la rezultatul dorit. Totuşi, faptul că am găsit o recurenţa lineară ne ajută să determinăm mult mai repede numărul de posibilităţi folosindu-ne de următorul raţionament:

* Putem observa uşor că <tex> $A[2n + 2] = 3A[2n] + 2B[2n – 2]$ </tex>, iar <tex> $B[2n] = A[2n] + B[2n – 2]$ </tex>. Aceste două recurenţe ar fi fost de ajuns pentru a rezolva problema în concurs. În cartea [3] rezolvarea continuă pentru a determina un număr explicit: <tex> $A[2n + 2] = 3 A[2n] + 2A[2n – 2] + 2B[2n – 4]$ </tex> (am înlocuit pe <tex> $B[2n – 2]$ </tex>). Mai departe obţinem <tex> $A[2n + 2] = 4 A[2n] – A[2n – 2]$ </tex>. Putem uşor afla că <tex> $A[2] = 3$ </tex> şi <tex> $A[4] = 11$ </tex>. Ecuaţia caracteristică a ecuaţiei liniare este $x^2^ – 4x + 1 = 0$, iar de aici obţinem că <tex> $A[2n] = 1/{2\sqrt{3}} * ((\sqrt{3} + 1) * (2 + \sqrt{3}){^n^} + (\sqrt{3} - 1) * (2 - \sqrt{3}){^n^})$ </tex>. (metoda rezolvării recurenţelor liniare este prezentată în manualul de clasa a 11-a de matematică). Un astfel de răspuns nu ne prea ajută pe noi ca programatori pentru că ar trebui să putem efectua operaţii cu numere reale cu o precizie destul de mare pentru a ajunge la rezultatul dorit. Totuşi, faptul că am găsit o recurenţa lineară ne ajută să determinăm mult mai repede numărul de posibilităţi folosindu-ne de următorul raţionament:

Dacă avem o recurenţa <tex> $X[n] = aX[n-1] + bX[n-2]$ </tex> atunci avem că:

* Dacă avem o recurenţa <tex> $X[n] = aX[n-1] + bX[n-2]$ </tex> atunci avem că:

<tex>
\emph{}

X[n] \\
X[n - 1] \end{array} \right)\]  </tex>

Iar cum o matrice o putem ridica la o putere în număr logaritmic de paşi, putem afla <tex> $X[n]$ </tex> mult mai repede.

* Iar cum o matrice o putem ridica la o putere în număr logaritmic de paşi, putem afla <tex> $X[n]$ </tex> mult mai repede.

h3. *Problema 7* (ACM ICPC 1997)

h3. Soluţie:

Poate părea surprinzător, dar pentru această problemă, deşi pare foarte grea, există o formulă:
 
<tex> ${2}^{\frac{M*N}{2}} * {(\cos^{2}\frac{m*pi}{M+1} + cos^{2}\frac{n*pi}{N+1})}^{\frac{1}{4}}$ </tex>
 
pentru $0 < m < M+1, 0 < n < N+1$. Şi mai surprinzător este că această expresie ce conţine numere iraţionale are ca rezultat un număr întreg. Pentru o demonstraţie a acestei formule puteţi să intraţi pe adresa [4]. Ar fi anormal ca să ştim o asemenea formulă pe de rost în speranţa că vom primi problema la vreun concurs. Dimensiunile mici ale problemei o făceau abordabilă printr-un algoritm ce combină $programarea dinamică$ cu $backtrackingul$ pe care îl vom prezenta în numărul următor.

* Poate părea surprinzător, dar pentru această problemă, deşi pare foarte grea, există o formulă: <tex> ${2}^{\frac{M*N}{2}} * {(\cos^{2}\frac{m*pi}{M+1} + cos^{2}\frac{n*pi}{N+1})}^{\frac{1}{4}}$ </tex> pentru $0 < m < M+1, 0 < n < N+1$. Şi mai surprinzător este că această expresie ce conţine numere iraţionale are ca rezultat un număr întreg. Pentru o demonstraţie a acestei formule puteţi să intraţi pe adresa [4]. Ar fi anormal ca să ştim o asemenea formulă pe de rost în speranţa că vom primi problema la vreun concurs. Dimensiunile mici ale problemei o făceau abordabilă printr-un algoritm ce combină $programarea dinamică$ cu $backtrackingul$ pe care îl vom prezenta în numărul următor.

h3. *Problema 8* (Lot matematică, 2001 şi acm.uva.es, 10644 Floor tiles)