Corso Prime: Pb. 10.3 (tassellare scacchiera lunga)

[matematik]

Ecco il problema 10 della lista 3:

Ho una scacchiera rettangolare $ 10\times 2 $ e $ 10 $ tessere da domino delle dimensioni giuste da ricoprire esattamente $ 2 $ caselle.
In quanti modi posso ricoprire completamente la scacchiera con le $ 10 $ tessere?

Suggerimento:

Testo nascosto:

Cominciamo coprendo le due caselle di uno dei lati "corti" della tabella.
Possiamo farlo in due modi:
1) con una sola tessera che le copre entrambe.
2) con due tessere diverse, che coprono ciascuna una delle due caselle (e quindi coprono anche le altre due caselle della scacchiera immediatamente vicine).

Le tassellazioni che ottengo cominciando nel primo modo sono tante quanti sono i modi di ricoprire con 9 tessere la restante tabella $ 9\times 2 $

Le tassellazioni che ottengo cominciando nel secondo modo sono tante quanti sono i modi di ricoprire con 8 tessere la restante tabella $ 8\times 2 $

Questo mi fa intuire come scrivere una legge ricorsiva che risolva il mio problema.......
(ricordare che la lezione 3 e': combinatoria ricorsiva)

[Gi.]

Bel problema

Testo nascosto:

Sia $ r_n $ il numero di ricoprimenti possibili di un rettangolo $ r \times 2 $.
A questo punto preso un rettangolo $ r\times 2 $ divido il problema in due "sottosezioni":

K: inserisco un pezzo verticalmente sull'estrema destra in modo da ricoprire le ultime due caselle.

j: inserisco due pezzi orizzontalmente sull'estrema destra in modo da ricoprire le ultime quattro caselle.

Il numero totale di possibili ricoprimenti del rettangolo $ r \times 2 $ sarà dato dalla somma del numero di modi in cui posso finire di ricoprire le due possibilità appena citate, infatti alcun ricoprimento è comune a J e K. Ma K è il numero di modi di ricoprire un rettangolo $ (r-1) \times 2 $ e J quelli di ricoprirne uno $ (r-2) \times 2 $. ossia K$ =r_{n-1} $ e J$ =r_{n-2} $.
Quindi

$ r_{n}=r_{n-1}+r_{n-2} $

Inoltre valgono, evidentemente, $ r_1=1 $ e $ r_2=2 $

La relazione ricorsiva è quella dei numeri di Fibonacci ed $ r_{10}=89 $.