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

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

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

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

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

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

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$. 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(#problema5). Problema 5

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

h2(#problema6). 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] = 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:

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

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(#problema7). 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.
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}} * {(\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.

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 (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)

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