Parlando di file di piastrelle

[OriginalBBB]

Sia dato una fila di N piastrelle, in quanti modi è possibile colorarli di bianco e di nero in modo che due piastrelle bianche non siano adiacenti?

[exodd]

Hint 1

Testo nascosto:

induzione

Hint 2

Testo nascosto:

fibonacci

[Mist]

Rilancio: Dato $A=\{ 0,1,2,\dots ,k \}$ e detto $B_{n+1} := \{ (a_1,a_2 \dots a_{n+1}) \in A^{n+1} : a_{j}+a_{j+1} \neq 0 \quad \forall \quad 1\leq j \leq n \}$, calcolare $|B_n|$.

[exodd]

Rilancio: Dato $A=\{ 0,1,2,\dots ,k \}$ e detto $B_{n+1} := \{ (a_1,a_2 \dots a_{n+1}) \in A^{n+1} : a_{j}+a_{j+1} \neq 0 \quad \forall \quad 1\leq j \leq n \}$, calcolare $|B_n|$.

Se capisco cosa sono gli $a_i$ posso iniziare a risolverlo..

[Drago96]

Osservazione 0: Dopo una piastrella bianca sono obbligato a metterne una nera, mentre dopo una nera ho 2 scelte.
Sia $C_n$ il numero cercato e $N_n$ il numero delle combinazioni che terminano con una piastrella nera date $n$ piastrelle.
Osservazione 1: $N_n=C_{n-1}$. (segue dall'Osservazione 0)
Osservazione 2: $C_{n+1}=C_n+N_n$. (segue dall'Osservazione 0)

Unendo O1 e O2, e tenendo presente che $C_1=2$, si ha che $C_n=F_{n-2}$, con $F_n$ n-esimo numero di Fibonacci e $F_0=0$

Sono sicuro che è giusta, ma non so come dimostrarla più formalmente...
E' che mi pare ovvio...


EDIT:

Rilancio: Dato $A=\{ 0,1,2,\dots ,k \}$ e detto $B_{n+1} := \{ (a_1,a_2 \dots a_{n+1}) \in A^{n+1} : a_{j}+a_{j+1} \neq 0 \quad \forall \quad 1\leq j \leq n \}$, calcolare $|B_n|$.

Se capisco cosa sono gli $a_i$ posso iniziare a risolverlo..

Mi sembra che gli $a_i$ siano elementi di $A$ , presi "a caso" (con la restrizione che non ci siano due 0 consecutivi), fino a formare una $n+1$-upla.

[exodd]

Osservazione 0: Dopo una piastrella bianca sono obbligato a metterne una nera, mentre dopo una nera ho 2 scelte.
Sia $C_n$ il numero cercato e $N_n$ il numero delle combinazioni che terminano con una piastrella nera date $n$ piastrelle.
Osservazione 1: $N_n=C_{n-1}$. (segue dall'Osservazione 0)
Osservazione 2: $C_{n+1}=C_n+N_n$. (segue dall'Osservazione 0)

Unendo O1 e O2, e tenendo presente che $C_1=2$, si ha che $C_n=F_{n-2}$, con $F_n$ n-esimo numero di Fibonacci e $F_0=0$

Sono sicuro che è giusta, ma non so come dimostrarla più formalmente...
E' che mi pare ovvio...

Ti mancano solo due cose:
Se vuoi veramente dimostrare che la sequenza dei $C_n$ è la sequenza di Fibonacci shiftata, semplicemente devi scrivere la relazione che lega i $C_n$ tra loro, e i primi 2 termini della successione..
Facendo questo, è dimostrata formalmente.

[Drago96]

Ti mancano solo due cose:
Se vuoi veramente dimostrare che la sequenza dei $C_n$ è la sequenza di Fibonacci shiftata, semplicemente devi scrivere la relazione che lega i $C_n$ tra loro, e i primi 2 termini della successione..
Facendo questo, è dimostrata formalmente.

Allora,

abbiamo da O1 e O2 che $C_{n+1}=C_n+C_{n-1}$ ; facendo i primi casi a mano, abbiamo $C_1=2$ e $C_2=3$ .

E' che non so se le osservazioni siano così evidenti...

[xXStephXx]

Usa l'induzione come scritto nell'hint 1 da exodd.
edit: non avevo letto O1 e O2, ok, dovresti stare apposto così.

[Mist]

Osservazione 0: Dopo una piastrella bianca sono obbligato a metterne una nera, mentre dopo una nera ho 2 scelte.
Sia $C_n$ il numero cercato e $N_n$ il numero delle combinazioni che terminano con una piastrella nera date $n$ piastrelle.
Osservazione 1: $N_n=C_{n-1}$. (segue dall'Osservazione 0)
Osservazione 2: $C_{n+1}=C_n+N_n$. (segue dall'Osservazione 0)

Unendo O1 e O2, e tenendo presente che $C_1=2$, si ha che $C_n=F_{n-2}$, con $F_n$ n-esimo numero di Fibonacci e $F_0=0$

Sono sicuro che è giusta, ma non so come dimostrarla più formalmente...
E' che mi pare ovvio...


EDIT:

Rilancio: Dato $A=\{ 0,1,2,\dots ,k \}$ e detto $B_{n+1} := \{ (a_1,a_2 \dots a_{n+1}) \in A^{n+1} : a_{j}+a_{j+1} \neq 0 \quad \forall \quad 1\leq j \leq n \}$, calcolare $|B_n|$.

Se capisco cosa sono gli $a_i$ posso iniziare a risolverlo..

Mi sembra che gli $a_i$ siano elementi di $A$ , presi "a caso" (con la restrizione che non ci siano due 0 consecutivi), fino a formare una $n+1$-upla.

Esatto ma è una palla, è solo come esercizio per chi deve ancora prenderci la mano col costruire le ricorrenze...

[exodd]

Se la forma chiusa non fosse così brutta, posterei la soluzione..

[OriginalBBB]

Generalizzando...

Dato una fila di N piastrelle, come colorarle di bianco e nero in modo che tra una bianca e la successiva vi siano almeno k piastrelle nere?

[exodd]

Beh, se sai risolvere un'equazione di k° grado, buon per te.. Io, sinceramente non ci riesco..

[OriginalBBB]

Servirebbe un computer