PrawdopodobieństwoWyzwanieZadanie nr 3699
Granica prawdopodobieństwa, że NWD dwóch losowych liczb jest kwadratem liczby całkowitej
Ze zbioru \(\{1,2,\dots,N\}\) losujemy niezależnie (ze zwracaniem) dwie liczby \(a\) i \(b\). Niech \(p_N\) będzie prawdopodobieństwem, że \(\operatorname{NWD}(a,b)\) jest kwadratem liczby całkowitej (np. \(1\), \(4\), \(9\)). Oblicz \(\lim_{N\to\infty}p_N\). Wolno skorzystać z równości \(\sum_{k\ge1}\frac1{k^2}=\frac{\pi^2}{6}\) i \(\sum_{k\ge1}\frac1{k^4}=\frac{\pi^4}{90}\).
Świetnie.
Jak rozwiązać to zadanie?
Potrzebujesz pomocy? Pokaż wskazówkę
Najpierw wyznacz granicę \(q\) prawdopodobieństwa, że liczby są względnie pierwsze, rozbijając wszystkie pary według wartości NWD. Potem policz granicę prawdopodobieństwa, że \(\operatorname{NWD}(a,b)=d\).
Chcesz poznać sposób? Rozwiązanie krok po kroku
- Para \((a,b)\) ma \(\operatorname{NWD}=d\) wtedy i tylko wtedy, gdy \(a=da'\), \(b=db'\) z \(\operatorname{NWD}(a',b')=1\), \(a',b'\le\frac Nd\). Niech \(c(M)\) — liczba par względnie pierwszych w \(\{1,\dots,M\}^2\). Wtedy \(N^2=\sum_{d\ge1}c\bigl(\lfloor N/d\rfloor\bigr)\).
- Ze wzoru odwrócenia Möbiusa \(c(N)=\sum_{d}\mu(d)\lfloor N/d\rfloor^2\), więc \(\frac{c(N)}{N^2}\to\sum_d\frac{\mu(d)}{d^2}=q\), a z \(\sum_d\frac1{d^2}\cdot\sum_d\frac{\mu(d)}{d^2}=1\) (splot Dirichleta \(1*\mu\)) dostajemy \(q=\frac6{\pi^2}\). Szereg \(\sum\frac1{d^2}\) jest zbieżny, więc przejście do granicy pod sumą jest uprawnione (ogony są jednostajnie małe).
- Prawdopodobieństwo, że \(\operatorname{NWD}(a,b)=d\), to \(\frac{c(\lfloor N/d\rfloor)}{N^2}\to\frac{q}{d^2}\), z ograniczeniem \(\frac{c(\lfloor N/d\rfloor)}{N^2}\le\frac1{d^2}\). Sumując po \(d=k^2\) (zbieżność majoryzowana szeregiem \(\sum\frac1{k^4}\)): \(\lim p_N=q\sum_{k\ge1}\frac1{k^4}=\frac6{\pi^2}\cdot\frac{\pi^4}{90}\).
- \(\lim_{N\to\infty}p_N=\frac{\pi^2}{15}\).
Odpowiedź: \(\frac{\pi^2}{15}\)
Czego warto się nauczyć?
Klasyczne prawdopodobieństwo sprowadza się do dobrego policzenia dwóch zbiorów: wszystkich wyników i wyników sprzyjających.
Podobne zadania
- Wybór najlepszego z dziesięciu kandydatów przy decyzjach podejmowanych na bieżąco
- Pięć losowych punktów na okręgu: pięciokąt zawiera środek okręgu
- Średnia liczba rzutów kostką do pierwszej szóstki, gdy wszystkie wyniki są parzyste
- Losowanie 8 białych i 5 czarnych kul: białych nigdy nie mniej niż czarnych