LVII OM - II - Zadanie 4

Zawody matematyczne:

LVII OM, 2005-2006

Etap:

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

$ a_1 =1,\;a_{n+1} = d(a_n)+c \text{ dla } n =1,2,\dots, $

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

$ d(k) \leq \frac{k}{2} + 1 \quad \text{ dla }k =3,4,\ldots. $

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

$ a_{n+1} = d(a_n)+c \leq \frac{a_n}{2}+1+c \leq \frac{2c+2}{2}+1+c =2c+2, $

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