== include(page="template/implica-te/scrie-articole" user_id="marius") ==
 

h1. Probleme de acoperire (partea I)

== include(page="template/implica-te/scrie-articole" user_id="marius") ==
 

(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)
(toc){width: 30em}*{text-align:center} *Conţinut*

* 'Problema 5':probleme-de-acoperire-1#problema5
* 'Problema 6 (ONI 2001)':probleme-de-acoperire-1#problema6
* 'Problema 7 (ACM ICPC 1997)':probleme-de-acoperire-1#problema7

* 'Problema 8 (Lot matematică 2001, acm.uva.es)':probleme-de-acoperire-1#problema8

* 'Problema 8: Floor tiles (Lot matematică 2001)':probleme-de-acoperire-1#problema8

* 'Problema 9':probleme-de-acoperire-1#problema9
* 'Concluzii':probleme-de-acoperire-1#concluzii
* 'Bibliografie':probleme-de-acoperire-1#bibliografie

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:

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]':probleme-de-acoperire-1#bibliografie. 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.

Poate părea surprinzător, dar pentru această problemă, deşi pare foarte grea, există o formulă: <tex> {2}^{\frac{M*N}{2}} * \prod {(\cos^{2}\frac{m*pi}{M+1} + cos^{2}\frac{n*pi}{N+1})}^{\frac{1}{4}} </tex> pentru <tex>0 < m < M+1</tex>, <tex>0 < n < N+1</tex>. Ş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]':probleme-de-acoperire-1#bibliografie. Ar fi anormal 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 $backtracking-ul$ pe care îl vom prezenta în secţiunea următoare.

h2(#problema8). 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(#problema8). Problema 8: 'Floor tiles':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=18&page=show_problem&problem=1585 (Lot matematică 2001)

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

Să considerăm pe rând:
* 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ă.

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

* 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

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]':probleme-de-acoperire-1#bibliografie sau putem folosi un algoritm de tip backtracking pentru a ne asigura că nu există vreo soluţie.

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]':probleme-de-acoperire-1#bibliografie sau putem folosi un algoritm de tip $backtracking$ pentru a ne asigura că nu există vreo soluţie.

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

h2(#concluzii). 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':probleme-de-acoperire-2 încercăm o abordare orientată spre algoritmică.

h2(#bibliografie). 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
* [3] Ioan Tomescu, Probleme de combinatorică şi teoria grafurilor, ed. Didactică şi pedagogică, 1981
* [4] http://rec-puzzles.org/new/sol.pl/geometry/tiling/count.1x2
* [5] Romanian mathematical competitions 2001, ed Theta, Bucureşti 2001
* [6] Probleme de matematică traduse din revista sovietica KVANT, ed didactică şi pedagogică, Bucureşti, 1983

* [1] Mircea Ganga - _Teme şi probleme de matematică_, Ed. Tehnică, Bucureşti, 1991
* [2] Valentin Vornicu - _Olimpiada de matematică - de la provocare la experienţă_, Ed. Gil, 2003
* [3] Ioan Tomescu - _Probleme de combinatorică şi teoria grafurilor_, Ed. Didactică şi Pedagogică, 1981
* [4] 'http://brainyplanet.com/index.php/Count 1x2':http://brainyplanet.com/index.php/Count%201x2
* [5] _Romanian mathematical competitions 2001_, Ed. Theta, Bucureşti, 2001
* [6] _Probleme de matematică traduse din revista sovietica KVANT_, Ed. Didactică şi Pedagogică, Bucureşti, 1983
 

3384