<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)
 
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!
 
h3. Soluţie:
 
Să începem cu dimensiuni mici.
 
* Tablele de $2 x n$ le putem acoperi doar dacă $n$ este multiplu de $3$, pentru că aria dreptunghiului trebuie să fie multiplu de $3$.
* Tablele de $3 x n$ le putem acoperi doar dacă $n$ este par, pentru că suntem obligaţi să acoperim dreptunghiul cu dreptunghiuri verticale de dimensiuni $2 x 3$.
* Tablele de $4 x n$ le putem acoperi doar dacă $n$ este multiplu de $3$, şi putem face acest lucru folosind dreptunghiuri de $2 x 3$.
* 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!
 
* 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!
 
* 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$.