(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)

(toc){width: 30em}*{text-align:center} *Conţinut*

(toc){width: 33em}*{text-align:center} *Conţinut*

* 'Problema 1 (Olimpiada de Informatică, Bucureşti, 1995)':probleme-de-acoperire-1#problema1
* 'Problema 2 (Lot 2001)':probleme-de-acoperire-1#problema2
* 'Problema 3 (Concursul Naţional de Informatică Lugoj, 1998)':probleme-de-acoperire-1#problema3

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

Acum se vede clar 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.

h2(#problema2). Problema 2 (Lot 2001)

Î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.

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-1?P22.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.

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-1?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]':probleme-de-acoperire-1#bibliografie secţiunea $1.1 Invariant$, sau în '[2]':probleme-de-acoperire-1#bibliografie secţiunea $Probleme de colorare şi acoperire$.

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]':probleme-de-acoperire-1#bibliografie secţiunea $1.1 Invariant$, sau în '[2]':probleme-de-acoperire-1#bibliografie 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.

h2(#problema5). 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-1?P51.jpg!

p=. !probleme-de-acoperire-1?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]':probleme-de-acoperire-1#bibliografie 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 <tex> X^{2} - 4X + 1 = 0 </tex>, iar de aici obţinem că <tex> A[2n] = \frac{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 liniară 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]':probleme-de-acoperire-1#bibliografie 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 <tex> X^{2} - 4X + 1 = 0 </tex>, 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:

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

<tex>
\emph{}