Straordinario Panurgo!!!!!!
Dammi il tempo di leggermi con (molta) calma la dimostrazione
e poì inserirò i miei commenti alla soluzione.
Sancho Panza
Nota per Bruno
La tua semplificazione della formula risolutiva è ottima
Questo forum è una sezione del PORTALE DI BASE CINQUE
-
Sancho Panza
- Livello 4
- Messaggi: 151
- Iscritto il: gio ott 12, 2006 9:01 pm
Mi sono letto la soluzione di Panurgo e sono rimasto stupito di come riesca ad essere rigoroso e semplice allo stesso tempo. Si riesce a seguire tutta la dimostrazione con facilità ed è facile verificare che la soluzione è esatta.
Vi risparmio quindi di mostrarvi quella che era la mia soluzione (assai più approssimativa e meno facile da seguire.) Mi limito a mostrarvi il calcolo del limite per n che tende ad infinito per far notare una cosa interessante.
Guardate quanti passaggi ho dovuto fare per un conto che Panurgo ha risolto con un semplice integrale:
Lemma 1
Se un intervallo viene diviso casualmente in tre parti, la probabilita che il primo segmento sia il più lungo è uguale a $\frac{1}{3}$
Lemma 2
Se un intervallo [1..N] viene diviso casualmente in tre parti, la probabilita che i due valori separatori siano entrambi maggiori di $\frac{N}{2}$ o entrambi minori di $\frac{N}{2}$ è uguale a $\frac{1}{2}$
Teorema 1
Se entrambi i valori separatori sono maggiori di $\frac{N}{2}$ o sono entrambi minori di $\frac{N}{2}$ è uguale a $\frac{1}{2}$ allora la probabilità che il terzo valore cada nell'intervallo più lungo è uguale a $\frac{2}{3}$
Dimostrazione del Teorema 1
Infatti l'intervallo più lungo è mediamente la somma di due termini:
il primo termine è $\frac{N}{2}$ (in quanto i due valori separatori sono entrambi dalla stessa parte rispetto a $\frac{N}{2}$)
il secondo termine è la lunghezza media della distanza tra$\frac{N}{2}$ ed il valore separatore più vicino.
Questa distanza è (per il Lemma 1) uguale a $\frac{N}{2}*\frac{1}{3}$
Lunghezza totale = $\frac{N}{2} + \frac{N}{6} = \frac{2}{3}*N$
Passaggio intermedio
Chiamo X la lunghezza media dell'intervallo più lungo.
Dimostrazione
Se i primi due valori, sono uno maggiore e l'altro minore di $\frac{N}{2}$, la lunghezza media dell'intervallo più lungo è la media tra la lunghezza media dell'intervallo intermedio e la media delle lunghezze medie degli intervalli più lunghi degli altri due intervalli.
In questa situazione, avendo uno dei valori separatori un valore casuale uniforme tra 0 e $\frac{N}{2}$ e l'altro valore separatore un valore casuale uniforme tra $\frac{N}{2}$ e N si ha che la lunghezza media dell'intervallo intermedio è $\frac{N}{2}$
Il primo e il terzo intervallo se sono il più lungo sono lunghi X
Calcolo la media: $\frac{{\left( {X} \right) + \frac{N}{2}}}{2} = \frac{{2X + N}}{4}$
Quindi:
$X = \frac{{\frac{2}{3}N + \frac{{2X + N}}{4}}}{2} = \frac{N}{3} + \frac{{2X + N}}{8} = \frac{{8N + 6X + 3N}}{{24}}$
$24X = 11N + 6X$
$18X = 11N$
$X = \frac{{11}}{{18}}N$
Lo so che la dimostrazione di Panurgo è molto molto meglio,
ho voluto mettere anche questa mia dimostrazione per far notare la seguente cosa:
$X = \frac{1}{3}*\frac{1}{2} + \frac{1}{3}*\left( {1 + \frac{1}{3}} \right) = \frac{1}{3}*\left( {\frac{1}{2} + 1 + \frac{1}{3}} \right) = \frac{1}{M}*\sum\limits_{i = 1}^M {\frac{1}{i}}$
dove M è il numero di biglie numerate estratte dalla scatola.
Risulta abbastanza facile dimostrare che questa formula ha valore generale.
(Vale sempre, anche quando M è diverso da 3)
Vi risparmio quindi di mostrarvi quella che era la mia soluzione (assai più approssimativa e meno facile da seguire.) Mi limito a mostrarvi il calcolo del limite per n che tende ad infinito per far notare una cosa interessante.
Guardate quanti passaggi ho dovuto fare per un conto che Panurgo ha risolto con un semplice integrale:
Lemma 1
Se un intervallo viene diviso casualmente in tre parti, la probabilita che il primo segmento sia il più lungo è uguale a $\frac{1}{3}$
Lemma 2
Se un intervallo [1..N] viene diviso casualmente in tre parti, la probabilita che i due valori separatori siano entrambi maggiori di $\frac{N}{2}$ o entrambi minori di $\frac{N}{2}$ è uguale a $\frac{1}{2}$
Teorema 1
Se entrambi i valori separatori sono maggiori di $\frac{N}{2}$ o sono entrambi minori di $\frac{N}{2}$ è uguale a $\frac{1}{2}$ allora la probabilità che il terzo valore cada nell'intervallo più lungo è uguale a $\frac{2}{3}$
Dimostrazione del Teorema 1
Infatti l'intervallo più lungo è mediamente la somma di due termini:
il primo termine è $\frac{N}{2}$ (in quanto i due valori separatori sono entrambi dalla stessa parte rispetto a $\frac{N}{2}$)
il secondo termine è la lunghezza media della distanza tra$\frac{N}{2}$ ed il valore separatore più vicino.
Questa distanza è (per il Lemma 1) uguale a $\frac{N}{2}*\frac{1}{3}$
Lunghezza totale = $\frac{N}{2} + \frac{N}{6} = \frac{2}{3}*N$
Passaggio intermedio
Chiamo X la lunghezza media dell'intervallo più lungo.
Dimostrazione
Se i primi due valori, sono uno maggiore e l'altro minore di $\frac{N}{2}$, la lunghezza media dell'intervallo più lungo è la media tra la lunghezza media dell'intervallo intermedio e la media delle lunghezze medie degli intervalli più lunghi degli altri due intervalli.
In questa situazione, avendo uno dei valori separatori un valore casuale uniforme tra 0 e $\frac{N}{2}$ e l'altro valore separatore un valore casuale uniforme tra $\frac{N}{2}$ e N si ha che la lunghezza media dell'intervallo intermedio è $\frac{N}{2}$
Il primo e il terzo intervallo se sono il più lungo sono lunghi X
Calcolo la media: $\frac{{\left( {X} \right) + \frac{N}{2}}}{2} = \frac{{2X + N}}{4}$
Quindi:
$X = \frac{{\frac{2}{3}N + \frac{{2X + N}}{4}}}{2} = \frac{N}{3} + \frac{{2X + N}}{8} = \frac{{8N + 6X + 3N}}{{24}}$
$24X = 11N + 6X$
$18X = 11N$
$X = \frac{{11}}{{18}}N$
Lo so che la dimostrazione di Panurgo è molto molto meglio,
ho voluto mettere anche questa mia dimostrazione per far notare la seguente cosa:
$X = \frac{1}{3}*\frac{1}{2} + \frac{1}{3}*\left( {1 + \frac{1}{3}} \right) = \frac{1}{3}*\left( {\frac{1}{2} + 1 + \frac{1}{3}} \right) = \frac{1}{M}*\sum\limits_{i = 1}^M {\frac{1}{i}}$
dove M è il numero di biglie numerate estratte dalla scatola.
Risulta abbastanza facile dimostrare che questa formula ha valore generale.
(Vale sempre, anche quando M è diverso da 3)
-
Sancho Panza
- Livello 4
- Messaggi: 151
- Iscritto il: gio ott 12, 2006 9:01 pm
Ok! 
P.S.: Per essere rigorosi, questo si chiama "assegnare la probabilità in base al principio di indifferenza"
P.S.: Per essere rigorosi, questo si chiama "assegnare la probabilità in base al principio di indifferenza"
il panurgo
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"
Peccato, Sancho.Sancho Panza ha scritto:Vi risparmio quindi di mostrarvi quella che era la mia soluzione...
Anch'io ho letto, seguito e apprezzato la
dimostrazione di Guido (ho finito proprio
ieri sera), di cui peraltro sono un fan.
Questo però non toglie che possano esserci
altri approcci meritevoli, forse (forse) meno
rigorosi, come dici tu, ma altrettanto
istruttivi.
Sarà perché, secondo me, nessuna risoluzione
(nemmeno le migliori), può scrivere "detto
tutto" su un problema interessante; sarà
perché da un ragionamento, da un discorso
dimostrativo, di qualunque foggia sia, imparo
sempre qualche cosa... per tutto questo,
Sancho, avrei letto volentieri pure il tuo
metodo.
Ma non ti voglio condizionare.
...è soltanto meno modulata, quindi più umana.Sancho Panza ha scritto: La tua semplificazione della formula risolutiva è ottima
Passare per forza per il mod 6 rende tutto più
complicato (volendo, poi, potremmo togliere
anche quel mod 2, ma vabbe'...).
Buona giornata!
Bruno