LVII OM - II - Zadanie 4

Niech $ c $ będzie ustaloną liczbą całkowitą dodatnią. Ciąg $ (a_n) $ jest określony przez warunki

\[<br />
a_1 =1,\;a_{n+1} = d(a_n)+c \text{ dla } n =1,2,\dots,<br />
\]

gdzie $ d(m) $ oznacza liczbę dodatnich dzielników liczby $ m $. Wykazać, że istnieje taka liczba całkowita dodatnia $ k $,
że ciąg $ a_k,a_{k+1},a_{k+2},\ldots $ jest okresowy.

Rozwiązanie

Wykażemy, że dla $ n =1,2,3,\ldots $ zachodzą nierówności $ 1 \leq a_n \leq 2c+2 $. Pierwsza z nich jest oczywiście spełniona.
Drugą wykażemy indukcyjnie. Dla $ n = 1 $ mamy $ a_1 = 1 \leq 2c + 2 $, co jest prawdą. Ustalmy więc $ n>1 $ i przyjmijmy, że
$ a_n \leq 2c+2 $.

Jeśli $ k \geq 3 $ jest liczbą całkowitą, to żadna liczba całkowita z przedziału $ (\frac{1}{2}k,k) $ nie jest dzielnikiem
liczby $ k $. Wobec tego liczba $ k $ nie może mieć więcej niż $ \frac{1}{2}k + 1 $ dzielników dodatnich. Zatem

\[<br />
d(k) \leq \frac{k}{2} + 1 \quad \text{ dla }k =3,4,\ldots.<br />
\]

Bezpośrednio sprawdzamy, że powyższa nierówność jest również spełniona dla $ k = 1 $ oraz dla $ k = 2 $. Stąd oraz z założenia
indukcyjnego uzyskujemy

\[<br />
a_{n+1} = d(a_n)+c \leq \frac{a_n}{2}+1+c \leq \frac{2c+2}{2}+1+c =2c+2,<br />
\]

co kończy dowód indukcyjny postulowanej nierówności. Ciąg $ (an) $ jest więc ograniczony, a zatem istnieją takie liczby całkowite dodatnie $ k<l $, że $ a_k = a_l $.

Każdy wyraz $ a_n $ danego ciągu wyznacza wyraz następny $ a_{n+1} $, a więc ciąg $ a_k,a_{k+1},a_{k+2},\ldots $ jest okresowy o okresie równym $ l-k $.

Komentarze

Dodaj nową odpowiedź