XIX OM - I - Zadanie 2

Niech $ p(n) $ oznacza liczbę liczb pierwszych nie większych od liczby naturalnej $ n $. Dowieść, że jeżeli $ n \geq 8 $, to $ p(n) < \frac{n}{2} $

Rozwiązanie

Jeżeli $ n $ jest liczbą parzystą, to w zbiorze liczb naturalnych od $ 1 $ do $ n $ jest $ \frac{n}{2}-1 $ liczb parzystych różnych od $ 2 $, a więc złożonych, oraz co najmniej jedna liczba nieparzysta, mianowicie $ 1 $, która nie jest liczbą pierwszą. Liczby pierwsze należą do zbioru pozostałych $ \frac{n}{2} $ liczb, więc $ p(n) \leq \frac{n}{2} $.

Jeżeli $ n $ jest liczbą nieparzystą co najmniej równą $ 9 $, to w zbiorze liczb naturalnych od $ 1 $ do $ n $ znajduje się $ \frac{n-1}{2}-1 $ liczb parzystych różnych od $ 2 $ oraz są w nim co najmniej dwie liczby nieparzyste, mianowicie $ 1 $ i $ 9 $, nie będące liczbami pierwszymi. Liczby pierwsze należą do zbioru pozostałych $ n - \left(\frac{n-1}{2}-1 \right) - 2 = \frac{n-1}{2} $ liczb, więc $ p(n)< \frac{n}{2} $.

Zatem dla każdego naturalnego $ n $:

\[<br />
n \geq 8 \Longrightarrow p(n) \leq \frac{n}{2}.<br />
\]

Komentarze

Dodaj nową odpowiedź