(Categoria _Algoritmi_, autor _Cosmin Negruşeri_)

(toc){width: 33em}*{text-align:left} *Cuprins:*
* 'Problema 1 ( _Olimpiada de informatică, Bucureşti, etapa pe sector, 1995,_ [1] )':probleme-de-acoperire#prob1
* 'Problema 2 ( _Lot 2001,_ [1] )':probleme-de-acoperire#prob2
* 'Problema 3 ( _Concursul naţional de informatică Lugoj, 1998_ )':probleme-de-acoperire#prob3
* 'Problema 4':probleme-de-acoperire#prob4
* 'Problema 5':probleme-de-acoperire#prob5
* 'Problema 6 ( _ONI 2001, clasa a X-a,_ [3] )':probleme-de-acoperire#prob6
* 'Problema 7 ( _ACM ICPC 1997_ )':probleme-de-acoperire#prob7
* 'Problema 8 ( _Lot matematică 2001, acm.uva.es - 10644 Floor tiles_ )':probleme-de-acoperire#prob8
* 'Problema 9':probleme-de-acoperire#prob9
* 'Concluzii':probleme-de-acoperire#concl
* 'Bibliografie':probleme-de-acoperire#biblio
 

În acest prim articol vom prezenta o serie de probleme apărute la concursurile de programare care au o tematică similară şi anume aceea de acoperire în plan. În general acest tip de probleme sunt $NP complete$, dar pentru cazurile particulare prezentate problemele sunt rezolvabile. Cea de a doua parte a articolului o puteţi găsi "aici":probleme-de-acoperire2.

h2. Problema 1 (Olimpiada de informatică, Bucureşti, etapa pe sector, 1995 şi [1])

h2(#prob1). Problema 1 ( _Olimpiada de informatică, Bucureşti, etapa pe sector, 1995,_ [1] )

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:

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

h2. Problema 2 (lot 2001 şi [1])

h2(#prob2). Problema 2 ( _Lot 2001,_ [1] )

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

h2. Problema 3 (Concursul naţional de informatică Lugoj, 1998)

h2(#prob3). 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?P33.jpg!

h2. Problema 4

h2(#prob4). Problema 4

bq. Să se determine dacă putem acoperi o tablă de dimensiune $N x N$ cu dominouri după ce îi eliminăm două colţuri opuse.

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.

h2. Problema 5

h2(#prob5). Problema 5

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $2 x N$ cu dominouri.

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

h2. Problema 6 (ONI 2001, clasa a X-a şi [3])

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

bq. Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $3 x N$ cu dominouri.

Iar cum o matrice o putem ridica la o putere în număr logaritmic de paşi, putem afla <tex> X[n] </tex> mult mai repede.

h2. Problema 7 (ACM ICPC 1997)

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

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. Problema 8 (Lot matematică, 2001 şi acm.uva.es, 10644 Floor tiles)

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:

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

h2. Problema 9

h2(#prob9). Problema 9

bq. Pentru un dreptunghi de dimensiuni $N x M$ să se determine o acoperire cu dominouri a lui astfel încât să nu existe vreo linie verticală sau orizontală care să taie dreptunghiul în două fără să intersecteze vreun domino.

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

h2. Concluzii

h2(#concl). Concluzii

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

h2(#biblio). Bibliografie

* [1] Mircea Ganga, Teme şi probleme de matematică, ed.tehnică, Bucuresti, 1991
* [2] Valentin Vornicu, Olimpiada de matematică de la provocare la experienţa, ed. Gil, 2003