Parlando di file di piastrelle

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
OriginalBBB
Messaggi: 69
Iscritto il: 09 nov 2009, 14:25

Parlando di file di piastrelle

Messaggio da OriginalBBB » 18 ago 2011, 12:31

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?

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Re: Parlando di file di piastrelle

Messaggio da exodd » 18 ago 2011, 12:44

Hint 1
Testo nascosto:
induzione
Hint 2
Testo nascosto:
fibonacci
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Parlando di file di piastrelle

Messaggio da Mist » 18 ago 2011, 13:16

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 [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Re: Parlando di file di piastrelle

Messaggio da exodd » 18 ago 2011, 14:02

Mist ha scritto: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.. :|
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

Avatar utente
Drago96
Messaggi: 1144
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Parlando di file di piastrelle

Messaggio da Drago96 » 18 ago 2011, 14:36

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:
exodd ha scritto:
Mist ha scritto: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.
Ultima modifica di Drago96 il 18 ago 2011, 14:43, modificato 1 volta in totale.
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Re: Parlando di file di piastrelle

Messaggio da exodd » 18 ago 2011, 14:41

Drago96 ha scritto: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.
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

Avatar utente
Drago96
Messaggi: 1144
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Parlando di file di piastrelle

Messaggio da Drago96 » 18 ago 2011, 14:47

exodd ha scritto: 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... :|
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Parlando di file di piastrelle

Messaggio da xXStephXx » 18 ago 2011, 14:59

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

Mist
Messaggi: 542
Iscritto il: 01 gen 2011, 23:52
Località: Provincia di Milano

Re: Parlando di file di piastrelle

Messaggio da Mist » 18 ago 2011, 16:13

Drago96 ha scritto: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:
exodd ha scritto:
Mist ha scritto: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 :D ma è una palla, è solo come esercizio per chi deve ancora prenderci la mano col costruire le ricorrenze...
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2

"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Re: Parlando di file di piastrelle

Messaggio da exodd » 18 ago 2011, 16:48

Se la forma chiusa non fosse così brutta, posterei la soluzione..
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

OriginalBBB
Messaggi: 69
Iscritto il: 09 nov 2009, 14:25

Re: Parlando di file di piastrelle

Messaggio da OriginalBBB » 18 ago 2011, 19:46

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?

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Re: Parlando di file di piastrelle

Messaggio da exodd » 19 ago 2011, 23:58

Beh, se sai risolvere un'equazione di k° grado, buon per te.. Io, sinceramente non ci riesco..
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

OriginalBBB
Messaggi: 69
Iscritto il: 09 nov 2009, 14:25

Re: Parlando di file di piastrelle

Messaggio da OriginalBBB » 20 ago 2011, 10:03

Servirebbe un computer :D

Rispondi