XXVI - III - Zadanie 6

Zawody matematyczne:

XXVI OM, 1974-1975

Etap:

III

Dane są funkcje $S$ i $T$ , $S(x) = 1 - x$ , $T(x) = -\frac{1}{2}$ dla $0\leq x \leq 1$ . Czy istnieje funkcja $f$ postaci

$ (1) \qquad f= g_1 \circ g_2 \circ \ldots g_n, \text{ gdzie }g_k = T \text{ lub } g_k = S $

dla $k = 1,2, \ldots, n$ przy pewnym naturalnym $n$ taka, że

$ f\left(\frac{1}{2}\right) = \frac{1975}{2^{1975}} ? $

Rozwiązanie

Udowodnimy

Twierdzenie. Każda liczba wymierna $\displaystyle \frac{m}{n}$ należąca do przedziału, $(0 ;\ 1)$ , gdzie $m$ jest liczbą nieparzystą, a $n$ - potęgą dwójki, jest równa $f\left( \frac{1}{2} \right)$ dla pewnej funkcji $f$ postaci (1).

Dowód. Zastosujemy indukcję ze względu na liczbę $m+n$ . Z określenia liczb $m$ i $n$ wynika, że $m+n \geq 3$ . Jeżeli $m+n = 3$ , to $m = 1$ , $n=2$ i wtedy $S \left( \displaystyle \frac{1}{2} \right) = \frac{1}{2}$ . Wystarczy więc przyjąć $f = S$ .

Załóżmy z kolei, że $m+n > 3$ i załóżmy, że dla dowolnych liczb naturalnych $m'$ , $n'$ , gdzie $m'$ jest liczbą nieparzystą, $n'$ - potęgą dwójki, $\displaystyle 0 < \frac{m'}{n'} < 1$ i $m' + n' < m + n$ , istnieje taka funkcja $f'$ postaci 1, że $\displaystyle f' \left( \frac{1}{2} \right) = \frac{m'}{n'}$ .

Jeżeli $\displaystyle \frac{m}{n} < \frac{1}{2}$ , to $\displaystyle 0 < \frac{m}{\frac{1}{2}n} < 1$ i liczba $\displaystyle \frac{1}{2} n$ jest potęgą dwójki. Stosując więc założenie indukcyjne do liczb $m' = m$ i $n' = \displaystyle \frac{1}{2} n$ stwierdzamy, że istnieje funkcja $f'$ postaci (1) taka, że $f' \displaystyle \left( \frac{1}{2} \right) = \frac{m'}{n'}$ . Wtedy jako $f$ wystarczy przyjąć funkcję $T \circ f'$ . Mamy bowiem

$ (T \circ f') \left( \frac{1}{2} \right) = T \left( f' \left( \frac{1}{2} \right)\right)= T \left( \frac{m'}{n'} \right)= \frac{1}{2} \cdot \frac{m'}{n'} = \frac{m}{n}. $

Jeżeli $\displaystyle \frac{1}{2} < \frac{m}{n} < 1$ , to $\displaystyle 0 < 1 - \frac{m}{n} < \frac{1}{2}$ . Mamy też 1 $\displaystyle -\frac{m}{n}= \frac{n-m}{n}$ i liczba $n-m$ jest nieparzysta, a $n$ jest potęgą dwójki. Przy tym $n-m+n < m+n$ , ponieważ $\displaystyle \frac{m}{n} > \frac{1}{2}$ . Z założenia indukcyjnego zastosowanego do liczb $m' = n-m$ i $n' = n$ wynika, że istnieje funkcja $f'$ postaci (1) spełniająca $\displaystyle f' \left( \frac{1}{2} \right) = \frac{n-m}{n}$ . Wtedy jako $f$ wystarczy przyjąć funkcję $S \circ f'$ . Mamy bowiem

$ (S \circ f') \left( \frac{1}{2} \right) = S \left( f' \left( \frac{1}{2} \right) \right) = S\left( \frac{n-m}{n} \right) = 1- \frac{n-m}{n} = \frac{m}{n}/ $

Wobec tego na mocy indukcji twierdzenie zachodzi dla każdej liczby wymiernej $\displaystyle \frac{m}{n}$ rozważanej postaci.

W szczególności stosując postępowanie opisane w dowodzie twierdzenia do liczby $\displaystyle \frac{1975}{2^{1975}}$ otrzymujemy, że $\displaystyle f \left( \frac{1}{2} \right) = \frac{1975}{2^{1975}}$ , gdzie $f = T^{1964} \circ S \circ T^4 \circ S \circ T \circ S \circ T^2 \circ S \circ T \circ S \circ T^2$ i $T_k$ oznacza $k$ -krotną superpozycję funkcji $T$ .