Combinazioni piastrelle per un sentiero lungo n metri

Messaggioda ValeTonarelli » 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:
ValeTonarelli
Starting Member
Starting Member
 
Messaggio: 1 di 2
Iscritto il: 17/03/2020, 14:46

Re: Combinazioni piastrelle per un sentiero lungo n metri

Messaggioda ValeTonarelli » 19/03/2020, 16:14

up ragazzi
ValeTonarelli
Starting Member
Starting Member
 
Messaggio: 2 di 2
Iscritto il: 17/03/2020, 14:46

Re: Combinazioni piastrelle per un sentiero lungo n metri

Messaggioda superpippone » 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è.....
Avatar utente
superpippone
Senior Member
Senior Member
 
Messaggio: 1960 di 1972
Iscritto il: 03/02/2011, 14:20
Località: TRIESTE

Re: Combinazioni piastrelle per un sentiero lungo n metri

Messaggioda axpgn » 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
axpgn
Cannot live without
Cannot live without
 
Messaggio: 15189 di 15833
Iscritto il: 20/11/2013, 22:03

Re: Combinazioni piastrelle per un sentiero lungo n metri

Messaggioda giammaria » 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"):}$
- Indicando i metri con m e i centimetri con cm, si ha m=100 cm. Quindi 5 centimetri equivalgono a metri m=100*5=500.
- E' disonesto che un disonesto si comporti in modo onesto (R. Powell)
giammaria
Cannot live without
Cannot live without
 
Messaggio: 5148 di 5184
Iscritto il: 29/12/2008, 22:19
Località: provincia di Asti

Re: Combinazioni piastrelle per un sentiero lungo n metri

Messaggioda axpgn » 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
axpgn
Cannot live without
Cannot live without
 
Messaggio: 15198 di 15833
Iscritto il: 20/11/2013, 22:03


Torna a Secondaria II grado

Chi c’è in linea

Visitano il forum: Nessuno e 18 ospiti