4. Zadatak

Prvo rješenje.

Primijetimo da sve horizontalne pločice moraju biti postavljene u parovima, po dvije pločice jedna ispod druge.

Gledajući ploču slijeva nadesno, prekrivanje može započeti jednom vertikalnom ili parom horizontalnih pločica.

Promotrimo slučaj kad prekrivanje započinje jednom vertikalnom pločicom. Tada je duljina ploče koju još trebamo prekriti za točno jedan manja, pa ćemo ostatak ploče prekriti na točno onoliko načina koliko postoji za prekrivanje ploče koja ima duljinu za jedan manju.

Promotrimo slučaj kad prekrivanje započinje dvjema horizontalnim pločicama. Tada je duljina koju još trebamo prekriti za točno dva manja, pa ćemo ostatak ploče prekriti na točno onoliko načina koliko imamo za prekrivanje ploče koja ima duljinu za dva manju.

Označimo s $n$ duljinu ploče. Iz prethodne rasprave slijedi da je broj načina prekrivanja ploče duljine $n$ jednak zbroju broja načina prekrivanja ploče duljine $n-2$ i broja načina prekrivanja ploče duljine $n-1$.

Za ploču dimenzija $1\times2$ postoji točno jedan način prekrivanja jednom pločicom, a za ploču dimenzija $2\times2$ postoje točno dva načina prekrivanja dvjema pločicama.

Ispišimo sada broj načina prekrivanja za sve ploče dimenzija $n\times2$ od $n=1$ do $n=10$.

$n$	broj načina prekrivanja
$1$	$1$
$2$	$2$
$3$	$1+2=3$
$4$	$2+3=5$
$5$	$3+5=8$
$6$	$5+8=13$
$7$	$8+13=21$
$8$	$13+21=34$
$9$	$21+34=55$
$10$	$34+55=89$

Broj načina prekrivanja ploče dimenzija $10\times2$ s deset pločica dimenzija $2\times1$ iznosi $89$.

Drugo rješenje.

Kao u prethodnom rješenju, uočavamo da horizontalne pločice uvijek moraju biti postavljene u paru jedna ispod druge. Svaki par horizontalnih pločica zauzima dva stupca pa se na ploči dimenzija $10\times2$ može pojaviti od nula do pet takvih parova. Prebrojimo koliko različitih prekrivanja ploče imamo u svakom od tih slučajeva.

Ako nema horizontalnih pločica, sve pločice su vertikalne, a tada postoji samo jedno takvo prekrivanje ploče.

Ako postoji točno jedan par horizontalnih pločica, tada preostaje osam vertikalnih pločica. Par horizontalnih pločica možemo postaviti na $9$ različitih pozicija na ploči, stoga u ovom slučaju postoji $9$ različitih prekrivanja ploče.

Ako postoje točno dva para horizontalnih pločica, tada preostaje šest vertikalnih pločica. Prvi par horizontalnih pločica možemo smjestiti na $8$ načina, a drugi par na $7$ načina. Time smo dva puta prebrojali iste rasporede, stoga u ovom slučaju postoji $(8\cdot7):2=28$ različitih prekrivanja.

Ako postoje točno tri para horizontalnih pločica, tada preostaju četiri vertikalne pločice. Prebrojimo koliko različitih prekrivanja imamo u ovom slučaju, ovisno o položaju prvog para horizontalnih pločica:

• ako se prvi par horizontalnih pločica nalazi na prvom mjestu, tada imamo $(6\cdot5):2=15$ rasporeda druga dva horizontalna para pločica na preostala mjesta
• ako je prvi par na drugom mjestu, tada imamo $(5\cdot4):2=10$ rasporeda
• ako je prvi par na trećem mjestu, tada imamo $(4\cdot3):2=6$ rasporeda
• ako je prvi par na četvrtom mjestu, tada imamo $(3\cdot2):2=3$ rasporeda
• ako je prvi par na petom mjestu, tada imamo samo $1$ raspored.

Ukupno u ovom slučaju imamo $15+10+6+3+1=35$ različitih prekrivanja ploče.

Ako postoje točno četiri para horizontalnih pločica, tada preostaju dvije vertikalne pločice, koje možemo postaviti na $(6\cdot5):2=15$ različitih načina.

Ako postoji pet parova horizontalnih pločica, oni zauzimaju cijelu ploču, pa postoji samo jedno prekrivanje u ovom slučaju.

Sve zajedno, postoji $1+9+28+35+15+1=89$ različitih prekrivanja ploče dimenzija $10\times2$ s deset pločica dimenzija $2\times1$.