Matematické Fórum

Andrejka3

Ahoj. Prosím o pomoc s příkladem:
Pro dané $N\in\mathbb{N}$ urči pravděpodobnost $P(N)$ , že zvolíme-li náhodně dvě čísla $m,n\in\{1,2,\ldots, N\}$ , budou nesoudělná. Ukaž, že
$P(N)\stackrel{N\to\infty}{\longrightarrow}\prod_{p\in\mathbb{P}}\left(1-\frac{1}{p^2}\right)\:.$

Spočítala jsem tohle:
Pro $N\in\mathbb{N}$ označme $\boldsymbol{N}=\{1,2,\ldots, N\}$ , množinu všech prvočísel značme $\mathbb{P}$ , $\mathbb{P}_N\mathrel{\mathop :}=\{p\in\mathbb{P};p\leq N\}$ .
Jsou $m,n\in \boldsymbol{N}$ soudělná, právě když $(\exists p\in\mathbb{P}_N)(p\mid m\;\wedge\;p\mid n)$ . Označme $A_p\mathrel{\mathop :}=\{(m,n)\in\boldsymbol{N}^2;\:p\mid m\;\wedge\;p\mid n\}$ . Pak
$P(N)=\frac{N^2-\left|\bigcup_{\mathbb{P}_N}A_p \right|}{N^2}\:.$
Podle principu inkluze a exkluze,

$P(N)=\frac{1}{N^2}\left( N^2-\sum_{\emptyset\neq X\subseteq \mathbb{P}_N}(-1)^{|X|-1}{\left\lfloor \frac{N}{\prod_{X}p}\right\rfloor}^2\right)=\frac{1}{N^2}\sum_{X\subseteq \mathbb{P}_N}(-1)^{|X|}{\left\lfloor \frac{N}{\prod_{X}p}\right\rfloor}^2\:.$

Nevím, jak dál.

edit: A pak ještě něco, ale vypadá to škareději (?)
$\prod_{p\in\mathbb{P}}\left(1-\frac{1}{p^2}\right)=\lim_{N\to\infty}\prod_{p\in\mathbb{P}_N}\left(1-\frac{1}{p^2}\right)=\lim_{N\to\infty}\sum_{X\subseteq \mathbb{P}_N}\prod_{p\in X}-\frac{1}{p^2}$ .

vanok · 10. 06. 2014 20:14 — Editoval vanok (10. 06. 2014 20:17)

Ahoj
Toto si uz videla?
http://en.wikipedia.org/wiki/Coprime_integers
À toto?
Odkaz

Andrejka3

↑ vanok:
Ahoj.
Díky. Přečetla jsem si v prvním odkazu část Probablilities, a pochopila neformální důkaz (až na výpočet té limity, ale to mi nevadí).

Ohledně toho postupu, co jsem psala, doufala jsem, že snad nějaké tvrzení o dolních částech, nebo spíše pečlivé porovnání obou sum (zatím mi to připadá docela technické), by mohlo dát rovnost obou limit. Tak to asi bude v druhém odkazu, že.

edit: Akorát druhý odkaz jde stejnou cestou.

Il est clair que la probabilité qu'un nombre entier soit divisible par un nombre premier p est 1/p

vanok · 10. 06. 2014 21:20

↑ Andrejka3:, ten citat pokracuje.( Napr jedno zo 7mych je delitelne7mimy)
Potom probabilita aby dve cisla boli delitelne p, je 1/p^2, a proba aby aspon jeden nebol je 1-1/p^2.
Zvysok si rozumela?

Andrejka3 · 11. 06. 2014 07:41

↑ vanok:
Ahoj, ano ten důkaz je pěkný, chci ale najít cestu od toho mého výpočtu k výsledku v odkazech. Snad se mi to povedlo :D :
$\prod_{p\in\mathbb{P}_N}\left(1-\frac{1}{p^2} \right)$ (1)
$\frac{1}{N^2}\sum_{X\subseteq\mathbb{P}_N}(-1)^{|X|}{\left\lfloor\frac{N}{\prod_Xp}\right\rfloor}^2$ (2)
Je $\frac{N}{\prod_Xp}-1\leq\left\lfloor \frac{N}{\prod_Xp}\right\rfloor\leq\frac{N}{\prod_Xp}$ .
Takze $(2)\leq \sum_{X\subseteq\mathbb{P}_N}(-1)^{|X|}\frac{1}{\left(\prod_Xp\right)^2}=\prod_{p\in\mathbb{P}_N}\left(1-\frac{1}{p^2} \right)=(1)$ .
Z druhe strany $(2)\geq \frac{1}{N^2}\sum_{X\subseteq\mathbb{P}_N}(-1)^{|X|}\left(\frac{N}{\prod_Xp}-1\right)^2=(1)+0-\underbrace{\frac{1}{N^2} \sum_{X\subseteq\mathbb{P}_N}(-1)^{|X|}\frac{2N}{\prod_Xp}}_{(3)}$ , kde
$(3)=\frac{2}{N}\prod_{X\subseteq \mathbb{P}_N}\left(1-\frac{1}{p}\right)\stackrel{N\to\infty}{\longrightarrow}0$ .

Odtud, $\lim(1)=\lim(2)$ .
Díky za pomoc.

Matematické Fórum

#1 10. 06. 2014 17:43 — Editoval Andrejka3 (10. 06. 2014 18:14)

pravdepodobnost vyberu dvou nesoudelnych cisel

#2 10. 06. 2014 20:14 — Editoval vanok (10. 06. 2014 20:17)

Re: pravdepodobnost vyberu dvou nesoudelnych cisel

#3 10. 06. 2014 20:43 — Editoval Andrejka3 (10. 06. 2014 20:45)

Re: pravdepodobnost vyberu dvou nesoudelnych cisel

#4 10. 06. 2014 21:20

Re: pravdepodobnost vyberu dvou nesoudelnych cisel

#5 11. 06. 2014 07:41

Re: pravdepodobnost vyberu dvou nesoudelnych cisel

Zápatí