Probleme de acoperire

(Categoria Algoritmi, autor Cosmin Negruşeri)

În acest articol vom prezenta o serie de probleme apărute la concursurile de programare care au o tematică similară şi anume acea de acoperire în plan. În general acest tip de probleme sunt NP complete, dar pentru cazurile particulare prezentate problemele sunt rezolvabile.

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

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:

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 trei. Să trecem acum la ideea rezolvării.
Împărţim pătratul în patru 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 sa acopere câte un colţ al fiecăruia dintre cele trei pătrate rămase dupa cum observăm în figură.

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

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

Problema 2 (lot 2001 şi [1])

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 × 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 × 3 formate din câte două piese, iar pătratul de 7 × 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 patru 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 × 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.