IMO Shortlist, 2019

We prove by induction on $k$ that every initial segment of the sequence, $a_{0}, a_{1}, \ldots, a_{k}$, consists of the following elements (counted with multiplicity, and not necessarily in order), for some $\ell \geqslant 0$ with $2 \ell \leqslant k+1$ :
$$0,1, \ldots, \ell-1, \quad 0,1, \ldots, k-\ell .$$
For $k=0$ we have $a_{0}=0$, which is of this form. Now suppose that for $k=m$ the elements $a_{0}, a_{1}, \ldots, a_{m}$ are $0,0,1,1,2,2, \ldots, \ell-1, \ell-1, \ell, \ell+1, \ldots, m-\ell-1, m-\ell$ for some $\ell$ with $0 \leqslant 2 \ell \leqslant m+1$. It is given that
$$\binom{m+1}{a_{0}}+\binom{m+1}{a_{1}}+\cdots+\binom{m+1}{a_{m}}+\binom{m+1}{a_{m+1}}=2^{m+1},$$
which becomes
$$\begin{aligned} \left(\binom{m+1}{0}+\binom{m+1}{1}\right. & \left.+\cdots+\binom{m+1}{\ell-1}\right) \\ & +\left(\binom{m+1}{0}+\binom{m+1}{1}+\cdots+\binom{m+1}{m-\ell}\right)+\binom{m+1}{a_{m+1}}=2^{m+1} \end{aligned}$$
or, using $\binom{m+1}{i}=\binom{m+1}{m+1-i}$, that
$$\begin{aligned} \left(\binom{m+1}{0}+\binom{m+1}{1}\right. & \left.+\cdots+\binom{m+1}{\ell-1}\right) \\ & +\left(\binom{m+1}{m+1}+\binom{m+1}{m}+\cdots+\binom{m+1}{\ell+1}\right)+\binom{m+1}{a_{m+1}}=2^{m+1} \end{aligned}$$
On the other hand, it is well known that
$$\binom{m+1}{0}+\binom{m+1}{1}+\cdots+\binom{m+1}{m+1}=2^{m+1},$$
and so, by subtracting, we get
$$\binom{m+1}{a_{m+1}}=\binom{m+1}{\ell} .$$
From this, using the fact that the binomial coefficients $\binom{m+1}{i}$ are increasing for $i \leqslant \frac{m+1}{2}$ and decreasing for $i \geqslant \frac{m+1}{2}$, we conclude that either $a_{m+1}=\ell$ or $a_{m+1}=m+1-\ell$. In either case, $a_{0}, a_{1}, \ldots, a_{m+1}$ is again of the claimed form, which concludes the induction.
As a result of this description, any integer $N \geqslant 0$ appears as a term of the sequence $a_{i}$ for some $0 \leqslant i \leqslant 2 N$.