XLIV OM - III - Zadanie 3

Zawody matematyczne:

XLIV OM, 1992-1993

Etap:

III

Oznaczmy przez $g(k)$ największy dzielnik nieparzysty liczby całkowitej dodatniej $k$ oraz przyjmijmy

$ f(k) = \begin{cases} \frac{k}{2} + \frac{k}{g(k)} & \text{ dla } $k$ \text{ parzystego,} \\ 2^{\frac{k+1}{2}} & \text{ dla } $k$ \text{ nieparzystego.} \end{cases} $

Ciąg $(x_n)$ jest określony przez zależności $x_1 = 1$ , $x_{n+1} = f(x_n)$ . Wykazać, że liczba 800 występuje wśród wyrazów tego ciągu dokładnie raz. Wyznaczyć $n$ , dla którego $x_n = 800$ .

Rozwiązanie

Wypiszmy piętnaście początkowych wyrazów ciągu $(x_n)$ , grupując je w bloki złożone kolejno z jednego, dwóch, trzech, czterech, pięciu wyrazów:

$ (U) \qquad \begin{array}{rrrrrr} 1\\ 2& 3\\ 4 & 6 & 5\\ 8 & 12 & 10& 7\\ 16 & 24 & 20 & 14& 9\\ \vdots & \vdots &\vdots &\vdots &\vdots & \ddots \end{array} $

Otrzymaliśmy pięć wierszy układu nieskończonego (U), który można kontynuować według następujących zasad: $j$ --ty wiersz składa się z $j$ liczb, z których ostatnią jest $2j - 1$ ; każda liczba nie będąca ostatnim wyrazem żadnego wiersza jest dwukrotnością liczby znajdującej się bezpośrednio nad nią.

Przyjmijmy te zasady za definicję układu (U).

Każda liczba całkowita $k \geq 1$ da się jednoznacznie przedstawić w postaci

$ (1) \qquad k = 2^m(2j - 1) \quad (m \geq 0, j \geq 1 \textrm{ całkowite}); $

pojawia się więc w układzie (U) dokładnie jeden raz, mianowicie na $m$ --tej pozycji w $j$ --lej kolumnie (pozycje w kolumnie numerujemy od zera).

Jeśli $k$ jest liczbą parzystą, a więc ma postać (1) z $m \geq 1$ , to $g(k) = 2j - 1$ , wobec czego

$ (2) \qquad f(k) = \frac{k}{2} + \frac{k}{g(k)} = 2^{m-1}(2j-1) + 2^m = 2^{m-1}(2(j + 1)-1). $

To znaczy, że $f(k)$ znajduje się w $(j + 1)$ --ej kolumnie na $(m-1)$ --ej pozycji, czyli bezpośrednio na prawo od $k$ .

Jeśli $k$ jest liczbą nieparzystą, $k = 2j - 1$ (a więc stanowi prawy koniec $j$ --tego wiersza), to

$ f(k) = 2^{(k+1)/2} = 2^j. $

W tym przypadku liczba $f(k)$ jest pierwszym wyrazem $(j + 1)$ --go (czyli następnego) wiersza.

Stąd wynika, że odczytując wyrazy tabeli (U) leksykograficznie, to znaczy, wiersz za wierszem (a w każdym wierszu - od lewej do prawej strony), przebiegniemy kolejne wyrazy ciągu $(x_n)$ , zgodnie z określającą ten ciąg zależnością rekurencyjną $x_{n+1} =f(x_n)$ .

Każda liczba naturalna $k \geq 1$ występuje w schemacie (U), więc i w ciągu $x_1,x_2,x_3,\ldots$ dokładnie raz. W szczególności dotyczy to liczby $k = 800$ . Pozostaje zlokalizować tę liczbę. Zgodnie z ogólną regułą, liczba $800$ , równa $2^5(2\cdot 13 -1)$ , znajduje się w trzynastej kolumnie, na piątej pozycji. Wobec tego (por. wzory (1) i (2)) liczba $f(800)$ znajduje się w czternastej kolumnie na czwartej pozycji, liczba $f\circ f(800)$ znajduje się w piętnastej kolumnie na trzeciej pozycji, itd., liczba $f \circ f \circ f \circ f \circ f (800)$ znajduje się w osiemnastej kolumnie na zerowej pozycji, czyli stanowi prawy koniec osiemnastego wiersza.

Skoro $j$ -ty wiersz liczy $j$ wyrazów, zatem liczba kończąca wiersz osiemnasty występuje w ciągu $(x_n)$ z numerem $1 + 2 + 3 + \ldots + 18 = 171$ . Jeśli więc $800 = x_N$ , to mamy równość $x_{N+5} = f \circ f \circ f \circ f \circ f (800) = x_{171}$ . Stąd (wobec różnowartościowości ciągu $(x_n)$ ) wnosimy, że $N + 5 = 171$ , czyli $N = 166$ .