LVI OM - I - Zadanie 12

Dane są funkcje

\[<br />
f(x)=2^x$ \quad \text{oraz} \quad $g(x)= f(f(f(f(f(f(f(x)))))))<br />
\]

(7-krotna iteracja funkcji $ f $). Rozstrzygnąć, czy liczba $ g(3)-g(0) $ jest podzielna przez liczbę $ g(2)-g(0) $.

Rozwiązanie

Liczby $ g(0) $, $ g(2) $ i $ g(3) $ są odpowiednio wyrazami $ a_7 $, $ b_7 $ i $ c_7 $ ciągów $ (a_n) $, $ (b_n) $ i $ (c_n) $ określonych rekurencyjnie wzorami

\[<br />
\left\{<br />
\begin{array}{l}<br />
a_0=0\\<br />
a_{n+1}=2^{a_n},<br />
\end{array}<br />
\right.<br />
\left\{<br />
\begin{array}{l}<br />
b_0=2\\<br />
b_{n+1}=2^{b_n},<br />
\end{array}<br />
\right.<br />
\left\{<br />
\begin{array}{l}<br />
c_0=3\\<br />
c_{n+1}=2^{c_n},<br />
\end{array}<br />
\right.<br />
\]

Wykażemy, że liczba $ c_7-a_7 =g(3)-g(0) $ nie dzieli się przez $ b_7-a_7 =g(2)-g(0) $. W dowodzie skorzystamy z następującego lematu:

Lemat

Dane są takie liczby całkowite dodatnie $ k $ i $ l $, że liczba $ 2^l-1 $ jest podzielna przez $ 2^k -1 $. Wówczas liczba $ l $ jest podzielna przez $ k $.

Dowód

Niech $ l = kq +r $, gdzie $ r \in \{0,1,2,\ldots,k-1\} $. Liczby $ 2^l -1 $ i $ 2^{kq} -1 $ są podzielne przez $ 2^k-1 $, zatem różnica tych liczb, czyli liczba $ 2^l -2^{kq} =2^{kq}(2^r -1) $ jest podzielna przez $ 2k - 1 $. Liczby $ 2^{kq} $ i $ 2^k - 1 $ są względnie pierwsze, skąd wynika, że liczba $ 2^r -1 $ jest podzielna przez $ 2^k -1 $. Ponieważ $ r<k $, więc podzielność ta ma miejsce jedynie wtedy, gdy $ r = 0 $. To oznacza, że liczba $ l $ jest podzielna przez $ k $.

Przystępujemy do rozwiązania zadania. Przypuśćmy, że $ b_7 -a_7 |c_7 -a_7 $. Wtedy $ 2^{b_{6}}-2^{a_{6}}|2^{c_{6}}-2^{a_{6}} $, skąd wynika, że $ 2^{b_{6}-a_{6}}-1|2^{c_{6}-a_{6}}-1 $. Korzystając z lematu uzyskujemy $ b_{6}-a_{6}|c_{6}-a_{6} $.

Kontynuując to rozumowanie dochodzimy do podzielności $ b_0-a_0 |c_0-a_0 $, czyli 2|3, co nie jest prawdą.

Komentarze

Dodaj nową odpowiedź