LVII OM - I - Zadanie 12

Zawody matematyczne:

LVII OM, 2005-2006

Etap:

Niech $a_0$ będzie liczbą całkowitą dodatnią i niech

$ a_{i+1} = \begin{cases} a_i/2, &\text{gdy } a_i \text{ jest liczbą parzystą}, \\ 3a_i -1, &\text{gdy } a_i \text{ jest liczbą nieparzystą} \end{cases} $

dla $i=0,1,2,\dots$ . Wykazać, że jeśli $n$ jest liczbą całkowitą dodatnią spełniającą warunek $a_n = a_0$ , to $2^n >a_0$ .

Rozwiązanie

Niech $a_{\ell}$ będzie największym spośród wyrazów $a_0,a_1,\dots ,a_{n-1}$ . Wówczas ciąg $b_i = a_{\ell+i}$ dla $i =0,1,2,...$ także spełnia dany w treści zadania warunek rekurencyjny oraz równość $b_n =b_0$ . Ponadto $b_0$ jest największą liczbą spośród $b_0,b_1,\dots,b_{n-1}$ .

Możemy więc bez straty ogólności przyjąć, że $a_0$ jest największą liczbą spośród $a_0,a_1,\dots ,a_{n-1}$ .
Stąd w szczególności wynika, że $a_0$ jest liczbą parzystą.

Oznaczmy: $f(x)= x/2$ oraz $g(x)=3x-1$ . Wówczas równość $a_0 = a_n$ możemy przypisać w postaci

$ (1) \qquad a_0 =(f_n \circ f_{n-1} \circ \dots \circ f_1)(a_0), $

gdzie każda z funkcji $f_1,f_2,\dots ,f_n$ jest równa funkcji $f$ lub funkcji $g$ . Przyjmijmy w dalszej części rozwiązania, że
w złożeniu występującym z prawej strony równości (1) znajduje się dokładnie $r$ funkcji $f$ oraz dokładnie $s$ funkcji $g$ .
Wtedy oczywiście $r + s = n$ oraz $r,s \geq 1$ .

Odwzorowanie $g$ przeprowadza wyraz nieparzysty $a_i$ na wyraz parzysty $3a_i-1$ . Stąd wynika, że jeśli dla pewnego $i$
mamy $f_i = g$ , to $f_{i-1} = f$ . Wyraz $a_0$ jest parzysty, więc $f_1 = f$ . Z obserwacji tych wynika, że $r \geq s$ .

Niech $p(x)=3x$ . Wtedy dla dowolnej liczby rzeczywistej $x$ spełniona jest zależność $g(x)<p(x)$ . Obie funkcje $p$ i $q$
są rosnące, więc zastępując każdą funkcję $g$ znajdującą się w równości (1) przez funkcję $p$ powiększamy wartość wyrażenia
stojącego z prawej stronie równości (1). Innymi słowy

$ (2) \qquad a_0 < (\tilde{f}_n \circ \tilde{f}_{n-1} \circ \dots \circ \tilde{f}_1)(a_0), $

gdzie tym razem każda z funkcji $\tilde{f}_1,\tilde{f}_2,\dots ,\tilde{f}_n$ jest równa funkcji $f$ lub funkcji $p$ .
Nierówność (2) jest równoważna zależności

$ a_0 < \frac{a_0\cdot 3^s}{2^r}, $

czyli $3^s > 2^r$ .

Niech

$ h(x)= g(f(x)) = \frac{3}{2}x-1. $

Jak zauważyliśmy wyżej, w równości (1) mamy $f_1 = f$ . Ponadto jeśli dla pewnego $i \geq 2$ spełniona jest zależność
$f_i = g$ , to $f_{i-1} = f$ . Zatem związek (1) możemy przepisać w postaci

$ (3) \qquad a_0 =(g_r \circ g_{r-1} \circ \dots \circ g_1)(a_0), $

gdzie każda z funkcji $g_1,g_2,\dots,g_r$ jest równa $f$ lub $h$ . Ponadto z prawej strony równości (3) występuje dokładnie
$s$ funkcji $h$ oraz $r-s$ funkcji $f$ .

Dalej zauważmy, że $h(f(x))= \frac{3}{4}x-1< \frac{3}{4}x-\frac{1}{2} =f(h(x))$ dla dowolnej liczby rzeczywistej $x$ .
Obie funkcje $f$ i $h$ są rosnące, zatem wymieniając w równości 3) dowolne złożenie $f \circ h$ na złożenie $h \circ f$
zmniejszamy wartość wyrażenia stojącego po prawej stronie równości (3). Przy pomocy skończonej liczby takich zamian możemy
doprowadzić prawą stronę związku (3) do postaci

$ (\underbrace{h\circ h\circ \dots \circ h}_{s\text{ razy}} \circ \underbrace{f \circ f \circ \dots \circ f}_{r-s \text{ razy}})(a_0)=(h^s\circ f^{r-s})(a0). $

A zatem

$ (4)\qquad a_0 \geqslant (h^s \circ f^{r-s})(a_0). $

Udowodnimy indukcyjnie, że $h^s(x)=(\frac{3}{2})^s(x-2)+2$ dla $s=1,2,\dots$ (gdzie $h^s$ oznacza $s$ -krotne złożenie
funkcji $h$ ). Istotnie: Dla $s=1$ powyższa równość jest spełniona, a krok indukcyjny wygląda następująco:

$ \begin{split} h^{s+1}(x) &= h(h^s(x)) = h \left( \left( \frac{3}{2}\right)^s (x-2)+2 \right) = \\ &= \frac{3}{2} \cdot \left(\left(\frac{3}{2}\right)^s (x-2)+2\right)-1 = \left(\frac{3}{2}\right)^{s+1}(x-2)+2. \end{split} $

Korzystając z udowodnionej właśnie zależności przepisujemy nierówność (4) jako

$ a_0 \geqslant \left(\frac{3}{2}\right)\left(\frac{a_0}{2^{r-s}}-2\right)+2 $

Mnożąc ją stronami przez $2r$ i przegrupowując wyrazy uzyskujemy

$ (3^s-2^r)a_0 \leqslant 3^s \cdot 2^{r-s+1} - 2^{r+1}. $

Wyżej udowodniliśmy, że $3^s > 2^r$ , a więc $3^s -2^r \geq 1$ . Zatem

$ a_0 \leq (3^s - 2^r) a_0 \leq 2^{r+1} \left(\left(\frac{3}{2}\right)^s-1\right) = 2^{n+1}\left(\left(\frac{3}{r}\right)^s - \left(\frac{1}{2}\right)^s \right) $

Aby dokończyć rozwiązanie zadania wystarczy wykazać, że

$ \left(\frac{3}{r}\right)^s - \left(\frac{1}{2}\right)^s < \frac{1}{2} \text{ dla }s =1,2,3,\dots. $

Bezpośrednio sprawdzamy, że dla $s=1$ i dla $s = 2$ powyższa nierówność jest spełniona. Jeśli natomiast $s \geq 3$ , to

$ \left(\frac{3}{r}\right)^s - \left(\frac{1}{2}\right)^s < \left(\frac{3}{r}\right)^s \leq \left(\frac{3}{r}\right)^3 = \frac{27}{64} <\frac{1}{2}. $

Tym samym rozwiązanie zadania zostało zakończone.