OliForum Matematico

Trovare la probabilità che due numeri presi a caso siano coprimi tra loro.

[Più formalmente: trovare il limite per $ n \rightarrow +\infty $ della probabilità che due numeri $ <n $ siano coprimi ]

Sfido a trovare una sol più breve della mia... :P

ehi simo... ma hai una dim elementare (ovvero che non fa uso di cose di analisi)?
Io l'avrei fatto usando il fatto che la somma di phi(i) per i=1.. n va come 6n^2/pi^2 (sta su wikipedia, l'ho appena scoperto ) ma non credo sia una cosa facile da dimostrare... magari ci penso!

Mi pare strano che a me sia venuta una dimostrazione elementare che a Maria non è venuta in mente, spero di non fare una figura di m***a... Vediamo...

Prendiamo due numeri a caso, ovviamente la probabilità che non abbiano uno stesso fattore primo $ p $ è $ $ 1-\frac{1}{p^2}=1-p^{-2} $. Quindi la probabilità che non contenga i primi n fattori primi, indicati con $ p_1,\dots,p_n $

$ $ P=(1-p_1^{-2})(1-p_1^{-2})\dots(1-p_n^{-2}) $
Facendo il limite a infinito avremo
$ $ P=\prod_{p}(1-p^{-2})=\frac{1}{\zeta(2)}=\frac{6}{\pi^2} $

Boll ha scritto: $ \frac{1}{\zeta(2)}=\frac{6}{\pi^2} $

Eli', non definirei questo passaggio come 'teoria elementare'
Intendevo una dimostrazione che facesse uso solo di conoscenze olimpiche...

no vabbè mi accontento che sia scritto come $ (1+1/4 + 1/9 + ... )^{-1} $

Sia $ ~ p(n)= |\{(a,b) \in \mathbb{N}^2 : a \le n, b \le n, gcd(a,b)=1\}| $ la quantità di coppie di naturali coprimi (a,b) che non superano n.

Come le contiamo?
Le coppie (a,b) con $ ~ gcd(a,b) = d, a \le n, b \le n $ sono in corrispondenza biunivoca con le coppie $ ~ (a,b) : gcd(a,b) = 1, a \le \frac nd, b \le \frac nd $ .
Quindi, se da tutte le coppie possibili togliamo quelle con massimo comun divisore > 1, otteniamo la formula:
$ \displaystyle p(n) = n^2 - \sum_{d=2}^n p(\lfloor \frac nd \rfloor) $

Da qui, però, non saprei come andare avanti.
Però, se p(n) fosse approssimabile con qualcosa come $ ~ c \cdot n^2 $, dove c è la probabilità cercata, potremmo stimare che:
$ \displaystyle cn^2 = p(n) = n^2 - \sum_{d=2}^n p(\lfloor \frac nd \rfloor) $$ \approx n^2 - \sum_{d=2}^n c \cdot (\frac nd)^2 = n^2 - cn^2(\frac 14 + \frac 19 + \ldots) $
$ \displaystyle c (1 + \frac 14 + \frac 19 + \ldots) = c \cdot \frac{\pi^2}6 = 1 $

Però quello che ho scritto non vuol dire niente...

Ok, per la dimostrazione contosa era stata fatta a suo tempo da ma_go...

Per quella breve io chiamo $ p $ questa probabilità. Poi dico: Che probabilità c'è che due numeri abbiano mcd uguale a n in genere?

Devono essere entrambi multipli di $ n $ quindi $ 1/n^2 $ e poi levato il fattore $ n $ devono essere coprimi tra loro quindi $ p/n^2 $

Io so che 1 è la probabilità che siano coprii + la robabilità che abbiano mcd =2 + la probabilità che abbiano mcd=3 + .... etc. quindi:

$ 1= p + \frac p{2^2}+ \frac p{3^2} + ... $

da cui la tesi.

Comunque vanno bene tutte le sol proposte sin ora...

clapclap

uau!
... la potenza della tecnica 12 delle schede olimpiche: generalizzare!!

Simo_the_wolf ha scritto:io chiamo $ p $ questa probabilità.

Devi prima dimostrare che quel numero esiste.
Ovvero che la successione delle probabilità parziali converge.

Questo si può fare integrandola con la soluzione di Boll, fino al punto in cui riconduce il limite ad una produttoria. A quel punto è evidente che la produttoria converge perché è fatta di termini <1.

Boll ha scritto: $ $ P=\prod_{p}(1-p^{-2})=\frac{1}{\zeta(2)}=\frac{6}{\pi^2} $

$ $ \frac{1}{P}=\frac{1}{\prod_{p}(1-\frac{1}{p^2})}=\prod_{p}(1+\frac{1}{p^2}+\frac{1}{p^4}+\frac{1}{p^6}+\ldots)=\sum_n \frac{1}{n^2}=\frac{\pi^2}{6} $

frengo ha scritto:$ $ \prod_{p}(1+\frac{1}{p^2}+\frac{1}{p^4}+\frac{1}{p^6}+\ldots)=\sum_n \frac{1}{n^2} $ $

Questa usa il teorema di Dirichlet per il riarrangiamento delle serie (e non solo, perché quella produttoria di sommatorie è proprio brutta), decisamente roba non elementare!

Poi, altra leggerezza: all'inizio inverti P, ma ancora non sai che non è 0. Ma mi pare che serva solo per leggibilità, quindi facciamo finta di niente.

(p.s. sarebbe il caso di spostare il thread, o almeno spezzarlo, vedremo)