Lista de probleme 2

Ovi este un băieţel foarte isteţ căruia îi place să scrie pe asfalt cu creta şi să ţopăie. El desenează cu cretă roşie un dreptunghi de lăţime exact 2 metri şi lungime N metri, pe care îl împarte în pătrate egale de latură 1 metru, unele laturi interioare fiind desenate cu cretă roşie, iar restul laturilor interioare cu cretă albă. Ovi porneşte din pătratul aflat în colţul stânga sus al dreptunghiului, sărind dintr-un pătrat în altul vecin pe linie sau coloană, cu condiţia ca latura care desparte cele două pătrate să nu fie colorată în roşu. El îşi doreşte ca prin sărituri succesive să ajungă în toate pătratele dreptunghiului, dar a observat că numai pentru anumite variante de colorare a laturilor pătratelor reuşeşte acest lucru.

Ajutaţi-l pe Ovi să numere câte posibilităţi de colorare în roşu a unor laturi interioare ale pătratelor sunt astfel încât plecând din colţul stânga sus să poată ajunge prin sărituri în oricare alt pătrat.

Renumitul arhitect Prăbuşilă doreşte să construiască unul din cele mai interesante turnuri de pe planetă. Acest turn, în mod cu totul deosebit, va avea etaje de diverse lăţimi, între 1 şi 100, numere întregi. Prăbuşilă s-a hotărât deja ce dimensiune va avea fiecare din etajele turnului, dar nu şi cum să le aşeze pe orizontală. El ar dori mai întâi să ştie câte variante are.