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ść

$ \begin{split} f(x_0 + 2x_1 + 2^2x_2 + \ldots + 2^{2n-1}x_{2n-1}) = (1 - x_0) + 2x_1 + \\ + (1 - x_2)\cdot 2^2 + x_3 \cdot 2^3 + \ldots + (1 - x_{2n-2}) \cdot 2^{2n-2} + \\ + x_{2n-1}\cdot 2^{2n-1}. \end{split} $

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ż

$ 4d \leq a_1 + 4d = a_s < 2^{2n},\quad \textrm{więc} \quad d < 2^{2n-2} $

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= \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

$ f(\ldots \underline{101} \ldots) < f(x) = f(\ldots \underline{100} \ldots) < f(\ldots \underline{110} \ldots). $

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.