XXVIII - III - Zadanie 3

Rozważmy zbiór $ A = \{0, 1, 2, 3, \ldots, 2^{2n-1}\} $. Dana jest funkcja $ f: A \to A $ taka, że dla każdego ciągu $ (x_0, x_1, \ldots, x_{2n-1}) $ o wyrazach równych 0 lub 1 spełniona jest równość

\[<br />
\begin{split}<br />
f(x_0 + 2x_1 + 2^2x_2 + \ldots + 2^{2n-1}x_{2n-1}) = (1 - x_0) + 2x_1 + \\<br />
+ (1 - x_2)\cdot 2^2 + x_3 \cdot 2^3 + \ldots + (1 - x_{2n-2}) \cdot 2^{2n-2} + \\<br />
+ x_{2n-1}\cdot 2^{2n-1}.<br />
\end{split}<br />
\]

Udowodnić, że jeżeli liczby $ a_1, a_2, \ldots, a_9 \in A $ są kolejnymi wyrazami ciągu arytmetycznego, to ciąg $ (f(a_1), f(a_2), \ldots, f(a_9)) $ nie jest rosnący.

Rozwiązanie

Dowolną liczbę $ a \in A $ zapiszmy w systemie dwójkowym dopisując ewentualnie z lewej strony odpowiednią liczbę zer tak, aby zapis miał $ 2n $ cyfr. Z warunków zadania wynika, że zapis liczby $ f(a) $ otrzymujemy z zapisu liczby $ a $ przez zamianę na miejscach parzystych (licząc od lewej strony) zer na jedynki i jedynek na zera.

Udowodnimy, że jeżeli liczby $ a_1, a_2, \ldots, a_5 \in A $ są kolejnymi wyrazami ciągu arytmetycznego o różnicy dodatniej $ d $, to ciąg $ (f(a_1), f(a_2), \ldots, f(a_5)) $ nie jest monotoniczny. Wynika stąd teza zadania nawet dla ciągów pięciowyrazowych.

Niech w zapisie dwójkowym liczby $ d $ pierwsza jedynka znajduje się na miejscu $ m $-tym licząc od lewej strony. Wtedy $ d \geq 2^{2n-m} $. Załóżmy, ze liczba $ m $ jest parzysta. W pozostałym przypadku rozumowanie przebiega podobnie. Ponieważ

\[<br />
4d \leq a_1 + 4d = a_s < 2^{2n},\quad \textrm{więc} \quad d < 2^{2n-2}<br />
\]

i stąd $ 2n - m < 2n - 2 $, czyli $ m \geq 3 $.

Rozpatrzmy wszystkie układy zer i jedynek, jakie występują na miejscach o numerach $ m-2, m-1, m $ w rozwinięciach dwójkowych liczb należących do zbioru $ A $. Układów tych jest $ 8 $, są one podane na rys. 17.

Przy tym, jeżeli $ x, x+d \in A $ oraz liczbie $ x $ odpowiada pewien układ, to liczbie $ x + d $ może odpowiadać jeden z dwóch układów w zależności od tego, czy dodając cyfry stojące na miejscach o numerze $ m +1 $ w rozwinięciach liczb $ x $ i $ d $ będziemy mieli $ 0 $, czy $ 1 $ w pamięci.

Na przykład, jeżeh $ x = \ldots \underline{101} \ldots $, $ d = 0 \ldots 0 \underline{001} \ldots $ to $ x + d=<br />
\ldots \underline{110} \ldots $ lub $ x + d = \ldots \underline{111} \ldots $ (podkreślamy cyfry na miejscach o numerach $ m - 2, m - 1, m $).

Na rys. 17 układ odpowiadający liczbie $ x $ łączymy strzałką (pojedynczą, podwójną lub przerywaną) z układem odpowiadającym liczbie $ x + d $. Przy tym strzałka jest przerywana wtedy i tylko wtedy gdy cyfry występujące na miejscach wcześniejszych od $ (m - 2) $ w rozwinięciach liczb $ x $ i $ x + d $ są różne. Na przykład, jeżeli $ x = 0 \ldots 0\underline{111}0 \ldots 0 $, to $ x + d = 0 \ldots 01\underline{000} \ldots $. Widzimy, że cyfry na $ (m - 3) $ miejscu w rozwinięciach liczb $ x $ i $ x + d $ są różne. Zatem od układu $ 111 $ do układu $ 000 $ prowadzi strzałka przerywana.

Pozostałe układy łączymy strzałką pojedynczą lub podwójną w zależności od tego, czy $ f(x) > f(x + d) $, czy $ f(x) < f(x + d) $. Na przykład, jeżeli $ x = \ldots \underline{100} \ldots $ to $ x + d = \ldots \underline{101} \ldots $ lub $ x + d = \ldots \underline{110} \ldots $ oraz cyfry występujące w rozwinięciach liczb $ x $ i $ x + d $ na miejscach o numerach mniejszych od $ m - 2 $ są jednakowe. Przy tym, ponieważ $ m $ jest liczbą parzystą, a $ f $ zmienia na miejscach parzystych jedynki na zera, a zera na jedynki, więc

\[ f(\ldots \underline{100} \ldots) = \ldots \underline{001} \ldots, \]
\[ f(\ldots \underline{101} \ldots) = \ldots \underline{000} \ldots, \]
\[ f(\ldots \underline{110} \ldots) = \ldots \underline{011} \ldots. \]

Zatem

\[<br />
f(\ldots \underline{101} \ldots) < f(x) =<br />
f(\ldots \underline{100} \ldots) < f(\ldots \underline{110} \ldots).<br />
\]

Wobec tego od układu $ 100 $ do układu $ 101 $ prowadzimy strzałki podwójną, a od układu $ 100 $ do układu $ 110 $ - strzałkę pojedynczą (rys. 17).

Jeżeli $ (a_1, a_2, \ldots, a_5) $ jest ciągiem arytmetycznym o różnicy $ d $ i wyrazach należących do zbioru $ A $, to liczbom $ a_1, a_2, \ldots, a_5 $ odpowiadają pewne układy cyfr na rys. 17 połączone kolejnymi czterem strzałkami. Sprawdzamy bezpośrednio, że każda droga złożona z czterech kolejnych strzałek na rys. 17 zawiera co najmniej jedną strzałkę pojedynczą i co najmniej jedną strzałkę podwójną. Ale jednej z tych strzałek odpowiada nierówność $ f(x + d) < f(x) $, a drugiej - $ f(x + d) > f(x) $. Wobec tego ciąg $ (f(a_1), f(a_2), \ldots, f(a_5) $ nie jest monotoniczny.

Uwaga. Istnieją ciągi arytmetyczne o czterech wyrazach $ (a_1, a_2, a_3, a4) $ takie, że ciąg $ (f(a_1), f(a_2), f(a_3), f(a_4)) $ jest rosnący.

Weźmy na przykład $ n = 2 $, $ a_1 = 4 $, $ a_2 = 6 $, $ a_3 = 8 $, $ a_4 = 10 $. Wtedy $ d = 2 = 0010 $ i wobec tego $ m = 3 $. Mamy więc

\[<br />
4 = \underline{010}0,\ 6 = \underline{011}0,\ 8 = \underline{100}0,\ 10 = \underline{101}0,<br />
\]
\[<br />
f(4) = \underline{000}1,\ f(6) =\underline{001}1,\ f(8) = \underline{110}1,\ f(10) = \underline{111}1.<br />
\]

Zatem $ f(4) < f(6) < f(8) < f(10) $.

Komentarze

Dodaj nową odpowiedź