XL OM - II - Zadanie 5

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dany jest ciąg $(c_n)$ liczb naturalnych określony rekurencyjnie: $c_1 = 2$ , $c_{n+1} = \left[ \frac{3}{2}c_n\right]$ . Udowodnić, że wśród wyrazów tego ciągu jest nieskończenie wiele liczb parzystych i nieskończenie wiele liczb nieparzystych.

Rozwiązanie

Wystarczy udowodnić następujące dwa stwierdzenia:

(a) Dla dowolnej liczby parzystej $p$ będącej wyrazem ciągu $(c_n)$ istnieje większa od niej liczba nieparzysta będąca wyrazem tego ciągu.

(b) Dla dowolnej liczby nieparzystej $q$ będącej wyrazem ciągu $(c_n)$ istnieje większa od niej liczba parzysta będąca wyrazem tego ciągu.

Dowód zdania (a). Niech $p = 2^km$ , $k,m \geq1$ , $m$ nieparzyste. Jeśli $p = c_n$ , to $c_{n+1} = 2^{k-1}\cdot 3m$ ; gdy $k -1 \geq 1$ , wówczas $c_{n+2} = 2^{k-2}\cdot 3^2m$ ; itd., ogólnie, dla $j \in \{1,\ldots, k\}$ mamy $c_{n-j} = 2^{k-j} \cdot 3^j m$ . W szczególności dla $j = k$ dostajemy $c_{n+k} = 3^km$ . Jest to większa niż p liczba nieparzysta.

Dowód zdania (b). Teraz $q - 1$ jest liczbą parzystą, dodatnią ( $q - 1$ nie może być zerem, bo $c_n \geq 2$ dla wszystkich $n$ ; to wynika przez natychmiastową indukcję z określenia ciągu $(c_n)$ ). Zatem $q = 2^km+1$ , $k,m \geq 1$ , $m$ nieparzyste. Jeśli $q = c_n$ , to $c_{n+1} = 2^{k-1}\cdot 3m + 1$ i ogólnie, jak poprzednio, dla $j\in \{1, \ldots, k\}$ mamy $c_{n+j} = 2^{k-j}\cdot 3^jm+1$ ; w szczególności $c_{n+k} = 3^km + 1$ . Jest to większa niż $q$ liczba parzysta.