OliForum Matematico

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

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.

Grazie Spiglerg.

Ciao
Arturo

@spiglerg: come hai fatto a trovare la forma chiusa di $ p(n) $?

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

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 $.

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.

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.

Interessante come metodo.

Grazie a tutti per le risposte, avevo trovato la formula per ricorrenza e "mi puzzava" di fibonacci ma non sapevo come arrivare alla formula chiusa.

@carlop: mi sa che hai dimenticato di inserire il link al post di cui parli