Siano $x$, $y$ e $z$ tre variabili aleatorie indipendenti che possono assumere con uguale probabilità i valori dell’insieme $\{1, 2, 3, \ldots, N\}$. Qual è la probabilità che esista un triangolo con lati di lunghezza $x$, $y$ e $z$?Vi sono $N^3$ terne ordinate $(x,y,z)$ con $x,y,z \in \{1, 2, 3, \ldots, N\}$, e quindi la probabilità sarà $p(N)=\dfrac{T(N)}{N^3}$ dove $T(N)$ è il numero di terne $(x,y,z)$ che soddisfano le disuguaglianze triangolari $x<y+z$, $\ y<z+x$, $\ z<x+y$.
Avevo trovato una dimostrazione molto ingombrante, ma un’osservazione di Diecie Cinquepa, compagno di un gruppo facebook, mi ha portato sulla giusta strada. La chiave per risolvere il problema in modo ottimale è:
Consideriamo ad esempio le terne con elemento massimo $4$: quante di queste terne non corrispondono ad un triangolo? Quelle dove la somma degli altri due elementi è minore o uguale a $4$, ovvero quelle dove gli altri elementi, presi ordinatamente, formano le coppie $(1,1)$ (somma $2$), $(1,2)$ e $(2,1)$ (somma $3$), $(1,3)$, $(2,2)$, $(3,1)$ (somma $4$). Le coppie sono $1+2+3$, e poiché il $4$ può essere in prima, seconda o terza posizione, le terne ottenute aggiungendo il $4$ alle coppie trovate saranno $3\times(1+2+3)$. In generale le terne saranno $3\times(1+2+\ldots+n-1)=3\dfrac{n(n-1)}2=\displaystyle{3\binom{n}2}$.
Ora, dalla proprietà dei coefficienti binomiali $\displaystyle{\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}}$ discende l’uguaglianza $\displaystyle{\binom{n}{k}=\binom{n+1}{k+1}-\binom{n}{k+1}}$, e attraverso quest’ultima uguaglianza possiamo calcolare il numero complessivo di terne che non soddisfano tutte le disuguaglianze triangolari, esse sono:$$D(N)=\sum_{n=1}^N 3\binom{n}2=3\sum_{n=1}^N \left[ \binom{n+1}3 - \binom{n}3\right]=\\=3\left[\binom{N+1}3-\binom{N}3+\binom{N}3-\binom{N-1}3+\ldots+\binom23-\binom13\right]=3\binom{N+1}3$$ricordando che se $0\leq n<k$ allora $\displaystyle{\binom{n}{k}=0}$.
Ora, dalla proprietà dei coefficienti binomiali $\displaystyle{\binom{n}{k}+\binom{n}{k+1}=\binom{n+1}{k+1}}$ discende l’uguaglianza $\displaystyle{\binom{n}{k}=\binom{n+1}{k+1}-\binom{n}{k+1}}$, e attraverso quest’ultima uguaglianza possiamo calcolare il numero complessivo di terne che non soddisfano tutte le disuguaglianze triangolari, esse sono:$$D(N)=\sum_{n=1}^N 3\binom{n}2=3\sum_{n=1}^N \left[ \binom{n+1}3 - \binom{n}3\right]=\\=3\left[\binom{N+1}3-\binom{N}3+\binom{N}3-\binom{N-1}3+\ldots+\binom23-\binom13\right]=3\binom{N+1}3$$ricordando che se $0\leq n<k$ allora $\displaystyle{\binom{n}{k}=0}$.
Si avrà allora $$T(N)=N^3-D(N)=N^3-3\ \dfrac{(N+1)N(N-1)}{3!}=\dfrac12N(N^2+1)\ .$$
La probabilità che una terna $(x,y,z)$ corrisponda alle lunghezze dei lati di un triangolo è dunque $p(N)=\dfrac{T(N)}{N^3}$=$\dfrac12+\dfrac1{2N^2}$ e si ha che $\displaystyle{ \lim_{N\to\infty}p(N) = \dfrac12}$. Ci si può convincere che il limite deve essere $1/2$ considerando che una terna $(x,y,z)$ con $x,y,z\in\{1,2,\ldots,N\}$corrisponde alle lunghezze dei lati di un triangolo se e solo se anche la terna $(x/N,y/N,z/N)$ vi corrisponde. Ma per $N$ che tende ad infinito la distribuzione di $x/N$, $y/N$ e $z/N$ approssima sempre meglio la distribuzione uniforme continua in $(0,1)$, discussa nella puntata precedente .
Post
0 commenti:
Posta un commento