LVII OM - I - Zadanie 12

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

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

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

\[<br /> (1) \qquad a_0 =(f_n \circ f_{n-1} \circ \dots \circ f_1)(a_0),<br /> \]

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

\[<br /> (2) \qquad a_0 < (\tilde{f}_n \circ \tilde{f}_{n-1} \circ \dots \circ \tilde{f}_1)(a_0),<br /> \]

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

\[<br /> a_0 < \frac{a_0\cdot 3^s}{2^r},<br /> \]

czyli $ 3^s > 2^r $.

Niech

\[<br /> h(x)= g(f(x)) = \frac{3}{2}x-1.<br /> \]

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

\[<br /> (3) \qquad a_0 =(g_r \circ g_{r-1} \circ \dots \circ g_1)(a_0),<br /> \]

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

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

A zatem

\[<br /> (4)\qquad a_0 \geqslant (h^s \circ f^{r-s})(a_0).<br /> \]

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:

\[<br /> \begin{split}<br /> h^{s+1}(x) &= h(h^s(x)) = h \left( \left( \frac{3}{2}\right)^s (x-2)+2 \right) = \\<br /> &= \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.<br /> \end{split}<br /> \]

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

\[<br /> a_0 \geqslant \left(\frac{3}{2}\right)\left(\frac{a_0}{2^{r-s}}-2\right)+2<br /> \]

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

\[<br /> (3^s-2^r)a_0 \leqslant 3^s \cdot 2^{r-s+1} - 2^{r+1}.<br /> \]

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

\[<br /> a_0 \leq (3^s - 2^r) a_0 \leq 2^{r+1} \left(\left(\frac{3}{2}\right)^s-1\right)<br /> = 2^{n+1}\left(\left(\frac{3}{r}\right)^s - \left(\frac{1}{2}\right)^s \right)<br /> \]

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

\[<br /> \left(\frac{3}{r}\right)^s - \left(\frac{1}{2}\right)^s < \frac{1}{2} \text{ dla }s =1,2,3,\dots.<br /> \]

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

\[<br /> \left(\frac{3}{r}\right)^s - \left(\frac{1}{2}\right)^s < \left(\frac{3}{r}\right)^s<br /> \leq \left(\frac{3}{r}\right)^3 = \frac{27}{64} <\frac{1}{2}.<br /> \]

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

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

Komentarze

by Gość - 01/12/2012 - 20:52

Drobne błędy

"[...] Obie funkcje p i q są rosnące [...]"

Literówka, zamiast "q" ma być "g".

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

We wzorze poniżej tego zdania brakuje s w potędze liczby (3/2).

Dodaj nową odpowiedź