Shortlist JBMO, 2008

Solution:
Since $a_{n-1} \equiv s(a_{n-1})$ (all congruences are modulo $9$), we have $2a_{n-1} \equiv a_{n} \equiv 2008 \equiv 10$, so $a_{n-1} \equiv 5$. But $a_{n-1} < 2008$, so $s(a_{n-1}) \leq 28$ and thus $s(a_{n-1})$ can equal $5$, $14$ or $23$. We check $s(2008-5) = s(2003) = 5$, $s(2008-14) = s(1994) = 23$, $s(2008-23) = s(1985) = 23$. Thus $a_{n-1}$ can equal $1985$ or $2003$.

As above $2a_{n-2} \equiv a_{n-1} \equiv 5 \equiv 14$, so $a_{n-2} \equiv 7$. But $a_{n-2} < 2003$, so $s(a_{n-2}) \leq 28$ and thus $s(a_{n-2})$ can equal $16$ or $25$. Checking as above we see that the only possibility is $s(2003-25) = s(1978) = 25$. Thus $a_{n-2}$ can be only $1978$.

Now $2a_{n-3} \equiv a_{n-2} \equiv 7 \equiv 16$ and $a_{n-3} \equiv 8$. But $s(a_{n-3}) \leq 27$ and thus $s(a_{n-3})$ can equal $17$ or $26$. The check works only for $s(1978-17) = s(1961) = 17$. Thus $a_{n-3} = 1961$ and similarly $a_{n-4} = 1939 \equiv 4$, $a_{n-5} = 1919 \equiv 2$ (if they exist).

The search for $a_{n-6}$ requires a residue of $1$. But $a_{n-6} < 1919$, so $s(a_{n-6}) \leq 27$ and thus $s(a_{n-6})$ can be equal only to $10$ or $19$. The check fails for both $s(1919-10) = s(1909) = 19$ and $s(1919-19) = s(1900) = 10$. Thus $n \leq 6$ and the case $n = 6$ is constructed above ($1919$, $1939$, $1961$, $1978$, $2003$, $2008$).