Problema CREDO semplice

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.
Rispondi
Il_matematico
Messaggi: 15
Iscritto il: 11/04/2020, 13:34

Problema CREDO semplice

Messaggio da Il_matematico »

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
ciao1_123
Messaggi: 6
Iscritto il: 22/11/2018, 19:29

Re: Problema CREDO semplice

Messaggio da ciao1_123 »

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
Il_matematico
Messaggi: 15
Iscritto il: 11/04/2020, 13:34

Re: Problema CREDO semplice

Messaggio da Il_matematico »

Credo di esserci riuscito, mi posteresti anche tu una soluzione così le confronto e capisco, in caso, la presenza di "scorciatoie".
ciao1_123
Messaggi: 6
Iscritto il: 22/11/2018, 19:29

Re: Problema CREDO semplice

Messaggio da ciao1_123 »

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}
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Problema CREDO semplice

Messaggio da afullo »

Testo nascosto:
Che è il doppio di Fibonacci...
Rispondi