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.
cesenatico 1989
cesenatico 1989
Appassionatamente BTA 197!
Per arrivare ad n gettoni devo:
1)Arrivare ad n-2 gettoni e fare croce.
2)Arrivare ad n-1 gettoni e fare testa.
Quindi sia $ P_n $ la probabilità di possedere esattamente n gettoni.
Avrò che $ P_n= \displaystyle \frac{P_{n-1}+P_{n-2}}{2} $
Dimostriamo ora che $ P_n = \displaystyle \frac{2}{3} + \frac{1}{3}(-\frac{1}{2})^n $
Per avere un gettone devo fare testa al primo lancio quindi
$ P_1=\displaystyle \frac{1}{2} $
Per avere due gettoni devo fare o croce al primo lancio o due teste di fila quindi:
$ P_2=\displaystyle \frac{3}{4} $
Diciamo ora che la formula vale fino ad un certo n:
Allora
$ P_{n+1}= \displaystyle \frac{P_{n}+P_{n-1}}{2} $
$ P_{n+1}= \displaystyle (\frac{1}{2})(\displaystyle \frac{2}{3} + \frac{1}{3}(-\frac{1}{2})^n + \frac{2}{3} + \frac{1}{3}(-\frac{1}{2})^{n-1}) $
$ P_{n+1}= \displaystyle (\frac{1}{2})(-\frac{1}{2})^{n-1}(\frac{1}{2})+\frac{2}{3} $
da cui tenendo conto che $ (-\frac{1}{2})^2=(\frac{1}{2})^2 $
si arriva alla formula cercata.
Ora nella formula noto che $ (-\frac{1}{2})^n $ è minore di 0 per n dispari e maggiore di 0 per n pari, quindi la probabilità sarà maggiore di 2/3 per un numero di gettoni pari e minore per un numero di gettoni dispari (e credo tenderà a 2/3 per n che va ad infinito, ma a nessuno importa). Quindi per n=100 sarà maggiore di 2/3.
1)Arrivare ad n-2 gettoni e fare croce.
2)Arrivare ad n-1 gettoni e fare testa.
Quindi sia $ P_n $ la probabilità di possedere esattamente n gettoni.
Avrò che $ P_n= \displaystyle \frac{P_{n-1}+P_{n-2}}{2} $
Dimostriamo ora che $ P_n = \displaystyle \frac{2}{3} + \frac{1}{3}(-\frac{1}{2})^n $
Per avere un gettone devo fare testa al primo lancio quindi
$ P_1=\displaystyle \frac{1}{2} $
Per avere due gettoni devo fare o croce al primo lancio o due teste di fila quindi:
$ P_2=\displaystyle \frac{3}{4} $
Diciamo ora che la formula vale fino ad un certo n:
Allora
$ P_{n+1}= \displaystyle \frac{P_{n}+P_{n-1}}{2} $
$ P_{n+1}= \displaystyle (\frac{1}{2})(\displaystyle \frac{2}{3} + \frac{1}{3}(-\frac{1}{2})^n + \frac{2}{3} + \frac{1}{3}(-\frac{1}{2})^{n-1}) $
$ P_{n+1}= \displaystyle (\frac{1}{2})(-\frac{1}{2})^{n-1}(\frac{1}{2})+\frac{2}{3} $
da cui tenendo conto che $ (-\frac{1}{2})^2=(\frac{1}{2})^2 $
si arriva alla formula cercata.
Ora nella formula noto che $ (-\frac{1}{2})^n $ è minore di 0 per n dispari e maggiore di 0 per n pari, quindi la probabilità sarà maggiore di 2/3 per un numero di gettoni pari e minore per un numero di gettoni dispari (e credo tenderà a 2/3 per n che va ad infinito, ma a nessuno importa). Quindi per n=100 sarà maggiore di 2/3.
Per arrivare a quella formula ha usato il metodo per risolvere le sucessioni per ricorsione lineari (o differenze finite, è uguale?). Poi una volta trovata era sufficiente scrivere la dimostrazione per induzione.Bake ha scritto:Chiedo scusa per aver resuscitato un post di chissà quale epoca, ma è da un pò che mi sbatto su sto problema.
L'inizio è piuttosto chiaro, facile da intuire, ma come arrivi alla formula?O_o ho letto un altra soluzione che usa le successioni lineari, ma non c'è una soluzione un pò più "olimpica"?
Un'altro metodo è quello che Tibor scrive qua: viewtopic.php?t=12425
mi sembrano entrambe soluzioni abbastanza elaborate O_o è normale che una soluzione di cesenatico richieda necessariamente tali conoscenze? Di certo non ho mai studiato a scuola come risolvere successioni per ricorsione lineari.
La soluzione di Tibor o non la capisco bene, o mi manca di rigorosità O_o
La soluzione di Tibor o non la capisco bene, o mi manca di rigorosità O_o
Nonostante sembri strano anche a me è comunque un esercizio 5, forse c'è qualche altra soluzione... bho. Comunque tieni conto che le sucessioni per ricorrenza lineari compaiono nelle schede olimpiche (è quindi un argomento olimpico?) e io le ho viste per la prima volta in uno stage locale (olimpico) spiegate da Francesco VenezianoBake ha scritto:mi sembrano entrambe soluzioni abbastanza elaborate O_o è normale che una soluzione di cesenatico richieda necessariamente tali conoscenze? Di certo non ho mai studiato a scuola come risolvere successioni per ricorsione lineari.
La soluzione di Tibor o non la capisco bene, o mi manca di rigorosità O_o
-
FrancescoVeneziano
- Site Admin
- Messaggi: 606
- Iscritto il: 01 gen 1970, 01:00
- Località: Genova
- Contatta:
Per adesso tralasciamo che il problema chiede solo di determinare se P_100 è minore, maggiore o uguale a 2/3, e supponiamo invece che il problema sia di calcolare P_100.
La soluzione di Alex_89 è impeccabile e perfettamente olimpica. Congettura la formula e la dimostra per induzione; tutto molto semplice ed elementare, tranne una cosa: da dove viene la formula? Come ha fatto a trovarla?
Questa formula è abbastanza semplice, e secondo me è possibile trovarla per tentativi calcolando a mano un po' di valori iniziali.
C'è un'altra via, più difficile da un punto di vista tecnico ma per altri versi più facile perché non richiede nessuna intuizione, andare per tentativi o indovinare magicamente la formula giusta, che è il metodo generale di cui si parla nei post linkati da Zorro.
Questo metodo, per quanto elementare, è in effetti piuttosto elaborato e dimostra direttamente la formula generale trovandola durante il procedimento. Naturalmente la cosa migliore da fare in gara sarebbe conoscere il metodo generale, usarlo in brutta per trovare la formula corretta, e dimostrare in bella la formula corretta per induzione, che è più semplice da capire e più veloce da scrivere.
In breve: per risolvere il problema non è necessaria la conoscenza della teoria generale, ma certo aiuta.
Andando al problema specifico, che chiede se P_100 è maggiore, minore o uguale a 2/3, questo è ancora più semplice. Chi è dotato di maggior intuizione geometrica può seguire il ragionamento di Tibor Gallai, ma io affrontando il problema da olimpionico, prima di conoscere la teoria generale, avrei ragionato così:
Definisco Q_n=P_n - 2/3
usando la ricorrenza trovata sui P_n trovo che $ Q_n=\frac{Q_{n-1}+Q_{n-2}}{2} $ e adesso mi interessa il segno di Q_100. Calcolo a mano i primi valori, che sono 1/3, -1/6, 1/12, -1/24, 1/48...
Adesso mi accorgo che $ Q_n=\frac{1}{3}\left(-\frac{1}{2}\right)^n $ e lo dimostro facilmente per induzione.
Anche qui ho dovuto accorgermi di una formula dai primi casi, ma innegabilmente questa è più facile da indovinare di quella per P_n; l'idea di sottrarre 2/3 alla successione di partenza mi è stata suggerita dal testo.
Difficilmente troverete un problema a Cesenatico la cui soluzione ufficiale utilizza la formula generale per le successioni per ricorrenza, ma naturalmente più cose avete studiato a casa meno fatica dovrete fare durante la gara. Questo problema è un problema medio per gli standard attuali senza sapere la teoria generale, e diventa decisamente facile sapendola.
La soluzione di Alex_89 è impeccabile e perfettamente olimpica. Congettura la formula e la dimostra per induzione; tutto molto semplice ed elementare, tranne una cosa: da dove viene la formula? Come ha fatto a trovarla?
Questa formula è abbastanza semplice, e secondo me è possibile trovarla per tentativi calcolando a mano un po' di valori iniziali.
C'è un'altra via, più difficile da un punto di vista tecnico ma per altri versi più facile perché non richiede nessuna intuizione, andare per tentativi o indovinare magicamente la formula giusta, che è il metodo generale di cui si parla nei post linkati da Zorro.
Questo metodo, per quanto elementare, è in effetti piuttosto elaborato e dimostra direttamente la formula generale trovandola durante il procedimento. Naturalmente la cosa migliore da fare in gara sarebbe conoscere il metodo generale, usarlo in brutta per trovare la formula corretta, e dimostrare in bella la formula corretta per induzione, che è più semplice da capire e più veloce da scrivere.
In breve: per risolvere il problema non è necessaria la conoscenza della teoria generale, ma certo aiuta.
Andando al problema specifico, che chiede se P_100 è maggiore, minore o uguale a 2/3, questo è ancora più semplice. Chi è dotato di maggior intuizione geometrica può seguire il ragionamento di Tibor Gallai, ma io affrontando il problema da olimpionico, prima di conoscere la teoria generale, avrei ragionato così:
Definisco Q_n=P_n - 2/3
usando la ricorrenza trovata sui P_n trovo che $ Q_n=\frac{Q_{n-1}+Q_{n-2}}{2} $ e adesso mi interessa il segno di Q_100. Calcolo a mano i primi valori, che sono 1/3, -1/6, 1/12, -1/24, 1/48...
Adesso mi accorgo che $ Q_n=\frac{1}{3}\left(-\frac{1}{2}\right)^n $ e lo dimostro facilmente per induzione.
Anche qui ho dovuto accorgermi di una formula dai primi casi, ma innegabilmente questa è più facile da indovinare di quella per P_n; l'idea di sottrarre 2/3 alla successione di partenza mi è stata suggerita dal testo.
Difficilmente troverete un problema a Cesenatico la cui soluzione ufficiale utilizza la formula generale per le successioni per ricorrenza, ma naturalmente più cose avete studiato a casa meno fatica dovrete fare durante la gara. Questo problema è un problema medio per gli standard attuali senza sapere la teoria generale, e diventa decisamente facile sapendola.
Wir müssen wissen. Wir werden wissen.
Chiarissimo grazie.FrancescoVeneziano ha scritto:Per adesso tralasciamo che il problema chiede solo di determinare se P_100 è minore, maggiore o uguale a 2/3, e supponiamo invece che il problema sia di calcolare P_100.
La soluzione di Alex_89 è impeccabile e perfettamente olimpica. Congettura la formula e la dimostra per induzione; tutto molto semplice ed elementare, tranne una cosa: da dove viene la formula? Come ha fatto a trovarla?
Questa formula è abbastanza semplice, e secondo me è possibile trovarla per tentativi calcolando a mano un po' di valori iniziali.
C'è un'altra via, più difficile da un punto di vista tecnico ma per altri versi più facile perché non richiede nessuna intuizione, andare per tentativi o indovinare magicamente la formula giusta, che è il metodo generale di cui si parla nei post linkati da Zorro.
Questo metodo, per quanto elementare, è in effetti piuttosto elaborato e dimostra direttamente la formula generale trovandola durante il procedimento. Naturalmente la cosa migliore da fare in gara sarebbe conoscere il metodo generale, usarlo in brutta per trovare la formula corretta, e dimostrare in bella la formula corretta per induzione, che è più semplice da capire e più veloce da scrivere.
In breve: per risolvere il problema non è necessaria la conoscenza della teoria generale, ma certo aiuta.
Andando al problema specifico, che chiede se P_100 è maggiore, minore o uguale a 2/3, questo è ancora più semplice. Chi è dotato di maggior intuizione geometrica può seguire il ragionamento di Tibor Gallai, ma io affrontando il problema da olimpionico, prima di conoscere la teoria generale, avrei ragionato così:
Definisco Q_n=P_n - 2/3
usando la ricorrenza trovata sui P_n trovo che $ Q_n=\frac{Q_{n-1}+Q_{n-2}}{2} $ e adesso mi interessa il segno di Q_100. Calcolo a mano i primi valori, che sono 1/3, -1/6, 1/12, -1/24, 1/48...
Adesso mi accorgo che $ Q_n=\frac{1}{3}\left(-\frac{1}{2}\right)^n $ e lo dimostro facilmente per induzione.
Anche qui ho dovuto accorgermi di una formula dai primi casi, ma innegabilmente questa è più facile da indovinare di quella per P_n; l'idea di sottrarre 2/3 alla successione di partenza mi è stata suggerita dal testo.
Difficilmente troverete un problema a Cesenatico la cui soluzione ufficiale utilizza la formula generale per le successioni per ricorrenza, ma naturalmente più cose avete studiato a casa meno fatica dovrete fare durante la gara. Questo problema è un problema medio per gli standard attuali senza sapere la teoria generale, e diventa decisamente facile sapendola.