Cesentatico 1989 problema n°5

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
arturoberto
Messaggi: 3
Iscritto il: 09 feb 2009, 13:30

Cesentatico 1989 problema n°5

Messaggio da arturoberto » 12 feb 2009, 19:03

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
Arturoberto

spiglerg
Messaggi: 94
Iscritto il: 01 giu 2008, 21:05
Località: Roma
Contatta:

Messaggio da spiglerg » 13 feb 2009, 19:30

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.

arturoberto
Messaggi: 3
Iscritto il: 09 feb 2009, 13:30

Messaggio da arturoberto » 14 feb 2009, 12:48

Grazie Spiglerg.

Ciao
Arturo
Arturoberto

marcuz
Messaggi: 70
Iscritto il: 26 feb 2007, 21:54
Località: Pisa
Contatta:

Messaggio da marcuz » 14 feb 2009, 22:46

@spiglerg: come hai fatto a trovare la forma chiusa di $ p(n) $?
Nessun uomo è un'isola (J. Donne)

carlop
Messaggi: 13
Iscritto il: 16 gen 2008, 06:45
Località: Pisa

Messaggio da carlop » 15 feb 2009, 12:27

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
Ultima modifica di carlop il 15 feb 2009, 22:18, modificato 1 volta in totale.

spiglerg
Messaggi: 94
Iscritto il: 01 giu 2008, 21:05
Località: Roma
Contatta:

Messaggio da spiglerg » 15 feb 2009, 13:17

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

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 15 feb 2009, 13:25

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.

spiglerg
Messaggi: 94
Iscritto il: 01 giu 2008, 21:05
Località: Roma
Contatta:

Messaggio da spiglerg » 15 feb 2009, 13:38

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. :)

marcuz
Messaggi: 70
Iscritto il: 26 feb 2007, 21:54
Località: Pisa
Contatta:

Messaggio da marcuz » 15 feb 2009, 20:40

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 :)
Nessun uomo è un'isola (J. Donne)

Rispondi