Il problema dei cinque ponti
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
-
- Supervisore del sito
- Messaggi: 1720
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Il problema dei cinque ponti
Cari amici, questo problema è abbastanza semplice ma può generare osservazioni (didattiche) molto interessanti.
---
L'immagine mostra cinque ponti che collegano le rive opposte di un fiume passando attraverso due isole. Ci sono diversi modi per attraversare il fiume usando alcuni ponti.
Ieri c'è stata una tempesta così forte che ciascun ponte ha avuto il 50% di probabilità di crollare. Oggi, Aldo arriva al fiume e deve attraversarlo.
Data la disposizione dei ponti e delle isole, qual è la probabilità che Aldo sia in grado attraversare il fiume?
---
L'immagine mostra cinque ponti che collegano le rive opposte di un fiume passando attraverso due isole. Ci sono diversi modi per attraversare il fiume usando alcuni ponti.
Ieri c'è stata una tempesta così forte che ciascun ponte ha avuto il 50% di probabilità di crollare. Oggi, Aldo arriva al fiume e deve attraversarlo.
Data la disposizione dei ponti e delle isole, qual è la probabilità che Aldo sia in grado attraversare il fiume?
Pace e bene a tutti.
Gianfranco
Gianfranco
Re: Il problema dei cinque ponti
Assumiamo come al solito una distribuzione uniforme e indipendente in base al Principio di Indifferenza.
Con tale premessa ci sono sei possibilità a seconda se i ponti crollati sono $0$, $1$, $2$, $3$, $4$ o $5$; la dispsosizione dei ponti è simmetrica quindi i sei stati sono simmetrici a due a due: nessun ponte/cinque ponti, un ponte/quattro ponti, due ponti/tre ponti.
Quindi la probabilità è $\frac12$
Con tale premessa ci sono sei possibilità a seconda se i ponti crollati sono $0$, $1$, $2$, $3$, $4$ o $5$; la dispsosizione dei ponti è simmetrica quindi i sei stati sono simmetrici a due a due: nessun ponte/cinque ponti, un ponte/quattro ponti, due ponti/tre ponti.
Quindi la probabilità è $\frac12$
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"
-
- Supervisore del sito
- Messaggi: 1720
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Il problema dei cinque ponti
Ciao Panurgo, la soluzione è esatta ma dovrò meditare a lungo sull'argomentazione per esplicitare meglio tutti i passaggi.
Ho una domanda per te e per tutti gli amici.
Secondo voi, questo problema si potrebbe formulare meglio?
Infatti se IERI c'è stata una tempesta e OGGI Aldo si trova al fiume, allora la probabilità che possa attraversarlo è 0 oppure 1, a seconda dei ponti che sono effettivamente crollati.
E' un po' come lanciare una moneta e DOPO il lancio chiedere qual è la probabilità che in quel lancio sia uscita Testa.
Una formulazione più corretta potrebbe essere questa(?)
---
Purtroppo oggi si è scatenata una tempesta così forte che ciascun ponte ha il 50% di probabilità di crollare.
Data la disposizione dei ponti e delle isole, qual è la probabilità che dopo la tempesta si possa attraversare il fiume passando sui ponti rimasti agibili?
---
Ho una domanda per te e per tutti gli amici.
Secondo voi, questo problema si potrebbe formulare meglio?
Infatti se IERI c'è stata una tempesta e OGGI Aldo si trova al fiume, allora la probabilità che possa attraversarlo è 0 oppure 1, a seconda dei ponti che sono effettivamente crollati.
E' un po' come lanciare una moneta e DOPO il lancio chiedere qual è la probabilità che in quel lancio sia uscita Testa.
Una formulazione più corretta potrebbe essere questa(?)
---
Purtroppo oggi si è scatenata una tempesta così forte che ciascun ponte ha il 50% di probabilità di crollare.
Data la disposizione dei ponti e delle isole, qual è la probabilità che dopo la tempesta si possa attraversare il fiume passando sui ponti rimasti agibili?
---
Pace e bene a tutti.
Gianfranco
Gianfranco
Re: Il problema dei cinque ponti
se cade nessun ponte si passa/se cadono tutti i ponti non si passa
se cade un ponte si passa/se cadono quattro ponti non si passa
fin qui nessun problema
se cadono due ponti si passa in otto modi/se cadono tre ponti NON si passa in otto modi
la situazione è simmetrica perché la disposizionie dei ponti è simmetrica.
Per quel che riguarda la formulazione, la probabilità è epistemica non ontologica: dipende da ciò che sappiamo non da ciò che è.
Per esempio, se sapessimo che sono caduti due ponti non sapremmo ancora se si possa o no passare però, per impedire il passaggio dovrebbero essere caduti i due ponti che collegano le isole ad una stessa riva del fiume quindi ci sono due modi (sui dieci possibili) che impediscono il passaggio. Assegnando una probilitò di $\frac12$ alla caduta di ogni singolo ponte, sapendo che ne sono caduti due la probabilità di passare è $\frac45$.
Se sapessimo che sono caduti tre ponti avremmo una probabilità di $\frac15$ di passare perché stavolta dovrebbero essere rimasti in piedi i due ponti che colleganouna delle due isole alle due sponde (due modi su dieci).
Questo discorso si riferisce alle informazioni che abbiamo: potrebbe riferirsi altrettanto bene al passato come al futuro, oppure ad un mondo ipotetico...
se cade un ponte si passa/se cadono quattro ponti non si passa
fin qui nessun problema
se cadono due ponti si passa in otto modi/se cadono tre ponti NON si passa in otto modi
la situazione è simmetrica perché la disposizionie dei ponti è simmetrica.
Per quel che riguarda la formulazione, la probabilità è epistemica non ontologica: dipende da ciò che sappiamo non da ciò che è.
Per esempio, se sapessimo che sono caduti due ponti non sapremmo ancora se si possa o no passare però, per impedire il passaggio dovrebbero essere caduti i due ponti che collegano le isole ad una stessa riva del fiume quindi ci sono due modi (sui dieci possibili) che impediscono il passaggio. Assegnando una probilitò di $\frac12$ alla caduta di ogni singolo ponte, sapendo che ne sono caduti due la probabilità di passare è $\frac45$.
Se sapessimo che sono caduti tre ponti avremmo una probabilità di $\frac15$ di passare perché stavolta dovrebbero essere rimasti in piedi i due ponti che colleganouna delle due isole alle due sponde (due modi su dieci).
Questo discorso si riferisce alle informazioni che abbiamo: potrebbe riferirsi altrettanto bene al passato come al futuro, oppure ad un mondo ipotetico...
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"
Re: Il problema dei cinque ponti
Questo è quello che intendo per simmetria: va da sé che serve anche la simmetria tra probabilità di crollo e di non crollo (ma questa è assicurata dal 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"
Re: Il problema dei cinque ponti
Leggendo il testo la prima volta avevo immaginato che il 50% fosse riferito alla possibilità che il ponte crollasse nel momento del passaggio di Aldo
Questo però potrebbe essere lo spunto per un problema leggermente diverso: Un ragno cieco e grasso deve andare da A a B spostandosi sui "5 ponti" costituiti da fili di ragnatela illustrati nella figura.
Essendo cieco, da ogni punto ("isola") prenderà a caso uno dei ponti (eventualmente anche quello da cui era arrivato).
Essendo grasso, ogni volta che passa su uno dei ponti ha il 50% di probabilità che il filo si spezzi mandandolo in pasto alle lucertole sottostanti (e il fatto che gli sia andata bene al primo passaggio non cambia la probabilità la volta dopo!).
Che probabilità ha di arrivare sano e salvo alla meta?
Questo però potrebbe essere lo spunto per un problema leggermente diverso: Un ragno cieco e grasso deve andare da A a B spostandosi sui "5 ponti" costituiti da fili di ragnatela illustrati nella figura.
Essendo cieco, da ogni punto ("isola") prenderà a caso uno dei ponti (eventualmente anche quello da cui era arrivato).
Essendo grasso, ogni volta che passa su uno dei ponti ha il 50% di probabilità che il filo si spezzi mandandolo in pasto alle lucertole sottostanti (e il fatto che gli sia andata bene al primo passaggio non cambia la probabilità la volta dopo!).
Che probabilità ha di arrivare sano e salvo alla meta?
Franco
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
-
- Supervisore del sito
- Messaggi: 1720
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Il problema dei cinque ponti
Non so usare bene le catene di Markov ma ho trovato un simulatore didattico online che ha questo modello in cui si possono modificare SOLO i valori della matrice 5x5.
Ho cercato di adattarlo al problema del ragno:
a) A=stato 1, B=stato 4, cade=stato 0
b) se cade, finisce nello stato 0 e ricomincia dallo stato 1
c) se finisce nello stato 4 ricomincia da 1
con il risultato illustrato nella figura. Si nota che il ragno finisce nello stato 0 nel 32% dei casi e nello stato 4 nel 4% dei casi.
Quindi la probabilità che arrivi salvo alla meta è circa:
4/(32+4)=4/36
Ho fatto anche una simulazione che rispecchia pedantemente il testo e il risultato è lo stesso cioè 11%.
Ma potrei non aver capito niente e sbagliato tutto.
Per cui aspetto lumi dai guru della probabilità.
Comunque il simulatore è molto istruttivo (**http://markov.yoriz.co.uk/**).
Attenzione: Edge mi dice che il sito non è sicuro, perciò non ho attivato il link. Ma ho visto che si attiva in automatico.
Peccato che non si possa ampliare o ridurre la matrice.
P.S. C'è un simulatore carino anche qui: https://www.mathematik.tu-clausthal.de/ ... -discrete/
Pace e bene a tutti.
Gianfranco
Gianfranco
Re: Il problema dei cinque ponti
4/36=1/9
È esattamente il risultato che bo trovato io per tutt'altra strada!
Domattina posto il mio ragionamento.
È esattamente il risultato che bo trovato io per tutt'altra strada!
Domattina posto il mio ragionamento.
Franco
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Il problema dei cinque ponti
Come sempre, quando ci sono formule di mezzo, posto la mia soluzione sotto forma di immagini.
ciao
Franco
Avevo parecchi dubbi di aver sbagliato alla grande ma il fatto che anche Gianfranco per altre vie sia arrivato allo stesso risultato mi conforta parecchio.ciao
Franco
Franco
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Il problema dei cinque ponti
Io sono un fan delle catene di Markov: rappresento in figura il processo semplificato a la Franco
I due stati $\text{C}$, equivalenti per simmetria, diventano lo stato $\Gamma$ mentre le transizioni tra i due stati diventano il restare nello stesso stato; ad ogni transizione che parte da $\text{A}$ o da $\Gamma$ c’è la possibilità di cadere nello stato $\Omega$: una volta arrivato in $\text{B}$ o $\Omega$ il ragno cieco e ubriaco (altrimenti si accorgerebbe di girare su se stesso per tornare indietro) lì rimane (transizioni con probabilità $1$)
$\text{B}$ e $\Omega$ sono stati assorbenti.
Raccogliamo le probabilità di transizione in una matrice $4\times 4$,
$\displaystyle\mathbf{T}=\left(\begin{array}{cC} 0 & \frac16 & 0 & 0 \\ \frac12 & \frac16 & 0 & 0 \\ 0 & \frac16 & 1 & 0 \\ \frac12 & \frac12 & 0 & 1\end{array}\right)$
e rappresentiamo la posizione iniziale del ragno con il vettore $\mathbf{y}_0=\left(1,0,0,0\right)^\text{T}$: la “distribuzione” del ragno nelle quattro posizioni si ottiene con il prodotto
$\displaystyle\mathbf{y}_r=\mathbf{T}\cdot\mathbf{y}_{r-1}=\mathbf{T}^{r}\cdot\mathbf{y}_0$
Dopodichè non dobbiamo far altro che passare al limite: $\mathbf{y}_\infty=\lim_{r\to\infty}\mathbf{y}_r$ e gli elementi corrispondenti agli stati $\text{B}$ e $\Omega$ conterrano le probabilità volute.
I simulatori di Gianfranco non fanno altro che reiterare la moltiplicazione: si può fare facilmente in un foglio di Excel anche per matrici abbastanza grandi.
L’elevamento a potenza di una matrice può essere fatto simbolicamente attraverso il processo di diagonalizzazione: un procedimento che suddivide una matrice nel prodotto di due matrici inverse e una diagonale
$\displaystyle \mathbf{T}=\mathbf{S}\cdot\left(\begin{array}{cC} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \end{array}\right)\cdot \mathbf{S}^{-1}$
La potenza di una matrice diagonale non è altro che la matrice diagonale delle potenze
$\displaystyle \left(\begin{array}{cC} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \end{array}\right)^r=\left(\begin{array}{cC} \lambda_1^r & & & \\ & \lambda_2^r & & \\ & & \ddots & \\ & & & \lambda_n^r \end{array}\right)$
per cui, posto
$\displaystyle \mathbf{\Lambda}=\left(\begin{array}{cC} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \end{array}\right)$
abbiamo
$\displaystyle \mathbf{y}_\infty = \lim_{r\to\infty}\mathbf{T}^r\cdot\mathbf{y}_0=\mathbf{S}\cdot\lim_{r\to\infty}\mathbf{\Lambda}^r\cdot\mathbf{S}^{-1}\cdot\mathbf{y}_0$
Passando al limite, gli elementi della matrice diagonale si annullano se $-1<\lambda_k<1$; gli elementi unitari rimangono invariati.
Nel nostro caso
$\displaystyle \lim_{r\to\infty}\left(\begin{array}{cC} \left(\frac{1-\sqrt{13}}6\right)^r & & & \\ & \left(\frac{1+\sqrt{13}}6\right)^r & & \\ & & 1 & \\ & & & 1 \end{array}\right)= \left(\begin{array}{cC} 0 & & & \\ & 0 & & \\ & & 1 & \\ & & & 1 \end{array}\right)$
Ovviamente i valori unitari corrispondono ai due stati assorbenti.
Chiediamo aiuto a WolframAlpha
otteniamo le matrici $\mathbf{S}$ e $\mathbf{S}^{-1}$, facciamo i dovuti prodotti e otteniamo il vettore
$\displaystyle \mathbf{y}_\infty = \left(0,0,\frac19,\frac89\right)^\text{T}$
Pensavate ad un risultato diverso?
P.S.: Franco, puoi spiegare meglio come deduci che “Sono valide le seguenti equazioni”…
I due stati $\text{C}$, equivalenti per simmetria, diventano lo stato $\Gamma$ mentre le transizioni tra i due stati diventano il restare nello stesso stato; ad ogni transizione che parte da $\text{A}$ o da $\Gamma$ c’è la possibilità di cadere nello stato $\Omega$: una volta arrivato in $\text{B}$ o $\Omega$ il ragno cieco e ubriaco (altrimenti si accorgerebbe di girare su se stesso per tornare indietro) lì rimane (transizioni con probabilità $1$)
$\text{B}$ e $\Omega$ sono stati assorbenti.
Raccogliamo le probabilità di transizione in una matrice $4\times 4$,
$\displaystyle\mathbf{T}=\left(\begin{array}{cC} 0 & \frac16 & 0 & 0 \\ \frac12 & \frac16 & 0 & 0 \\ 0 & \frac16 & 1 & 0 \\ \frac12 & \frac12 & 0 & 1\end{array}\right)$
e rappresentiamo la posizione iniziale del ragno con il vettore $\mathbf{y}_0=\left(1,0,0,0\right)^\text{T}$: la “distribuzione” del ragno nelle quattro posizioni si ottiene con il prodotto
$\displaystyle\mathbf{y}_r=\mathbf{T}\cdot\mathbf{y}_{r-1}=\mathbf{T}^{r}\cdot\mathbf{y}_0$
Dopodichè non dobbiamo far altro che passare al limite: $\mathbf{y}_\infty=\lim_{r\to\infty}\mathbf{y}_r$ e gli elementi corrispondenti agli stati $\text{B}$ e $\Omega$ conterrano le probabilità volute.
I simulatori di Gianfranco non fanno altro che reiterare la moltiplicazione: si può fare facilmente in un foglio di Excel anche per matrici abbastanza grandi.
L’elevamento a potenza di una matrice può essere fatto simbolicamente attraverso il processo di diagonalizzazione: un procedimento che suddivide una matrice nel prodotto di due matrici inverse e una diagonale
$\displaystyle \mathbf{T}=\mathbf{S}\cdot\left(\begin{array}{cC} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \end{array}\right)\cdot \mathbf{S}^{-1}$
La potenza di una matrice diagonale non è altro che la matrice diagonale delle potenze
$\displaystyle \left(\begin{array}{cC} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \end{array}\right)^r=\left(\begin{array}{cC} \lambda_1^r & & & \\ & \lambda_2^r & & \\ & & \ddots & \\ & & & \lambda_n^r \end{array}\right)$
per cui, posto
$\displaystyle \mathbf{\Lambda}=\left(\begin{array}{cC} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n \end{array}\right)$
abbiamo
$\displaystyle \mathbf{y}_\infty = \lim_{r\to\infty}\mathbf{T}^r\cdot\mathbf{y}_0=\mathbf{S}\cdot\lim_{r\to\infty}\mathbf{\Lambda}^r\cdot\mathbf{S}^{-1}\cdot\mathbf{y}_0$
Passando al limite, gli elementi della matrice diagonale si annullano se $-1<\lambda_k<1$; gli elementi unitari rimangono invariati.
Nel nostro caso
$\displaystyle \lim_{r\to\infty}\left(\begin{array}{cC} \left(\frac{1-\sqrt{13}}6\right)^r & & & \\ & \left(\frac{1+\sqrt{13}}6\right)^r & & \\ & & 1 & \\ & & & 1 \end{array}\right)= \left(\begin{array}{cC} 0 & & & \\ & 0 & & \\ & & 1 & \\ & & & 1 \end{array}\right)$
Ovviamente i valori unitari corrispondono ai due stati assorbenti.
Chiediamo aiuto a WolframAlpha
otteniamo le matrici $\mathbf{S}$ e $\mathbf{S}^{-1}$, facciamo i dovuti prodotti e otteniamo il vettore
$\displaystyle \mathbf{y}_\infty = \left(0,0,\frac19,\frac89\right)^\text{T}$
Pensavate ad un risultato diverso?
P.S.: Franco, puoi spiegare meglio come deduci che “Sono valide le seguenti equazioni”…
Ultima modifica di panurgo il gio lug 09, 2020 7:48 am, modificato 1 volta in totale.
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"
Re: Il problema dei cinque ponti
Mah, molto a lume di naso ...
1.
per andare da A a B bisogna comunque passare da C
P(AB) = P(AC)*P(CB) e siccome P(AC)=50% ...
2.
Quando il ragno è in C ci sono 3 casi equiprobabili (1/3 ciascuno)
- arriva al bersaglio (con il 50% di probabilità di arrivarci vivo)
- resta in C avendo preso il ponte centrale (e quindi con il 50% di sopavvivere)
- torna al punto di partenza (sempre con un 50% di provavilità di salvezza)
da cui i valori 1/6 messi nei 3 addendi dell'equazione.
Ripeto, è un approccio un po' fantasioso e forse totalmente sbagliato ma il risultato finale è 1/9
P.S. immagino che nella tua catena lo stato "omega" corrisponda alle lucertole, o sbaglio?
Franco
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician
Re: Il problema dei cinque ponti
$\text{A},\,\text{B},\,\Gamma,\,\cdots,\,\Omega$
è il maiuscolo di
$\alpha,\,\beta,\,\gamma,\,\cdots,\,\omega$
e, come ben si sa, $\Omega$ è The End
è il maiuscolo di
$\alpha,\,\beta,\,\gamma,\,\cdots,\,\omega$
e, come ben si sa, $\Omega$ è The End
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"