ps: io l'ho risolto con la forza bruta e ci ho messo quasi mezz'ora (ho perso tempo con i casi più semplici, cosa che si è rivelata inutile poi)
19 palline rosso-blu
19 palline rosso-blu
In quanti modi diversi possiamo disporre in una fila 19 palline rosse o blu, in modo che non ci siano mai due palline rosse consecutive, nè tre palline blu consecutive?
ps: io l'ho risolto con la forza bruta e ci ho messo quasi mezz'ora (ho perso tempo con i casi più semplici, cosa che si è rivelata inutile poi)
ps: io l'ho risolto con la forza bruta e ci ho messo quasi mezz'ora (ho perso tempo con i casi più semplici, cosa che si è rivelata inutile poi)
"Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
Re: 19 palline rosso-blu
Ti accontento subito:iademarco ha scritto:ps: io l'ho risolto con la forza bruta..
In quanti modi diversi possiamo disporre in una fila 2009 palline rosse o blu, in modo che non ci siano mai due palline rosse consecutive, nè tre palline blu consecutive?
Ps. interessa in primo luogo il procedimento..
Ps2. il risultato empirico dovrebbe essere dell'ordine di 10^248..
Ps3.Trovare la formula chiusa del risultato..
Ultima modifica di jordan il 16 apr 2009, 15:34, modificato 3 volte in totale.
The only goal of science is the honor of the human spirit.
Accetto la sfida 
E poi vedremo se la forza bruta è davvero utile o no
jordan Ps. interessa in primo luogo il procedimento..
iademarco Ps. il procedimento usando la forza bruta è appunto la forza bruta
jordan Ps2. il risultato empirico dovrebbe essere dell'ordine di 10^248..
iademarco Ps2. con la forza bruta i risultati si possono dare solamente approssimati, quindi la mia risposta è 10^248
jordan Ps3.Trovare la formula chiusa del risultato..
iademarco Ps3. la formula chiusa è: forza bruta
E poi vedremo se la forza bruta è davvero utile o no
jordan Ps. interessa in primo luogo il procedimento..
iademarco Ps. il procedimento usando la forza bruta è appunto la forza bruta
jordan Ps2. il risultato empirico dovrebbe essere dell'ordine di 10^248..
iademarco Ps2. con la forza bruta i risultati si possono dare solamente approssimati, quindi la mia risposta è 10^248
jordan Ps3.Trovare la formula chiusa del risultato..
iademarco Ps3. la formula chiusa è: forza bruta
"Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
Siano $ i,j \in \{R,B\} $ i pedici che rappresentano il colore della pallina, sia $ n \in \mathbb{N} \setminus \{0,1\} $ fissato, e sia definito $ a_{n,ij} \in \mathbb{N} $ il numero di sequenze di palline di lunghezza $ n $ e che iniziano con le prime due palline con colori $ i $ e $ j $ e che naturalmente rispettano l'ipotesi del problema.
Sia inoltre $ \displaystyle a_n= \sum_{i,j}{a_{n,ij}} $ il numero di sequenze di lunghezza $ n $, senza il vincolo sul colore delle prime due palline. Le ipotesi del problema sono equivalenti a:
i) $ a_{n+1,RR}=a_{n,RR}=0, \forall n \in \mathbb{N} $.
ii) $ a_{n+1,RB}=a_{n,BB}+a_{n,BR}, \forall n \in \mathbb{N} \setminus\{0,1\} $.
iii) $ a_{n+1,BR}=a_{n,RB}, \forall n \in \mathbb{N} \setminus\{0,1\} $.
iv) $ a_{n+1,BB}=a_{n,BR},\forall n \in \mathbb{N} \setminus\{0,1\} $.
Quello che ne possiamo ricavare è qualcosa di molto simpatico:
$ a_{n+1}=\displaystyle \sum_{i,j}{a_{n+1,ij}}=a_{n+1,RB}+a_{n+1,BB}+a_{n+1,BR}= $
$ =(a_{n,BB}+a_{n,BR})+(a_{n,BR})+(a_{n,RB})= $
$ =(a_{n-1,BR}+a_{n,BR})+(a_{n-1,RB})+(a_{n-1,BB}+a_{n-1,BR})= $
$ =(a_{n-2,RB}+a_{n-1,RB})+(a_{n-2,BB}+a_{n-2,BR})+(a_{n-2,BR}+a_{n-1,BR})= $
$ =(a_{n-2,RB}+a_{n-1,RB})+(a_{n-2,BB}+a_{n-1,BB})+(a_{n-2,BR}+a_{n-1,BR})= $
$ =(a_{n-1,RB}+a_{n-1,BB}+a_{n-1,BR})+(a_{n-2,RB}+a_{n-2,BB}+a_{n-2,BR})= $
$ =a_{n-1}+a_{n-2}, \forall n \in \mathbb{N}\setminus\{0,1\} $.
Abbiamo la ricorsione, con il vincolo (ricavabile "all'indietro"): $ a_0=a_1=a_2-1=2 $.
[Questo è quanto ci basta con due conti per affermare che $ a_{19}=351 $..]
Passiamo ora a trovare la formula chiusa di $ \{a_n\}_{n \in \mathbb{N}} $: siano $ \alpha, \beta, \gamma $ le tre radici del polinomio caratteristico $ p(x)=x^3-x-1 $.
Dato che $ deg(p(x)) \in 2\mathbb{N}+1 $ possiamo assumere senza perdità di generalità che $ \alpha \in \mathbb{R} $.
Una piccola nota di cultura generale su Cardano (mi auguro qui che la buona percentuale dei lettori ne conoscano già la dimostrazione) ci fornisce il valore di $ \displaystyle \alpha= \sqrt[3]{\frac{1}{2}+\frac{1}{6}\sqrt{\frac{23}{3}}}-\sqrt[3]{\frac{1}{2}-\frac{1}{6}\sqrt{\frac{23}{3}}} $ (circa 1,324..) (*)
Un veloce grafico sull'intersezione delle curve $ x^3 $ e $ x+1 $ ci fa subito vedere inoltre che $ (\beta, \gamma) \in (\mathbb{C} \setminus \mathbb{R})^2 $, ma $ \beta=\overline{\gamma} $ per cui esistono $ (c,d) \in \mathbb{R}^2 $ tali che $ d \neq 0 $, $ \beta=c+id $ e $ \gamma=c-id $.
Ricordando che $ p(\alpha)=p(\beta)=p(\gamma)=0 $ abbiamo $ p(x)=(x-\alpha)(x-\beta)(x-\gamma) $ da cui otteniamo $ \beta+\gamma=2c=-\alpha $ e $ \displaystyle \beta\gamma=c^2+d^2=\frac{1}{\alpha} $.
Abbiamo quindi ottenuto anche il valore delle altre due radici complesse, dove wlog $ \displaystyle \beta=\overline{\gamma}=-\frac{\alpha}{2}+i\sqrt{\frac{4-\alpha^3}{4\alpha}} $. (**)
Notiamo qui che $ |\beta|=|\gamma|=\sqrt{c^2+d^2}=\sqrt{\frac{1}{\alpha}}<1<\alpha $. (***)
Esistono adesso $ (x,y,z) \in \mathbb{R}^3 $ tali che $ a_n=x\alpha^n+y\beta^n+z\gamma^n, \forall n \in \mathbb{N} $.
Imponiamo i vincoli su valori "piccoli" di $ n $ e otteniamo tale tripla, infatti per quanto detto prima vale:
i) $ x\alpha^0+y\beta^0+z\gamma^0=2 $
ii) $ x\alpha^1+y\beta^1+z\gamma^1=2 $
iii) $ x\alpha^2+y\beta^2+z\gamma^2=3 $.
Che, eliminando la i), è equivalente a:
iv) $ x (\alpha-\gamma) + y (\beta-\gamma)=2-2\gamma $
v) $ x (\alpha^2-\gamma^2) + y (\beta^2-\gamma^2)=3-2\gamma^2 $.
Ma questo è un sistema di Cramer, con soluzione $ \displaystyle (x,y)=(\frac{(2-2\gamma)(\beta^2-\gamma^2)+(\gamma-\beta)(3-2\gamma^2)}{(\alpha-\gamma)(\beta^2-\gamma^2)+(\gamma-\beta)(\alpha^2-\gamma^2)}, $ $ \displaystyle \frac{(\alpha-\gamma)(\beta^2-\gamma^2)+(2\gamma-2)(\alpha^2-\gamma^2)}{(\alpha-\gamma)(\beta^2-\gamma^2)+(\gamma-\beta)(\alpha^2-\gamma^2)}) $. (****)
Bene, abbiamo finito, e possiamo concludere:
è la valida la formula $ \displaystyle a_n=x \alpha^n + y \beta^n + z\gamma^n, \forall n \in \mathbb{N}\setminus \{0,1\} $,
dove $ \alpha $ è stata definita dalla (*), $ (\beta, \gamma) $ dalla (**), e $ (x,y) $ dalla (****), con $ x+y+z=2 $.
Da notare inoltre che grazie alla (***), poichè $ 0<|\beta|=|\gamma|<|\alpha| $ , vale $ \displaystyle \lim_{n\to + \infty}{\frac{a_{n+1}}{a_n}}= \alpha $.
Sia inoltre $ \displaystyle a_n= \sum_{i,j}{a_{n,ij}} $ il numero di sequenze di lunghezza $ n $, senza il vincolo sul colore delle prime due palline. Le ipotesi del problema sono equivalenti a:
i) $ a_{n+1,RR}=a_{n,RR}=0, \forall n \in \mathbb{N} $.
ii) $ a_{n+1,RB}=a_{n,BB}+a_{n,BR}, \forall n \in \mathbb{N} \setminus\{0,1\} $.
iii) $ a_{n+1,BR}=a_{n,RB}, \forall n \in \mathbb{N} \setminus\{0,1\} $.
iv) $ a_{n+1,BB}=a_{n,BR},\forall n \in \mathbb{N} \setminus\{0,1\} $.
Quello che ne possiamo ricavare è qualcosa di molto simpatico:
$ a_{n+1}=\displaystyle \sum_{i,j}{a_{n+1,ij}}=a_{n+1,RB}+a_{n+1,BB}+a_{n+1,BR}= $
$ =(a_{n,BB}+a_{n,BR})+(a_{n,BR})+(a_{n,RB})= $
$ =(a_{n-1,BR}+a_{n,BR})+(a_{n-1,RB})+(a_{n-1,BB}+a_{n-1,BR})= $
$ =(a_{n-2,RB}+a_{n-1,RB})+(a_{n-2,BB}+a_{n-2,BR})+(a_{n-2,BR}+a_{n-1,BR})= $
$ =(a_{n-2,RB}+a_{n-1,RB})+(a_{n-2,BB}+a_{n-1,BB})+(a_{n-2,BR}+a_{n-1,BR})= $
$ =(a_{n-1,RB}+a_{n-1,BB}+a_{n-1,BR})+(a_{n-2,RB}+a_{n-2,BB}+a_{n-2,BR})= $
$ =a_{n-1}+a_{n-2}, \forall n \in \mathbb{N}\setminus\{0,1\} $.
Abbiamo la ricorsione, con il vincolo (ricavabile "all'indietro"): $ a_0=a_1=a_2-1=2 $.
[Questo è quanto ci basta con due conti per affermare che $ a_{19}=351 $..]
Passiamo ora a trovare la formula chiusa di $ \{a_n\}_{n \in \mathbb{N}} $: siano $ \alpha, \beta, \gamma $ le tre radici del polinomio caratteristico $ p(x)=x^3-x-1 $.
Dato che $ deg(p(x)) \in 2\mathbb{N}+1 $ possiamo assumere senza perdità di generalità che $ \alpha \in \mathbb{R} $.
Una piccola nota di cultura generale su Cardano (mi auguro qui che la buona percentuale dei lettori ne conoscano già la dimostrazione) ci fornisce il valore di $ \displaystyle \alpha= \sqrt[3]{\frac{1}{2}+\frac{1}{6}\sqrt{\frac{23}{3}}}-\sqrt[3]{\frac{1}{2}-\frac{1}{6}\sqrt{\frac{23}{3}}} $ (circa 1,324..) (*)
Un veloce grafico sull'intersezione delle curve $ x^3 $ e $ x+1 $ ci fa subito vedere inoltre che $ (\beta, \gamma) \in (\mathbb{C} \setminus \mathbb{R})^2 $, ma $ \beta=\overline{\gamma} $ per cui esistono $ (c,d) \in \mathbb{R}^2 $ tali che $ d \neq 0 $, $ \beta=c+id $ e $ \gamma=c-id $.
Ricordando che $ p(\alpha)=p(\beta)=p(\gamma)=0 $ abbiamo $ p(x)=(x-\alpha)(x-\beta)(x-\gamma) $ da cui otteniamo $ \beta+\gamma=2c=-\alpha $ e $ \displaystyle \beta\gamma=c^2+d^2=\frac{1}{\alpha} $.
Abbiamo quindi ottenuto anche il valore delle altre due radici complesse, dove wlog $ \displaystyle \beta=\overline{\gamma}=-\frac{\alpha}{2}+i\sqrt{\frac{4-\alpha^3}{4\alpha}} $. (**)
Notiamo qui che $ |\beta|=|\gamma|=\sqrt{c^2+d^2}=\sqrt{\frac{1}{\alpha}}<1<\alpha $. (***)
Esistono adesso $ (x,y,z) \in \mathbb{R}^3 $ tali che $ a_n=x\alpha^n+y\beta^n+z\gamma^n, \forall n \in \mathbb{N} $.
Imponiamo i vincoli su valori "piccoli" di $ n $ e otteniamo tale tripla, infatti per quanto detto prima vale:
i) $ x\alpha^0+y\beta^0+z\gamma^0=2 $
ii) $ x\alpha^1+y\beta^1+z\gamma^1=2 $
iii) $ x\alpha^2+y\beta^2+z\gamma^2=3 $.
Che, eliminando la i), è equivalente a:
iv) $ x (\alpha-\gamma) + y (\beta-\gamma)=2-2\gamma $
v) $ x (\alpha^2-\gamma^2) + y (\beta^2-\gamma^2)=3-2\gamma^2 $.
Ma questo è un sistema di Cramer, con soluzione $ \displaystyle (x,y)=(\frac{(2-2\gamma)(\beta^2-\gamma^2)+(\gamma-\beta)(3-2\gamma^2)}{(\alpha-\gamma)(\beta^2-\gamma^2)+(\gamma-\beta)(\alpha^2-\gamma^2)}, $ $ \displaystyle \frac{(\alpha-\gamma)(\beta^2-\gamma^2)+(2\gamma-2)(\alpha^2-\gamma^2)}{(\alpha-\gamma)(\beta^2-\gamma^2)+(\gamma-\beta)(\alpha^2-\gamma^2)}) $. (****)
Bene, abbiamo finito, e possiamo concludere:
è la valida la formula $ \displaystyle a_n=x \alpha^n + y \beta^n + z\gamma^n, \forall n \in \mathbb{N}\setminus \{0,1\} $,
dove $ \alpha $ è stata definita dalla (*), $ (\beta, \gamma) $ dalla (**), e $ (x,y) $ dalla (****), con $ x+y+z=2 $.
Da notare inoltre che grazie alla (***), poichè $ 0<|\beta|=|\gamma|<|\alpha| $ , vale $ \displaystyle \lim_{n\to + \infty}{\frac{a_{n+1}}{a_n}}= \alpha $.
The only goal of science is the honor of the human spirit.
Se ti basta risolvere il caso per n=19, o al massimo per n=40-50 (tanto in un problema non metteranno mai un problema con 2009 palline), potresti fare come ho fatto io , cioè conti i modi per 3 palline, per 4, per 5, 6,7,8,9 e dovresti notare una "regolarità", cioè una successione. Trovata la regola che governa tale successione si arriva subito ad n=19
ps: lascialo stare a jordan che confonde solamente le idee
pps: naturalmente skerzo
, cioè conti i modi per 3 palline, per 4, per 5, 6,7,8,9 e dovresti notare una "regolarità", cioè una successione. Trovata la regola che governa tale successione si arriva subito ad n=19 ps: lascialo stare a jordan che confonde solamente le idee
pps: naturalmente skerzo
"Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
è difficile...
Io ho pensato di limitare i casi da 6 a 10 palline rosse,infatti se se ne hanno di più o di meno il problema nn può essere risolto, ma poi mi perdo nei calcoli...come faccio a calcolare velocemente quante serie valide ci siano con 10 palline blu e 8 rosse?ps:la matematica di jordan è fuori dalla mia comprensione
Eh questo?
Questo non va bene...
Morto...
Questo non va bene...
Morto...
Con una pallina ci sono 2 modi di disporre "in fila" questa pallina: R e B
Con 2 palline: BB-RB-BR
Con 3 palline: BBR-BRB-RBB-RBR
Con 4 palline: BBRB-BRBB-RBRB-RBBR
Con 5 palline: RBRBR-RBRBB-RBBRB-BRBRB-BRBBR-BBRBR-BBRBB
Con 6 palline: RBRBRB-RBRBBR-RBBRBR-RBBRBB-BRBRBR-BRBRBB-BRBBRB-BBRBRB-BBRBBR
Con 7 palline: RBRBRBR-RBRBRBB-RBRBBRB-RBBRBRB-RBBRBBR-BRBRBRB-BRBRBBR-BRBBRBR-BRBBRBB-BBRBRBR-BBRBRBB-BBRBBRB
Quindi:
1 pallina = 2 modi
2 palline = 3 modi
3 palline = 4 modi
4 palline = 4 modi
5 palline = 7 modi
6 palline = 9 modi
7 palline = 12 modi
Come puoi notare
9=7+2
12=9+3
Quindi chiamando con M(n) il numero di sequenze possibili con n palline, si ha che:
M(n)=M(n-1)+M(n-5)
E quindi puoi continuare la sequenza:
M(8)=16
M(9)=20
M(10)=27
M(11)=36
M(12)=48
M(13)=64
M(14)=84
M(15)=111
M(16)=147
M(17)=195
M(18)=259
M(19)=343
L'ho fatto un po' di fretta, quindi può anche essere che abbia sbagliato a contare qualcosa, cmq il metodo che dicevo era questo
Con 2 palline: BB-RB-BR
Con 3 palline: BBR-BRB-RBB-RBR
Con 4 palline: BBRB-BRBB-RBRB-RBBR
Con 5 palline: RBRBR-RBRBB-RBBRB-BRBRB-BRBBR-BBRBR-BBRBB
Con 6 palline: RBRBRB-RBRBBR-RBBRBR-RBBRBB-BRBRBR-BRBRBB-BRBBRB-BBRBRB-BBRBBR
Con 7 palline: RBRBRBR-RBRBRBB-RBRBBRB-RBBRBRB-RBBRBBR-BRBRBRB-BRBRBBR-BRBBRBR-BRBBRBB-BBRBRBR-BBRBRBB-BBRBBRB
Quindi:
1 pallina = 2 modi
2 palline = 3 modi
3 palline = 4 modi
4 palline = 4 modi
5 palline = 7 modi
6 palline = 9 modi
7 palline = 12 modi
Come puoi notare
9=7+2
12=9+3
Quindi chiamando con M(n) il numero di sequenze possibili con n palline, si ha che:
M(n)=M(n-1)+M(n-5)
E quindi puoi continuare la sequenza:
M(8)=16
M(9)=20
M(10)=27
M(11)=36
M(12)=48
M(13)=64
M(14)=84
M(15)=111
M(16)=147
M(17)=195
M(18)=259
M(19)=343
L'ho fatto un po' di fretta, quindi può anche essere che abbia sbagliato a contare qualcosa, cmq il metodo che dicevo era questo
"Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
AL 99,99999999999%Rosinaldo ha scritto:ma sei sicuro che una ricorsione di questo tipo vada bene?
ps: ripeto che i conti li ho fatti di fretta, quindi avrei potuto anche sbagliare a contare qualcosa, ma la ricorsione si può fare!!!
"Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
Uhm, e perché non "come puoi notare, 9=2*3+3, 12=3*3+3, quindi M(n)=3*M(n-5)+3"?iademarco ha scritto: 1 pallina = 2 modi
2 palline = 3 modi
3 palline = 4 modi
4 palline = 4 modi
5 palline = 7 modi
6 palline = 9 modi
7 palline = 12 modi
Come puoi notare
9=7+2
12=9+3
Quindi chiamando con M(n) il numero di sequenze possibili con n palline, si ha che:
M(n)=M(n-1)+M(n-5)
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
non faccio M(n)=3*M(n-5)+3 perchè...si perchè...proprio perchè...fph ha scritto:Uhm, e perché non "come puoi notare, 9=2*3+3, 12=3*3+3, quindi M(n)=3*M(n-5)+3"?iademarco ha scritto: 1 pallina = 2 modi
2 palline = 3 modi
3 palline = 4 modi
4 palline = 4 modi
5 palline = 7 modi
6 palline = 9 modi
7 palline = 12 modi
Come puoi notare
9=7+2
12=9+3
Quindi chiamando con M(n) il numero di sequenze possibili con n palline, si ha che:
M(n)=M(n-1)+M(n-5)
ok conto anche i modi per 8 palline
MA GUARDA UN PO' COSA MI COSTRINGI A FARE
RBRBRBRB-RBRBRBBR-RBRBBRBR-RBRBBRBB-RBBRBRBR-RBBRBRBB-RBBRBBRB-BRBRBRBR-BRBRBRBB-BRBRBBRB-BRBBRBRB-BRBBRBBR-BBRBRBRB-BBRBRBBR-BBRBBRBR-BBRBBRBB
Con 8 palline = 16 modi
Con questo credo non ci dovrebbero essere più dubbi
@fph: questo problema mi ha fatto dannare perchè non sono riuscito a farlo nello stage che hai fatto qui a campobasso durante la gara, e a fine gara non avevo il coraggio di chiederti come si risolvesse
, dato che già altri ti avevano trattenuto abbastanza. Quindi un modo per farlo lo dovevo pur trovare no?! A costo di inventarmi regolarità che non ci sono "Il lemma fondamentale: se vi danno un esercizio è perchè potete farlo; se potete farlo è perchè è proprio facile; se è proprio facile è perchè servono delle cose che sapete; le cose che sapete sono pochissime, quindi avete da cercare in un insieme piccolissimo di cose" Michele Barsanti
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
[quote="julio14"]
jordan è in realtà l'origine e il fine di tutti i mali in [tex]\mathbb{N}[/tex][/quote]
Purtroppo questo è un problema un po' di "tecnica", ci sono un paio di cose che sono facili se uno le ha già viste ma è difficile inventarsi da solo.iademarco ha scritto:@fph: questo problema mi ha fatto dannare perchè non sono riuscito a farlo nello stage che hai fatto qui a campobasso durante la gara, e a fine gara non avevo il coraggio di chiederti come si risolvesse
La strada collaudata è quella che ha scritto Jordan (forse in modo un po' "tecnico" a sua volta
).L'idea è quella di contare i possibili "finali": per esempio, puoi chiamare
a_n = numero di sequenze "buone" lunghe n palline che finiscono con R
b_n = numero di sequenze "buone" lunghe n palline che finiscono con RB
c_n = numero di sequenze "buone" lunghe n palline che finiscono con RBB
e vedere che si combinano bene: per esempio,
a_{n+1}=b_n+c_n.
b_{n+1}=... (*)
c_{n+1}=...
Perché scelgo proprio quei tre "finali"? Perché sono quelli che hanno "abbastanza informazioni" da permettermi di scrivere facilmente delle equazioni come le (*) che danno qualcosa_{n+1} in funzione di qualcosa_n. Detto in altro modo, perché sono quelli che fanno funzionare quest'ultimo passaggio.
Poi c'è da manipolare un po' le espressioni per arrivare a qualcosa in una variabile sola, per esempio
a_{n+1}=a_{n-1}+a_{n-2} (**)
e infine c'è un po' di teoria da studiare che spiega come trovare una formula chiusa per le successioni del tipo (**) -- la trovi per esempio sulle schede di Gobbino, "successioni per ricorrenza lineari".
Prova per esercizio a scrivertelo, guardare la teoria e vedere se torna tutto, anche confrontando con quello che ha detto Jordan (che è la stessa cosa detta con più paroloni). Vedo per esempio che i tuoi primi casi e la sua formula generale non tornano, quindi uno di voi due ha sbagliato qualche conto.
Altro esercizio uguale a questo "da allenamento": ho una pulce che salta sui vertici di un quadrato ABCD, al tempo t=0 sta in A, e al tempo t+1 salta in uno a caso dei due vertici adiacenti a quello in cui si trova al tempo t. Qual è la probabilità che sia nel vertice A al tempo t=2009?
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]