Lista de probleme 1

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.