Corso Prime: Pb. 10.3 (tassellare scacchiera lunga)

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
matematik
Messaggi: 72
Iscritto il: 27 apr 2009, 11:42
Località: Roma

Corso Prime: Pb. 10.3 (tassellare scacchiera lunga)

Messaggio da matematik » 16 dic 2013, 18:11

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.
Messaggi: 149
Iscritto il: 18 dic 2012, 16:45

Re: Corso Prime: Pb. 10.3 (tassellare scacchiera lunga)

Messaggio da Gi. » 01 gen 2014, 09:49

Bel problema :D
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 $.

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti