XLIV OM - III - Zadanie 3

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

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

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:

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

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

\[<br /> (1) \qquad k = 2^m(2j - 1) \quad (m \geq 0, j \geq 1 \textrm{ całkowite});<br /> \]

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

\[<br /> (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).<br /> \]

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

\[<br /> f(k) = 2^{(k+1)/2} = 2^j.<br /> \]

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

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź