Griglie, formiche, calcolo combinatorio e statistica
Preso dal test della SNS dell'AA 2009-2010
Allora, io sono partito da questo approccio perché questo quesito simile ad un problema che avevo già affrontato:
Per arrivare a $B(m,n)$ la formica deve necessariamente fare m passi verso W e n passi verso N, con un totale di m+n passi.
I percorsi sono distinti tra loro per almeno un elemento quindi è una combinazione $C_{m+n,n}$ e da questa ricaviamo che $m$ e $n$ devono essere entrambi $>0$.
Per risolvere il punto a sono partito dal considerare che per $A(0,0)$ e per $B(m,n)$ la formica deve assolutamente passare mentre per alcuni punti la probabilità che passi è minima. Chiamando $i+j=q$ ho elaborato che $1/2^q$ esprime la probabilità che la formica sia passata da $C(i,j)$ fino a che $2q=m+n$ da questo caso in poi la probabilità comincia a salire e da qui in poi non so bene come rendere la mia formula adatta a tutti i punti del rettangolo.
Naturalmente escludo dalla mia ricerca tutti i punti $C(i,j)$ con $i>m$ o $j>n$ perché per le ipotesi del quesito la formica non può uscire dalla griglia.
Edit:
La probabilità di passare per un punto $C(i,j)$ è data da tutti i percorsi che ci arrivano sul totale dei miei percorsi da $A$ a $B$ quindi forse potrebbe essere $C_{i+j,i} / C_{m+n,n}$?
Per b la soluzione è molto semplice, la probabilità è minima quando la mia $f= 1/2^q$ è minima quindi quando q è massima nell'intervallo $0<=q<=(m+n)/2$
Io non riesco ad andare oltre a questo punto, consigli?
Edoardo
4. Su un piano cartesiano è disposta una rete metallica costituita da fili rettilinei
che, incrociandosi perpendicolarmente, formano quadrati di lato
unitario. La rete `e disposta con i fili paralleli agli assi coordinati e gli
incroci nei punti con coordinate intere.
Una formica si muove lungo la rete, scegliendo a caso ad ogni incrocio
quale direzione prendere, ma sempre nel verso positivo degli assi
coordinati.
(a) La formica ha percorso un cammino dall’origine (0;0) al punto di
coordinate (m;n), con m;n>0. Qual `e la probabilit`a che sia passata
per un dato punto di coordinate (i; j)?
(b) Per quali punti (i; j) del rettangolo di vertici (0;0), (m;0), (0;n),
(m;n) tale probabilit`a `e minima?
Allora, io sono partito da questo approccio perché questo quesito simile ad un problema che avevo già affrontato:
Per arrivare a $B(m,n)$ la formica deve necessariamente fare m passi verso W e n passi verso N, con un totale di m+n passi.
I percorsi sono distinti tra loro per almeno un elemento quindi è una combinazione $C_{m+n,n}$ e da questa ricaviamo che $m$ e $n$ devono essere entrambi $>0$.
Per risolvere il punto a sono partito dal considerare che per $A(0,0)$ e per $B(m,n)$ la formica deve assolutamente passare mentre per alcuni punti la probabilità che passi è minima. Chiamando $i+j=q$ ho elaborato che $1/2^q$ esprime la probabilità che la formica sia passata da $C(i,j)$ fino a che $2q=m+n$ da questo caso in poi la probabilità comincia a salire e da qui in poi non so bene come rendere la mia formula adatta a tutti i punti del rettangolo.
Naturalmente escludo dalla mia ricerca tutti i punti $C(i,j)$ con $i>m$ o $j>n$ perché per le ipotesi del quesito la formica non può uscire dalla griglia.
Edit:
La probabilità di passare per un punto $C(i,j)$ è data da tutti i percorsi che ci arrivano sul totale dei miei percorsi da $A$ a $B$ quindi forse potrebbe essere $C_{i+j,i} / C_{m+n,n}$?
Per b la soluzione è molto semplice, la probabilità è minima quando la mia $f= 1/2^q$ è minima quindi quando q è massima nell'intervallo $0<=q<=(m+n)/2$
Io non riesco ad andare oltre a questo punto, consigli?
Edoardo
Risposte
Per rispondere alla domanda (a) potresti fare il rapporto tra casi favorevoli e casi possbili.
I casi possibili li hai già individuati come le combinazioni \( \displaystyle {m+n \choose n} \).
Sono tutti i possibili percorsi che da A portano a B.
Per i casi favorevoli vuoi, tra tutti i percorsi che da A vanno a B, quelli che transitano per C(i,j).
Questi sono tutti i modi di accoppiare un percorso che porta da A a C, con uno che porta da C a B:
\( \displaystyle {i+j \choose j} \cdot {m-i+n-j \choose n-j} \)
Per il punto (b) mi sembra evidente che si ha un unico caso favorevole nei vertici D(0,n) ed E(m,0).
I casi possibili li hai già individuati come le combinazioni \( \displaystyle {m+n \choose n} \).
Sono tutti i possibili percorsi che da A portano a B.
Per i casi favorevoli vuoi, tra tutti i percorsi che da A vanno a B, quelli che transitano per C(i,j).
Questi sono tutti i modi di accoppiare un percorso che porta da A a C, con uno che porta da C a B:
\( \displaystyle {i+j \choose j} \cdot {m-i+n-j \choose n-j} \)
Per il punto (b) mi sembra evidente che si ha un unico caso favorevole nei vertici D(0,n) ed E(m,0).
Grande, grazie mille per l'aiuto, non riuscivo proprio a risolvere il problema delle probabilità, non mi era nemmeno passato in mente che $C_{i,j} * C_{m-i,n-j}$ dovessero essere tutti i percorsi per C, inoltre con questo è ovvio che la probabilità sia minima in $(0,n) ; (m,0)$, ci passa un solo percorso! 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo