h2(#problema3). 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ă.

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-1?P31doi.jpg!

h2(#problema7). Problema 7 (ACM ICPC 1997)

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $N x M (N <= 20, M <= 20)$ cu dominouri.

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $N x M (N ≤ 20, M ≤ 20)$ cu dominouri.

h3. Soluţie:

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

* 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-1?P82.jpg!

* Pentru cazul general $M x N$, presupunem fără a reduce generalitatea 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 &#120; 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 &#120; 3$.

* Pentru cazul general $M x N$, presupunem fără a reduce generalitatea 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$.

h2(#problema9). Problema 9