Probabilità well known...

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Probabilità well known...

Messaggio da Simo_the_wolf »

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:P
Avatar utente
Leblanc
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00

Messaggio da Leblanc »

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!
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

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} $
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Avatar utente
Leblanc
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00

Messaggio da Leblanc »

Boll ha scritto: $ \frac{1}{\zeta(2)}=\frac{6}{\pi^2} $
Eli', non definirei questo passaggio come 'teoria elementare' :P
Intendevo una dimostrazione che facesse uso solo di conoscenze olimpiche...
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

no vabbè mi accontento che sia scritto come $ (1+1/4 + 1/9 + ... )^{-1} $
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

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...
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

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...
Avatar utente
mattilgale
Messaggi: 372
Iscritto il: 01 gen 1970, 01:00
Località: Lucca
Contatta:

Messaggio da mattilgale »

clapclap
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"

Galileo Galilei
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

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

Messaggio da MindFlyer »

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.
Avatar utente
frengo
Messaggi: 223
Iscritto il: 01 gen 1970, 01:00

Messaggio da frengo »

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} $
MindFlyer

Messaggio da MindFlyer »

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. :D

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