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.

h3. *Problema 5*
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.
 
p=. !probleme-de-acoperire?P51.jpg!
 
h3. *Problema 6* (ONI 2001, clasa a X-a şi [3])
 
Determinaţi numărul de moduri în care poate fi acoperit un dreptunghi de dimensiuni $3 x N$ cu dominouri.
 
h3. 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:
 
p=. !probleme-de-acoperire?P61.jpg!
 
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.
 
p=. !probleme-de-acoperire?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 $x^2^ – 4x + 1 = 0$, 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ă:
 
<tex>
\emph{}
\[ \left( \begin{array}{ccc}
a & b \\
1 & 0 \end{array} \right)\]
 
x
 
\emph{}
\[ \left( \begin{array}{ccc}
X[n - 1] \\
X[n - 2] \end{array} \right)\]
</tex>
 
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.