Problema CREDO semplice

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Problema CREDO semplice

Messaggioda Il_matematico » 17/04/2020, 14:55

Ho bisogno d'aiuto per trovare una legge ricorsiva, o in caso un altro metodo per il seguente problema:
Ho una stringa fissa di 21 caselle, che posso colorare di bianco o di nero ( le stringhe totali sono ovviamente 2^21). Quante sono le stringhe che non hanno mai tre caselle dello stesso colore adiacenti?
Grazie dell'aiuto
Il_matematico
 
Messaggi: 12
Iscritto il: 11/04/2020, 13:34

Re: Problema CREDO semplice

Messaggioda ciao1_123 » 17/04/2020, 16:34

B=bianco
N=nero
Hint1:
Testo nascosto:
Considera le parole che terminano per BN, NB, BB, NN

Hint2:
Testo nascosto:
Il numero di parole che terminano con BN è uguale al numero di quelle che terminano con NB per simmetria del problema. Analogamente quelle che terminano per NN e BB
ciao1_123
 
Messaggi: 6
Iscritto il: 22/11/2018, 19:29

Re: Problema CREDO semplice

Messaggioda Il_matematico » 18/04/2020, 16:16

Credo di esserci riuscito, mi posteresti anche tu una soluzione così le confronto e capisco, in caso, la presenza di "scorciatoie".
Il_matematico
 
Messaggi: 12
Iscritto il: 11/04/2020, 13:34

Re: Problema CREDO semplice

Messaggioda ciao1_123 » 18/04/2020, 19:18

Io l'ho risolto così:
Testo nascosto:
Chiamiamo [tex]a_n = \mbox{numero di parole che terminano con NN} = \mbox{numero di parole che terminano con BB}[/tex]
e [tex]b_n = \mbox{numero di parole che terminano con NB} = \mbox{numero di parole che terminano con BN}[/tex]
\begin{equation} a_n = b_{n-1} \end{equation}
\begin{equation} b_n = a_{n-1} + b_{n-1} \end{equation}
Ora chiamiamo [tex]S_n = 2a_n + 2b_n[/tex]
\begin{equation}S_n=2a_n+2b_n=2b_{n-1}+2(a_{n-1}+b_{n-1})=2a_{n-1}+2b_{n-1}+2(a_{n-2}+b_{n-2})=S_{n-1}+S_{n-2} \end{equation}
Poi ricaviamo [tex]S_1=2[/tex] e [tex]S_2=4[/tex] e abbiamo così ottenuto la successione:
\begin{equation}\begin{cases}
S_1=2 \\
S_2=4 \\
S_n=S_{n-1}+S_{n-2}
\end{cases}\end{equation}
ciao1_123
 
Messaggi: 6
Iscritto il: 22/11/2018, 19:29

Re: Problema CREDO semplice

Messaggioda afullo » 19/04/2020, 19:48

Testo nascosto:
Che è il doppio di Fibonacci...
afullo
 
Messaggi: 1792
Iscritto il: 13/03/2013, 22:06


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti