PrawdopodobieństwoWyzwanieZadanie nr 3699

Granica prawdopodobieństwa, że NWD dwóch losowych liczb jest kwadratem liczby całkowitej

Prawdopodobieństwo w teorii liczb Zadania konkursoweZadania olimpijskieAnaliza (calculus)

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}\).

+18 pkt za pierwsze rozwiązanie na koncie

Zapis: ułamki (3/4), pierwiastki (2sqrt(3)), pi/6.

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
  1. 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)\).
  2. 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).
  3. 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}\).
  4. \(\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.

Więcej zadań z prawdopodobieństwa →

Podobne zadania