Il problema dei cinque ponti

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Il problema dei cinque ponti

Messaggio da Gianfranco »

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?
5ponti.png
5ponti.png (19.23 KiB) Visto 7673 volte
Pace e bene a tutti.
Gianfranco

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Il problema dei cinque ponti

Messaggio da panurgo »

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

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Il problema dei cinque ponti

Messaggio da Gianfranco »

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?
---
Pace e bene a tutti.
Gianfranco

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Il problema dei cinque ponti

Messaggio da panurgo »

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

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Il problema dei cinque ponti

Messaggio da panurgo »

ICinquePonti.01.540x640.png
ICinquePonti.01.540x640.png (51.33 KiB) Visto 7637 volte
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"

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Il problema dei cinque ponti

Messaggio da franco »

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:
5ponti.png
5ponti.png (25.86 KiB) Visto 7631 volte
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

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Il problema dei cinque ponti

Messaggio da Gianfranco »

franco ha scritto:
lun lug 06, 2020 12:59 pm
Un ragno cieco e grasso deve andare da A a B spostandosi sui "5 ponti" costituiti da fili di ragnatela illustrati nella figura.
...
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.
markov_ragno.png
markov_ragno.png (37.77 KiB) Visto 7587 volte
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

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Il problema dei cinque ponti

Messaggio da franco »

4/36=1/9
È 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

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Il problema dei cinque ponti

Messaggio da franco »

Come sempre, quando ci sono formule di mezzo, posto la mia soluzione sotto forma di immagini.
5ponti1.PNG
5ponti1.PNG (112.87 KiB) Visto 7574 volte
5ponti2.PNG
5ponti2.PNG (28.09 KiB) Visto 7574 volte
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

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Il problema dei cinque ponti

Messaggio da panurgo »

Io sono un fan delle catene di Markov: rappresento in figura il processo semplificato a la Franco
ICinquePunti.04.640x640.png
ICinquePunti.04.640x640.png (35.45 KiB) Visto 7547 volte
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? :wink:

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"

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Il problema dei cinque ponti

Messaggio da franco »

panurgo ha scritto:
mer lug 08, 2020 3:26 pm
P.S.: Franco, puoi spiegare meglio come deduci che “Sono valide le seguenti equazioni”…
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

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Il problema dei cinque ponti

Messaggio da panurgo »

$\text{A},\,\text{B},\,\Gamma,\,\cdots,\,\Omega$

è il maiuscolo di

$\alpha,\,\beta,\,\gamma,\,\cdots,\,\omega$

e, come ben si sa, $\Omega$ è The End :wink:
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"

Rispondi