h1. Probleme de acoperire (partea I)

(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)
 

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

(toc){width: 33em}*{text-align:center} *Conţinut*

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

* 'Problema 1 (Olimpiada de Informatică, Bucureşti, 1995)':probleme-de-acoperire-1#problema1
* 'Problema 2 (Lot 2001)':probleme-de-acoperire-1#problema2
* 'Problema 3 (Concursul Naţional de Informatică Lugoj, 1998)':probleme-de-acoperire-1#problema3

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

Î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 în "$secţiunea următoare...$":probleme-de-acoperire2.

Î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 în "$secţiunea următoare...$":probleme-de-acoperire-2.

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

h2(#problema1). Problema 1 (Olimpiada de Informatică, Bucureşti, 1995)

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:

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

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

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

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

h2(#problema2). Problema 2 (Lot 2001)

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:

În aceste trei figuri am epuizat toate cazurile pentru table de dimensiune $7$ unde lipseşte un pătrat. În fiecare desen am lăsat un pătrat de latură doi liber pentru a trata astfel cele patru cazuri în care pătrăţelul lipsă ar face parte din acest pătrat. Recurgând şi la rotaţiile acestor soluţii acoperim toate cazurile posibile pentru pătrăţelul lipsă. Menţionăm că cele trei soluţii au fost găsite cu uşurinţă de mână de autor.

Să presupunem că ştim cum să acoperim un pătrat de latură $6N + 1$. Să vedem acum cum acoperim un pătrat de latură $6N + 7$. În acest nou pătrat putem plasa într-un colţ de al lui un pătrat de latură $6N + 1$, care are un pătrăţel lipsă. Pătratul acesta îl ştim acoperi şi după cum arată şi figura următoare ne mai rămâne să acoperim două dreptunghiuri de dimensiuni $6 x 6n$, respectiv $6n x 6$ şi un pătrat de latură $7$ cu patrăţelul din colţ lipsă. Dreptunghiurile le putem acoperi cu dreptunghiuri de dimensiuni $2 x 3$ formate din câte două piese, iar pătratul de $7 x 7$ cu un colţ lipsă este un caz pentru $N = 1$ al problemei noastre.

Să presupunem că ştim cum să acoperim un pătrat de latură $6N + 1$. Să vedem acum cum acoperim un pătrat de latură $6N + 7$. În acest nou pătrat putem plasa într-un colţ de-al lui un pătrat de latură $6N + 1$, care are un pătrăţel lipsă. Pătratul acesta îl ştim acoperi şi după cum arată şi figura următoare ne mai rămâne să acoperim două dreptunghiuri de dimensiuni $6 x 6n$, respectiv $6n x 6$ şi un pătrat de latură $7$ cu patrăţelul din colţ lipsă. Dreptunghiurile le putem acoperi cu dreptunghiuri de dimensiuni $2 x 3$ formate din câte două piese, iar pătratul de $7 x 7$ cu un colţ lipsă este un caz pentru $N = 1$ al problemei noastre.

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

h2(#prob1ema3). Problema 3 ( _Concursul naţional de informatică Lugoj, 1998_ )

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!

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

h2(#prob1ema4). Problema 4

h2(#problema4). 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.
h3. Soluţie:

Prima observaţie pe care o facem este aceea că $N$ trebuie să fie par pentru ca tabla să poată fi acoperită. Este evident pentru cazurile $N = 2$ sau $N = 4$ că problema nu are soluţie, dar pentru cazuri mai mari demonstraţia faptului că există sau nu există soluţie pare dificilă, şi valorile lui $N$ pentru care o abordare exhaustivă a posibilităţilor de  acoperire a tablei cu dominouri ar fi eficientă sunt destul de mici.

Prima observaţie pe care o facem este aceea că $N$ trebuie să fie par pentru ca tabla să poată fi acoperită. Este evident pentru cazurile $N = 2$ sau $N = 4$ că problema nu are soluţie, dar pentru cazuri mai mari demonstraţia faptului că există sau nu există soluţie pare dificilă, şi valorile lui $N$ pentru care o abordare exhaustivă a posibilităţilor de acoperire a tablei cu dominouri ar fi eficientă sunt destul de mici.

O idee interesantă este aceea de a colora pătratele tablei în acelaşi mod în care se colorează o tablă de şah, aşa cum vedem în figura următoare.
p=. !probleme-de-acoperire-1?P41.jpg!

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.

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]':probleme-de-acoperire-1#bibliografie secţiunea $1.1 Invariant$, sau în '[2]':probleme-de-acoperire-1#bibliografie secţiunea $Probleme de colorare şi acoperire$.

h2(#prob1ema5). Problema 5

h2(#problema5). Problema 5

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

Pentru $N = 1$ avem o posibilitate, pentru $N = 2$ avem două posibilităţi, iar în cazul general daca notăm cu <tex> F[n] </tex> numărul de posibilităţi avem, aşa cum putem observa şi din figură, <tex> F[n] = F[n - 1] + F[n - 2] </tex>, deci exact şirul lui Fibonacci.

Pentru $N = 1$ avem o posibilitate, pentru $N = 2$ avem două posibilităţi, iar în cazul general daca notăm cu <tex> F[n] </tex> numărul de posibilităţi, avem, aşa cum putem observa şi din figură, <tex> F[n] = F[n - 1] + F[n - 2] </tex>, deci exact şirul lui Fibonacci.

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

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

h2(#problema6). Problema 6 (ONI 2001)

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

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

Putem observa uşor că <tex> A[2n + 2] = 3A[2n] + 2B[2n - 2] </tex>, iar <tex> B[2n] = A[2n] + B[2n - 2] </tex>. Aceste două recurenţe ar fi fost de ajuns pentru a rezolva problema în concurs. În cartea [3] rezolvarea continuă pentru a determina un număr explicit: <tex> A[2n + 2] = 3 A[2n] + 2A[2n - 2] + 2B[2n - 4] </tex> (am înlocuit pe <tex> B[2n - 2] </tex>). Mai departe obţinem <tex> A[2n + 2] = 4 A[2n] - A[2n - 2] </tex>. Putem uşor afla că <tex> A[2] = 3 </tex> şi <tex> A[4] = 11 </tex>. Ecuaţia caracteristică a ecuaţiei liniare este <tex> X^{2} - 4X + 1 = 0 </tex>, iar de aici obţinem că <tex> A[2n] = 1/{2\sqrt{3}} * ((\sqrt{3} + 1) * (2 + \sqrt{3})^{n} + (\sqrt{3} - 1) * (2 - \sqrt{3})^{n}) </tex>. (metoda rezolvării recurenţelor liniare este prezentată în manualul de clasa a 11-a de matematică). Un astfel de răspuns nu ne prea ajută pe noi ca programatori pentru că ar trebui să putem efectua operaţii cu numere reale cu o precizie destul de mare pentru a ajunge la rezultatul dorit. Totuşi, faptul că am găsit o recurenţa lineară ne ajută să determinăm mult mai repede numărul de posibilităţi folosindu-ne de următorul raţionament:

Putem observa uşor că <tex> A[2n + 2] = 3A[2n] + 2B[2n - 2] </tex>, iar <tex> B[2n] = A[2n] + B[2n - 2] </tex>. Aceste două recurenţe ar fi fost de ajuns pentru a rezolva problema în concurs. În cartea '[3]':probleme-de-acoperire-1#bibliografie rezolvarea continuă pentru a determina un număr explicit: <tex> A[2n + 2] = 3 A[2n] + 2A[2n - 2] + 2B[2n - 4] </tex> (am înlocuit pe <tex> B[2n - 2] </tex>). Mai departe obţinem <tex> A[2n + 2] = 4 A[2n] - A[2n - 2] </tex>. Putem uşor afla că <tex> A[2] = 3 </tex> şi <tex> A[4] = 11 </tex>. Ecuaţia caracteristică a ecuaţiei liniare este <tex> X^{2} - 4X + 1 = 0 </tex>, iar de aici obţinem că <tex> A[2n] = \frac{1}{2\sqrt{3}} * ((\sqrt{3} + 1) * (2 + \sqrt{3})^{n} + (\sqrt{3} - 1) * (2 - \sqrt{3})^{n}) </tex> (metoda rezolvării recurenţelor liniare este prezentată în manualul de clasa a 11-a de matematică). Un astfel de răspuns nu ne prea ajută pe noi ca programatori pentru că ar trebui să putem efectua operaţii cu numere reale cu o precizie destul de mare pentru a ajunge la rezultatul dorit. Totuşi, faptul că am găsit o recurenţa liniară ne ajută să determinăm mult mai repede numărul de posibilităţi folosindu-ne de următorul raţionament:

Dacă avem o recurenţa <tex> X[n] = aX[n - 1] + bX[n - 2] </tex> atunci avem că:

Dacă avem o recurenţa <tex> X[n] = aX[n - 1] + bX[n - 2] </tex> atunci:

<tex>
\emph{}

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(#prob1ema7). Problema 7 ( _ACM ICPC 1997_ )

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]. 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(#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(#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(#prob1ema9). Problema 9

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