China National Team Selection Test

For any $a \in [0, 1)$, define a sequence $\{a_i\}_{i=0}^n$ generated by $a$ as follows: $a_0 = a$; for $1 \le i \le n$, $a_i = a_{i-1} - x_i$ if $a_{i-1} \ge 0$, and $a_i = a_{i-1} + x_i$ if $a_{i-1} < 0$.

Set $f(a) = a_n$. It is easy to show by induction that $|a_i| \le 1$ for every $0 \le i \le n$.

If there exists $a \in [0, 1)$ such that $f(a) = -a$, consider the sequence generated by $a$, $a_0 = a, a_1, ..., a_n = f(a) = -a$. Clearly, this sequence satisfies the conditions (1) and (3). By the recursive relation, it also satisfies the condition (2). Thus, it suffices to show that there exists $a \in [0, 1)$ such that $f(a) = -a$.

For any $a \in [0, 1)$, we say that $a$ is a breaking point if at least one term in its generating sequence is $0$. Since every breaking point is of the form $\sum_{i=1}^{n} t_i x_i$, where $t_i = -1, 0, 1$, there are finitely many breaking points.

Clearly, $0$ is a breaking point; label all breaking points in increasing order by $0 = b_1 < b_2 < \cdots < b_m < 1$.

We first prove that for $1 \le k \le m-1$, $f(a) = f(b_k) + (a-b_k)$ for every $a \in [b_k, b_{k+1})$.

Consider $b_k, b_{k+1}$ and their generating sequences. Assume that $q_0 = b_k, q_1, q_2, \dots, q_n$ is the generating sequence of $b_k$, and $r_0 = b_{k+1}, r_1, r_2, \dots, r_n$ is the generating sequence of $b_{k+1}$. Suppose that $r_l$ is the first term of $\{r_i\}_{i=0}^n$ equal to $0$.

Construct a sequence $\{s_i\}_{i=0}^n$ as follows:
$$\begin{align*} s_0 &= r_0, \quad s_1 = r_1, \quad \dots, \quad s_l = r_l = 0, \\ s_{l+1} &= -r_{l+1}, \quad \dots, \quad s_n = -r_n. \end{align*}$$
It is clear that the sequence $\{s_i\}_{i=0}^n$ satisfies $s_0 = b_{k+1}$; and for $1 \le i \le n$, $s_i = s_{i-1} - x_i$ if $s_{i-1} > 0$, and $s_i = s_{i-1} + x_i$ if $s_{i-1} \le 0$.

We prove by induction that $q_i s_i \ge 0$ and $s_i - q_i = b_{k+1} - b_k$.

The conclusion is obviously true for $i=0$. Assume that it holds for $i-1$. Then $q_{i-1} s_{i-1} \ge 0$ and $s_{i-1} - q_{i-1} = b_{k+1} - b_k > 0$, which implies that $q_{i-1} \ge 0$, $s_{i-1} > 0$, or $q_{i-1} < 0$, $s_{i-1} \le 0$. In the former case, $q_i = q_{i-1} - x_i$, $s_i = s_{i-1} - x_i$, and thus $s_i - q_i = s_{i-1} - q_{i-1} = b_{k+1} - b_k$. Similarly, in the latter case, we have $s_i - q_i = b_{k+1} - b_k$.

If $q_i s_i < 0$, then $q_i < 0 < s_i$. Set $b' = b_{k+1} - s_i = b_k + (-q_i) \in (b_k, b_{k+1})$, and consider the generating sequence of $b'$, $u_0 = b', u_1, \dots, u_n$. It is easy to show by induction that $s_j - u_j = s_0 - u_0 = s_i$ for any $0 \le j \le i$ ($q_{j-1}$ and $s_{j-1}$ both add or subtract $x_j$ for $j < i$; $u_j$ lies between $q_{j-1}$ and $s_{j-1}$, so the recursive relation is the same). Then $u_i = s_i - s_i = 0$, i.e. $b'$ is a breaking point — a contradiction to $b_k, b_{k+1}$ being two consecutive breaking points. Therefore, $q_i s_i \ge 0$. By induction we have verified that $q_i s_i \ge 0$ and $s_i - q_i = b_{k+1} - b_k$ for all $0 \le i \le n$.

Since $f(b_k) = q_n$, $f(b_{k+1}) = r_n = -s_n$, we have $f(b_k) + f(b_{k+1}) = b_k - b_{k+1}$. It follows from the above argument that, for any $b_k < b' < b_{k+1}$, the generating sequence of $b'$ has the same recursive relation as $\{q_i\}_{i=0}^n$ and $\{s_i\}_{i=0}^n$, and hence
$$f(b') = f(b_k) + (b' - b_k).$$
Let us go back to the original problem.

If $f(b_k) = -b_k$ for some $k$, we are done. If $f(b_k) = b_k$ for some $k$, then consider the generating sequence of $b_k$, reversing every term after the first $0$, and we obtain a new sequence $z_0 = b_k, z_1, \dots, z_n = -b_k$, which satisfies the required conditions. Now assume that $|f(b_k)| \ne b_k$ for every $k$, and we shall consider two cases to show that $f(a) = -a$ for some $a \in [0, 1)$:

Case 1: $|f(b_m)| < b_m$. Since $|f(b_1)| > b_1 = 0$, there exists $k$ such that $|f(b_k)| > b_k$, $|f(b_{k+1})| < b_{k+1}$.

Since $f(b_k) + f(b_{k+1}) = b_k - b_{k+1}$, we have $f(b_k) - b_k = -(f(b_{k+1}) + b_{k+1}) < 0$, and hence $f(b_k) \le -b_k$. Again by $f(b_k) + f(b_{k+1}) = b_k - b_{k+1}$, we have
$$f(b_k) = b_k - b_{k+1} - f(b_{k+1}) > b_k - 2b_{k+1},$$
i.e.
$$b_k - 2b_{k+1} < f(b_k) < -b_k.$$
Let $b' = \frac{b_k - f(b_k)}{2}$. Then $b_k < b' < b_{k+1}$, and
$$f(b') = f(b_k) + (b' - b_k) = (b_k - 2b') + (b' - b_k) = -b',$$
and the result follows.

Case 2: $|f(b_m)| > b_m$. Since there is no breaking number in $(b_m, 1)$, we see from the previous argument that for any $b' \in (b_m, 1)$, the generating sequence of $b'$ and the generating sequence of $b_m$ have the same recursive relation, and hence
$$f(b') = f(b_m) + (b' - b_m).$$
Since $|f| \le 1$, we have $f(b_m) \le b_m$, and hence
$$-1 \le f(b_m) < -b_m.$$
Let $b' = \frac{b_m - f(b_m)}{2}$. Then
$$b_m = \frac{b_m - (-b_m)}{2} < b' < \frac{b_m - (-1)}{2} = \frac{b_m + 1}{2} < 1,$$
$$\begin{aligned} f(b') &= f(b_m) + (b' - b_m) \\ &= (b_m - 2b') + (b' - b_m) = -b'. \end{aligned}$$
The result again follows.