Probleme de acoperire (partea I)

Acest articol a fost adăugat de

Marius Stroe •Marius
Intră aici dacă doreşti să scrii articole sau află cum te poţi implica în celelalte proiecte infoarena!

(Categoria Algoritmi, Autor Cosmin Negruşeri)

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

Problema 1 (Olimpiada de Informatică, Bucureşti, 1995)

Se dă un pătrat de latură 2ⁿ 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:

Soluţie:

Prima întrebare care ne vine în minte este dacă aria ce trebuie acoperită este divizibilă cu 3. Aria este 4ⁿ – 1 = (4 – 1)(4^n-1 + 4^n-2 + … + 4 + 1), deci este multiplu de 3. Să trecem acum la ideea rezolvării.

Împărţim pătratul în 4 pătrate de dimensiuni egale. Unul dintre ele are un pătrat lipsă. Facem ca celelalte trei pătrate să aibă şi ele un pătrat lipsă prin plasarea unei piese care să acopere câte un colţ al fiecăruia dintre cele trei pătrate rămase, după cum observăm în figură.

Astfel am redus problema la patru noi probleme de dimensiuni mai mici.

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

Problema 2 (Lot 2001)

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:

Soluţie:

Să vedem întâi cum rezolvăm cazul minim în care N = 1.

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

Problema 3 (Concursul Naţional de Informatică Lugoj, 1998)

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

Soluţie:

Observăm că fiecare piesă este formată din 4 pătrăţele. De aici deducem că N² este multiplu de 4 deci N e multiplu de 2. Pentru N = 6 avem următoarea soluţie:

Pentru N > 6 putem împărţi pătratul într-un pătrat de latură 6 şi două dreptunghiuri de dimensiuni 6 x (N – 6) şi (N – 6) x N, după cum observăm în figura următoare. Dreptunghiurile pot fi acoperite cu piese de tip 3.

Problema 4

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

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.

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.

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 5

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

Soluţie:

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

Problema 6 (ONI 2001)

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

Soluţie:

Şi în această problemă N trebuie să fie par pentru ca tabla să poată fi acoperită. Avem următoarele posibilităţi la început:

Observăm că în ultimele două cazuri pătrăţelul rămas gol poate fi acoperit într-un singur mod de un nou domino, aşa cum ne arată dominoul haşurat. Numim $A[n]$ numărul de moduri în care poate fi acoperit un dreptunghi de dimensiune 3 x n de dominouri, şi $B[n]$ numărul de moduri în care putem acoperi un dreptunghi de 3 x n dominouri la care se mai lipeşte pe margine un domino vertical aşa cum vedem în figura următoare.

Putem observa uşor că $A[2n + 2] = 3A[2n] + 2B[2n - 2]$ , iar $B[2n] = A[2n] + B[2n - 2]$ . 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: $A[2n + 2] = 3 A[2n] + 2A[2n - 2] + 2B[2n - 4]$ (am înlocuit pe $B[2n - 2]$ ). Mai departe obţinem $A[2n + 2] = 4 A[2n] - A[2n - 2]$ . Putem uşor afla că $A[2] = 3$ şi $A[4] = 11$ . Ecuaţia caracteristică a ecuaţiei liniare este $X^{2} - 4X + 1 = 0$ , iar de aici obţinem că $A[2n] = \frac{1}{2\sqrt{3}} * ((\sqrt{3} + 1) * (2 + \sqrt{3})^{n} + (\sqrt{3} - 1) * (2 - \sqrt{3})^{n})$ (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 $X[n] = aX[n - 1] + bX[n - 2]$ atunci:

$\emph{} \[ \left( \begin{array}{ccc} a & b \\ 1 & 0 \end{array} \right)\] \emph{} \[ \left( \begin{array}{ccc} X[n - 1] \\ X[n - 2] \end{array} \right)\]$ $=$ $\emph{} \[ \left( \begin{array}{ccc} X[n] \\ X[n - 1] \end{array} \right)\]$ $\Leftrightarrow$ $\emph{} \[ \left( \begin{array}{ccc} a & b \\ 1 & 0 \end{array} \right)\]^{(n-1)} \emph{} \[ \left( \begin{array}{ccc} X[1] \\ X[0] \end{array} \right)\]$ $=$ $\emph{} \[ \left( \begin{array}{ccc} X[n] \\ X[n - 1] \end{array} \right)\]$

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

Problema 7 (ACM ICPC 1997)

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

Soluţie:

Poate părea surprinzător, dar pentru această problemă, deşi pare foarte grea, există o formulă: ${2}^{\frac{M*N}{2}} * \prod {(\cos^{2}\frac{m*pi}{M+1} + cos^{2}\frac{n*pi}{N+1})}^{\frac{1}{4}}$ 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 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.

Problema 8: Floor tiles (Lot matematică 2001)

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

Soluţie:

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

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

Problema 9

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.

Soluţie:

În figura următoare avem o soluţie greşită:

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.

Un dreptunghi de dimensiune N x M îl putem mări la unul de dimensiune (N + 2) x M folosind procedeul prezentat în ultima figură.

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

Bibliografie

[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 1×2
[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

remote content

infoarena informatica de performanta

Probleme de acoperire (partea I)

Problema 1 (Olimpiada de Informatică, Bucureşti, 1995)

Soluţie:

Problema 2 (Lot 2001)

Soluţie:

Problema 3 (Concursul Naţional de Informatică Lugoj, 1998)

Soluţie:

Problema 4

Soluţie:

Problema 5

Soluţie:

Problema 6 (ONI 2001)

Soluţie:

Problema 7 (ACM ICPC 1997)

Soluţie:

Problema 8: Floor tiles (Lot matematică 2001)

Soluţie:

Problema 9

Soluţie:

Concluzii

Bibliografie