IMO Shortlist

We start with some observations. First, from the definition of $x_{i}$ it follows that for each positive integer $k$ we have
$$x_{4k-3}=x_{2k-1}=-x_{4k-2} \quad \text{ and } \quad x_{4k-1}=x_{4k}=-x_{2k}=x_{k} .$$
Hence, denoting $S_{n}=\sum_{i=1}^{n} x_{i}$, we have
$$S_{4k}=\sum_{i=1}^{k}\left(\left(x_{4k-3}+x_{4k-2}\right)+\left(x_{4k-1}+x_{4k}\right)\right)=\sum_{i=1}^{k}\left(0+2x_{k}\right)=2S_{k}$$
$$S_{4k+2}=S_{4k}+\left(x_{4k+1}+x_{4k+2}\right)=S_{4k}$$
Observe also that $S_{n}=\sum_{i=1}^{n} x_{i} \equiv \sum_{i=1}^{n} 1=n \pmod{2}$.
Now we prove by induction on $k$ that $S_{i} \geq 0$ for all $i \leq 4k$. The base case is valid since $x_{1}=x_{3}=x_{4}=1$, $x_{2}=-1$. For the induction step, assume that $S_{i} \geq 0$ for all $i \leq 4k$. Using the relations above, we obtain
$$S_{4k+4}=2S_{k+1} \geq 0, \quad S_{4k+2}=S_{4k} \geq 0, \quad S_{4k+3}=S_{4k+2}+x_{4k+3}=\frac{S_{4k+2}+S_{4k+4}}{2} \geq 0$$
So, we are left to prove that $S_{4k+1} \geq 0$. If $k$ is odd, then $S_{4k}=2S_{k} \geq 0$; since $k$ is odd, $S_{k}$ is odd as well, so we have $S_{4k} \geq 2$ and hence $S_{4k+1}=S_{4k}+x_{4k+1} \geq 1$.
Conversely, if $k$ is even, then we have $x_{4k+1}=x_{2k+1}=x_{k+1}$, hence $S_{4k+1}=S_{4k}+x_{4k+1}=2S_{k}+x_{k+1}=S_{k}+S_{k+1} \geq 0$. The step is proved.

We will use the notation of $S_{n}$ and the relations above from the previous solution.
Assume the contrary and consider the minimal $n$ such that $S_{n+1}<0$; surely $n \geq 1$, and from $S_{n} \geq 0$ we get $S_{n}=0$, $x_{n+1}=-1$. Hence, we are especially interested in the set $M=\{n: S_{n}=0\}$; our aim is to prove that $x_{n+1}=1$ whenever $n \in M$ thus coming to a contradiction.
For this purpose, we first describe the set $M$ inductively. We claim that (i) $M$ consists only of even numbers, (ii) $2 \in M$, and (iii) for every even $n \geq 4$ we have $n \in M \Longleftrightarrow [n/4] \in M$. Actually, (i) holds since $S_{n} \equiv n \pmod{2}$, (ii) is straightforward, while (iii) follows from the relations $S_{4k+2}=S_{4k}=2S_{k}$.
Now, we are left to prove that $x_{n+1}=1$ if $n \in M$. We use the induction on $n$. The base case is $n=2$, that is, the minimal element of $M$; here we have $x_{3}=1$, as desired.
For the induction step, consider some $4 \leq n \in M$ and let $m=[n/4] \in M$; then $m$ is even, and $x_{m+1}=1$ by the induction hypothesis. We prove that $x_{n+1}=x_{m+1}=1$. If $n=4m$ then we have $x_{n+1}=x_{2m+1}=x_{m+1}$ since $m$ is even; otherwise, $n=4m+2$, and $x_{n+1}=-x_{2m+2}=x_{m+1}$, as desired. The proof is complete.