XIX OM - I - Zadanie 2

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

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 />$