Taiwan IMO Selection Camp

Define $S_n = \sum_{i=1}^n x_i$。First observe that
$$x_{4k-3} = -x_{4k-2} = x_{2k-1}$$
$$x_{4k-1} = x_{4k} = -x_{2k} = x_k$$
We prove by mathematical induction on $k$ that for any $i \le 4k$ we have $S_i \ge 0$. When $k=1$,
$x_1 = -x_2 = x_3 = x_4 = 1$, and the statement clearly holds.
Suppose it is known that for any $i \le 4k$ we have $S_i \ge 0$, then
$$S_{4k+2} = S_{4k} + x_{4k+1} + x_{4k+2} = S_{4k} \ge 0$$
$$S_{4k+4} = \sum_{i=1}^{k+1} ((x_{4k-3} + x_{4k-2}) + (x_{4k-1} + x_{4k})) = \sum_{i=1}^{k+1} (0 + 2x_i) = 2S_{k+1} \ge 0$$
$$S_{4k+3} = \frac{S_{4k+2} + S_{4k+4}}{2} \ge 0$$
We are only left with proving $S_{4k+1} \ge 0$. When $k$ is even, since $x_{4k+1} = x_{2k+1} = x_{k+1}$,
we have
$$S_{4k+1} = S_{4k} + x_{4k+1} = 2S_k + x_{k+1} = S_k + S_{k+1} \ge 0.$$
When $k$ is odd, since $S_k \ge 0$ and
$$S_k \equiv \sum_{i=1}^{k} x_i \equiv \sum_{i=1}^{k} 1 \equiv k \pmod{2},$$
we obtain $S_k \ge 1$. Thus
$$S_{4k+1} = 2S_k + x_{k+1} \ge 2-1 \ge 0.$$
Therefore, by mathematical induction we know that for any positive integer $i$, $S_i \ge 0$ holds, which completes the proof!