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{array}{rl}{s}_0& =r_0,s_1=r_1,\dots ,s_l=r_l=0,\\ s_{l+1}& =-r_{l+1},\dots ,s_n=-r_n.\end{array}$$ 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^{\prime }=b_{k+1}-s_i=b_k+(-q_i)\in (b_k,b_{k+1})$, and consider the generating sequence of $b^{\prime }$, $u_0=b^{\prime },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^{\prime }$ 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^{\prime }<b_{k+1}$, the generating sequence of $b^{\prime }$ has the same recursive relation as $\{q_i{\}}_{i=0}^n$ and $\{s_i{\}}_{i=0}^n$, and hence $$f(b^{\prime })=f(b_k)+(b^{\prime }-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^{\prime }=\frac{b_k-f(b_k)}{2}$. Then $b_k<b^{\prime }<b_{k+1}$, and $$f(b^{\prime })=f(b_k)+(b^{\prime }-b_k)=(b_k-2b^{\prime })+(b^{\prime }-b_k)=-b^{\prime },$$ 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^{\prime }\in (b_m,1)$, the generating sequence of $b^{\prime }$ and the generating sequence of $b_m$ have the same recursive relation, and hence $$f(b^{\prime })=f(b_m)+(b^{\prime }-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^{\prime }=\frac{b_m-f(b_m)}{2}$. Then $$b_m=\frac{b_m-(-b_m)}{2}<b^{\prime }<\frac{b_m-(-1)}{2}=\frac{b_m+1}{2}<1,$$ $$\begin{array}{rl}f(b^{\prime })& =f(b_m)+(b^{\prime }-b_m)\\ & =(b_m-2b^{\prime })+(b^{\prime }-b_m)=-b^{\prime }.\end{array}$$ The result again follows.