PL-OM 1977 Problem 3

Consider the set $A = \{0, 1, 2, . . . , 2^{2n} - 1\}$ . The function $f : A \rightarrow A$ is given by: $f(x_0 + 2x_1 + 2^2x_2 + ... + 2^{2n-1}x_{2n-1})=$ $(1 - x_0) + 2x_1 + 2^2(1 - x_2) + 2^3x_3 + ... + 2^{2n-1}x_{2n-1}$ for every $0-1$ sequence $(x_0, x_1, . . . , x_{2n-1})$ . Show that if $a_1, a_2, . . . , a_9$ are consecutive terms of an arithmetic progression, then the sequence $f(a_1), f(a_2), . . . , f(a_9)$ is not increasing.