LVI OM - I - Zadanie 12

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Dane są funkcje

$ f(x)=2^x$ \quad \text{oraz} \quad $g(x)= f(f(f(f(f(f(f(x))))))) $

(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

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

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