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?P51.jpg!

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.

* 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 <tex> A[n] </tex> numărul de moduri în care poate fi acoperit un dreptunghi de dimensiune $3 x n$ de dominouri, şi <tex> B[n] </tex> 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:

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

* 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 avem că:

<tex>
\emph{}

X[n] \\
X[n - 1] \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.

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

h3. *Problema 7* (ACM ICPC 1997)

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

h3. *Problema 8* (Lot matematică, 2001 şi acm.uva.es, 10644 Floor tiles)