Passa al tema normale
Discussioni su argomenti di matematica di scuola secondaria di secondo grado

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

Combinazioni piastrelle per un sentiero lungo n metri

17/03/2020, 14:49

Ciao a tutti,
sono un pò di giorni che non riesco a trovare una formula per risolvere questo Problema:
Dobbiamo piastrellare una sentiero largo 1m con delle piastrelle che esistono in 2 dimensioni: 1 × 1 m o 1 × 2 m.

Quelle da 1 × 1 possono essere bianche o blu, quelle da 1 × 2 possono essere gialle, verdi o nere. Se il sentiero è lungo n metri, in quanti modi diversi puo essere piastrellato?

Esempio dato:
Se lungo 7m ho 1640 modi diversi

Qualcuno è in grado di aiutarmi? :cry:

Re: Combinazioni piastrelle per un sentiero lungo n metri

19/03/2020, 16:14

up ragazzi

Re: Combinazioni piastrelle per un sentiero lungo n metri

20/03/2020, 12:33

Ho cominciato a contare....
Nella prima colonna la lunghezza in metri, nella seconda le combinazioni possibili.

1-2
2-7
3-20
4-61
5-182

Ha questo punto ho notato che:
2x3=6 6+1=7
7x3=21 21-1=20
20x3=60 60+1=61
61x3=183 183-1=182

Continuando solo con la formula
182x3=546 546+1=547
547x3=1641 1641-1=1640

Cioè per passare da un "livello" all'altro, basta moltiplicare per 3, e alternativamente, togliere o aggiungere 1.

N.B. Faccio come De Fermat: so che è così, ma non so perchè.....

Re: Combinazioni piastrelle per un sentiero lungo n metri

20/03/2020, 16:58

Dunque ...

La relazione di ricorrenza è questa: $a_n=7*a_(n-2)+6*a_(n-3)$

La spiegazione per $7*a_(n-2)$ ce l'ho mentre per l'altro pezzo è ancora nebulosa :D

Cordialmente, Alex

EDIT: ok, adesso mi è chiaro anche il resto :D quando ho tempo, spiego ...

EDIT2: ringrazio superpippone che mi ha evitato di fare i conti più lunghi :-D

Re: Combinazioni piastrelle per un sentiero lungo n metri

21/03/2020, 20:55

Complimenti a chi ha dato risposte; io non sapevo che pesci prendere. Nell'attesa della spiegazione di axpgn, do la formula di $a_n$ in funzione di $n$, dedotta dalle osservazioni di superpippone.

$a_n={((3^(n+1)-1)/4 if n="dispari"),((3^(n+1)+1)/4 if n="pari"):}$

Re: Combinazioni piastrelle per un sentiero lungo n metri

23/03/2020, 01:04

Dunque ...

Supponiamo di avere un sentiero lungo $n-2$ metri il quale può essere formato in $a_(n-2)$ modi diversi.
Se alla fine del sentiero posiamo una piastrella $1 xx 2$ otteniamo un sentiero lungo $n$ metri.
Le piastrelle di questo tipo sono di tre colori diversi quindi possiamo "completare" ciascuno degli $a_(n-2)$ diversi sentieri lunghi $n-2$ metri in tre modi, ottenendo perciò $3a_(n-2)$ sentieri diversi lunghi $n$ metri.
Però, invece di una piastrella da due metri, potremmo usarne due $1 xx 1$ per completare il sentiero; in questo caso ci sono $4$ modi per farlo portando quindi il totale a $7a_(n-2)$ modi per ottenere un sentiero lungo $n$ metri.
E questo giustifica il primo addendo della relazione ricorsiva.

Se ponessimo la piastrella lunga (o due corte) all'inizio del sentiero di $n-2$ metri otterremmo ancora uno dei percorsi precedenti, nessuno nuovo; la stessa cosa accadrebbe se la intercalassimo tra una piastrella e l'altra.
Se invece sovrapponessimo una piastrella lunga (o due corte) a quelle esistenti avremmo due possibilità: o la piastrella si sovrappone esattamente a una doppia o a due corte (e ricadremmo ancora nei casi precedenti) oppure ricoprirebbe una corta e mezza lunga.
In tal caso, togliendo quella corta, la lunga si sovrapporrebbe ad una lunga formando un sentiero lungo $n-3$ metri che si può completare aggiungendo una piastrella lunga ed una corta, in sei combinazioni diverse ovvero, in tal caso, otterremmo $6a_(n-3)$ modi diversi per costruire un sentiero lungo $n$ metri.
Altre possibilità non ci sono quindi sommando le due modalità avremo la relazione ricorsiva vista prima. :D

Lo so, è un po' complicato ma che ci volete fare, questo mi è venuto :-D

C'è una relazione più semplice, oltre a una forma chiusa, che altri ( :D ) hanno trovato, quindi lascio a loro ... :wink:

Cordialmente, Alex
Rispondi al messaggio


Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000— Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.