bq. Se dă un pătrat de latură $2^n^$ care se împarte în pătrate disjuncte de latură $1$. Unul dintre aceste pătrate se elimină. Se cere acoperirea suprafeţei rămase cu piese de forma:

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

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

h3. Soluţie:

Împărţim pătratul în $4$ 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 să acopere câte un colţ al fiecăruia dintre cele trei pătrate rămase, după cum observăm în figură.

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

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

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

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

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

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

bq. Se dă un pătrat de latură $6N + 1$ care se împarte în pătrate disjuncte de latură $1$. Unul dintre aceste pătrate se elimină. Se cere acoperirea suprafeţei rămase cu piese de forma:

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

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

h3. Soluţie:
Să vedem întâi cum rezolvăm cazul minim în care $N = 1$.

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

p=. !probleme-de-acoperire-1?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.

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

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

h2(#prob1ema3). Problema 3 ( _Concursul naţional de informatică Lugoj, 1998_ )
bq. Să se acopere complet un pătrat de latură $N >= 6$ cu următoarele piese, astfel ca fiecare piesă să fie folosită cel puţin o dată.

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

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

h3. Soluţie:
Observăm că fiecare piesă este formată din $4$ 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!

p=. !probleme-de-acoperire-1?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$.

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

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

h2(#prob1ema4). Problema 4

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!

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

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!

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

h2(#prob1ema6). Problema 6 ( _ONI 2001, clasa a X-a,_ [3] )

Ş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!

p=. !probleme-de-acoperire-1?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 <tex> A[n] </tex> numărul de moduri în care poate fi acoperit un dreptunghi de dimensiune $3 x n$ de dominouri, şi <tex> B[n] </tex> 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!

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] 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:

bq. Se dă un dreptunghi de dimensiuni $M x N$, să se determine dacă el se poate acoperi cu piese de forma:

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

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

h3. Soluţie:

* Tabla de $5 x 3$ nu poate fi acoperită după cum am văzut la tablele de $3 x n$.
* Tabla de $5 x 6$ poate fi acoperită cu dreptunghiuri de $2 x 3$ aşa cum vedem în figură.

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

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

* Pentru tabla de $5 x 9$ este uşor să determinăm o acoperire de mână, una găsită de autor apare în figură. Menţionăm că tabla de $5 x 9$ este cea mai mică tablă de dimensiuni impare pe care o putem acoperi complet. Putem acoperi table de dimensiuni $5 x n$ cand $n$ e multiplu de $3$ şi e diferit de $3$ ({$n = 9 + 6k$} sau $n = 6 + 6k$ unde $k >= 0$ deci adăugăm la o soluţie de $5 x (n – 6)$ un dreptunghi de dimensiuni $5 x 6$).

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

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

* Pentru cazul general $M x N$, presupunem fără a reduce generalizarea că $N$ e multiplu de $3$. Pentru $M <= 5$ problema e deja rezolvată. Să vedem acum rezolvarea pentru $M > 5$: dacă $M$ e par atunci putem obţine uşor o soluţie folosind dreptunghiuri de dimensiune $2 x 3$, iar dacă $M$ e impar atunci obţinem întâi o soluţie pentru $(M – 2) x N$ la care adăugăm o bandă de dimensiune $2 x N$ formată din dreptunghiuri $2 x 3$.

În figura următoare avem o soluţie greşită:

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

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

Este evident că pentru dreptunghiuri de dimensiuni $2 x N$, $3 x N$ şi $4 x N$ nu există soluţie. Pentru $5 x 6$ şi $6 x 8$ este foarte uşor să găsim o soluţie de mână; avem o solutie pentru $5 x 6$ în următoarea figură. Pentru $6 x 6$ nu există soluţie. Pentru aceasta putem folosi o demonstraţie matematică care se găseşte în [6] sau putem folosi un algoritm de tip backtracking pentru a ne asigura că nu există vreo soluţie.

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

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

Un dreptunghi de dimensiune $N x M$ îl putem mări la unul de dimensiune $(N + 2) x M$ folosind procedeul prezentat în ultima figură.

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

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

h2(#concluzii). Concluzii