Per questioni di vita o di morte ho necessità di risolvere il problema in oggetto. Avviso che nel topic di questo sito dedicato alle soluzioni delle olimpiadi della matematica, non si trova, i link non funzionano, quindi inutile darmi il consiglio di andare lì.
Riporto il testo per chi voglia compiere un'opera meritoria:
Se esce “testa” ottengo un gettone, se esce “croce” ne ottengo due. Vincerò il gioco se arriverò (non importa dopo quanti lanci) a possedere esattamente 100 gettoni. Dire se la probabilità di vincere è maggiore, uguale o minore di 2/3.
Grazie e saluti a tutti
Arturo
Cesentatico 1989 problema n°5
-
arturoberto
- Messaggi: 3
- Iscritto il: 09 feb 2009, 13:30
Cesentatico 1989 problema n°5
Arturoberto
Allora, per prima cosa cerco di determinare una formula chiusa che mi permetta di calcolare p(n).
Faccio a mano i casi per n=1,2,3, che sono p(1)=1/2, p(2)=3/4 e p(3)=5/8.
Effettivamente, per poter ottenere n seguendo le regole dell'ipotesi devi per forza arrivare ad avere (n-1) (con probabilita' 1/2), oppure (n-2) (ancora con probabilita' 1/2). Di nuovo, in modo ricorsivo, devo calcolare le probabilita' di avere (n-1) e (n-2).
Posso scrivere la relazione ricorsiva
$ $$ p(n) = \frac{1}{2} p(n-1) + \frac{1}{2} p(n-2) $$ $
Ora mi calcolo la formula chiusa, che risulta essere
$ $$ p(n) = \frac{1}{3} \frac{1}{ (-2)^n } + \frac{2}{3} $$ $
ed infine vedo p(100)
$ p(100) = \frac{1}{3} \frac{1}{2^{100} } + \frac{2}{3} $
che non ho bisogno di calcolare, poiche' e' chiaramente maggiore di 2/3.
Faccio a mano i casi per n=1,2,3, che sono p(1)=1/2, p(2)=3/4 e p(3)=5/8.
Effettivamente, per poter ottenere n seguendo le regole dell'ipotesi devi per forza arrivare ad avere (n-1) (con probabilita' 1/2), oppure (n-2) (ancora con probabilita' 1/2). Di nuovo, in modo ricorsivo, devo calcolare le probabilita' di avere (n-1) e (n-2).
Posso scrivere la relazione ricorsiva
$ $$ p(n) = \frac{1}{2} p(n-1) + \frac{1}{2} p(n-2) $$ $
Ora mi calcolo la formula chiusa, che risulta essere
$ $$ p(n) = \frac{1}{3} \frac{1}{ (-2)^n } + \frac{2}{3} $$ $
ed infine vedo p(100)
$ p(100) = \frac{1}{3} \frac{1}{2^{100} } + \frac{2}{3} $
che non ho bisogno di calcolare, poiche' e' chiaramente maggiore di 2/3.
-
arturoberto
- Messaggi: 3
- Iscritto il: 09 feb 2009, 13:30
In questo topic si risponde anche alla domanda: "Come trovare una formula chiusa per una ricorrenza lineare ?"
Salta pure i primi post che parlano di un problema particolare, dal secondo post di Boll in poi si tenta di spiegare come si ricava la formula di Binet, cioè la formula chiusa per il calcolo dei numeri di fibonacci. A parte modificare le costanti, lo stesso ragionamento vale per tutte le ricorrenze lineari.
Se hai dubbi chiedi pure..
EDIT: viewtopic.php?t=3682&highlight=ricorrenze, avevo dimenticato di scrivere la cosa più importante..... scusate
Salta pure i primi post che parlano di un problema particolare, dal secondo post di Boll in poi si tenta di spiegare come si ricava la formula di Binet, cioè la formula chiusa per il calcolo dei numeri di fibonacci. A parte modificare le costanti, lo stesso ragionamento vale per tutte le ricorrenze lineari.
Se hai dubbi chiedi pure..
EDIT: viewtopic.php?t=3682&highlight=ricorrenze, avevo dimenticato di scrivere la cosa più importante..... scusate
Ultima modifica di carlop il 15 feb 2009, 22:18, modificato 1 volta in totale.
Per le successioni per ricorrenza lineari dipendenti da 2 termini precedenti $ a_n=\alpha a_{n-1} + \beta a_{n-2} $ devi per prima cosa ricavare le radici $ x_1, x_2 $ di $ x^2 - \alpha x - \beta $. Se le radici sono distinte (come in questo caso) la formula chiusa e' del tipo $ a_n = k_1 x_1^n + k_2 x_2^n $, e puoi calcolare $ k_1, k_2 $ imponendo che la relazione sia verificata per $ n_0, n_1 $.
Se le radici non sono distinte la formula diventa $ a_n = k_1 x^n + k_2 n x^n $.
Se le radici non sono distinte la formula diventa $ a_n = k_1 x^n + k_2 n x^n $.
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
In questo caso non è affatto necessario usare la teoria generale delle serie generatrici, basta un disegnino per accorgersi di come funzionano le cose. Il fatto stesso che il testo fornisca quel 2/3 è già un grosso aiuto.
Si parte con 2 "estremi", p(0)=1=A e p(1)=1/2=B, ed un "punto fisso" P=2/3. Ad ogni passo della successione, i 2 estremi vengono trasformati secondo un'omotetia di ragione -1/2: A'=B, e B'=(A+B)/2. Il centro di tale omotetia è proprio il punto fisso P=2/3. Osservato questo, è evidente come p(n) oscilli attorno a 2/3, ed i termini pari siano tutti maggiori di 2/3.
Si parte con 2 "estremi", p(0)=1=A e p(1)=1/2=B, ed un "punto fisso" P=2/3. Ad ogni passo della successione, i 2 estremi vengono trasformati secondo un'omotetia di ragione -1/2: A'=B, e B'=(A+B)/2. Il centro di tale omotetia è proprio il punto fisso P=2/3. Osservato questo, è evidente come p(n) oscilli attorno a 2/3, ed i termini pari siano tutti maggiori di 2/3.
Interessante come metodo.Tibor Gallai ha scritto:In questo caso non è affatto necessario usare la teoria generale delle serie generatrici, basta un disegnino per accorgersi di come funzionano le cose. Il fatto stesso che il testo fornisca quel 2/3 è già un grosso aiuto.
Si parte con 2 "estremi", p(0)=1=A e p(1)=1/2=B, ed un "punto fisso" P=2/3. Ad ogni passo della successione, i 2 estremi vengono trasformati secondo un'omotetia di ragione -1/2: A'=B, e B'=(A+B)/2. Il centro di tale omotetia è proprio il punto fisso P=2/3. Osservato questo, è evidente come p(n) oscilli attorno a 2/3, ed i termini pari siano tutti maggiori di 2/3.
