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.

h2(#prob8). Problema 8 ( _Lot matematică 2001,_ "_Floor tiles_":http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1585 )

h2(#prob8). Problema 8 ( _Lot matematică 2001, acm.uva.es - 10644 Floor tiles_ )

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?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$).

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

h2(#concl). Concluzii

Acest articol a pus accentul mai mult asupra gândirii matematice în problemele de acoperire. În articolul următor încercăm o abordare orientată spre algoritmică.

Acest articol a pus accentul mai mult asupra gândirii matematice în problemele de acoperire. În articolul următor vom încerca o abordare orientată spre algoritmică.

h2(#biblio). Bibliografie