55rd Ukrainian National Mathematical Olympiad - Fourth Round

If $a=b=1$ then $(a_n)$ has terms $(1;1;2;1;3;1;4;1;5;1;...)$, and $(a_n+a_{n+1})$ has terms $(2;3;3;4;4;5;5;6;6;7;...)$. Therefore $a=b=1$ satisfies the condition of the question.

Let $a_1=a$ and $a_2=b$. Suppose that $a_1\ne 1$ or $a_2\ne 1$. Without loss of generality it can be assumed that $a_1\ne 1$ (if not then we just swap $a_1,a_2$). It is clear that $(a_n)$ is unbounded. Indeed, if $\max \{a_i:i\in \mathbb{N}\}=s$ then there must be at least $s+1$ equal numbers among $\{a_1,a_2,...,a_{s+1}\}$. Thus the next number is greater or equal to $s+1$. Contradiction. Now, assume that for $n\ge n_0$ sequence $(a_n+a_{n+1})$ is non-decreasing. Consider a number $k\ge n_0+1$ such that $a_k=t\ge \max \{a,b\}+1$ and this is the first number $t$ in the sequence. Obviously, all numbers before $a_k$ are lower than $t$. Then $a_{k+1}=1$ and since $(a_n+a_{n+1})$ is non-decreasing, it follows that $a_{k-1}=1$. Thus there exist exactly $t$ indexes $\{1<i_1<i_2<...<i_t=k-1\}$ such that $a_{i_1}=a_{i_2}=...=a_{i_t}=1$. Hence numbers $\{a_{i_1-1};a_{i_2-1};...,a_{i_t-1}\}$ are lower or equal to $t-1$ and there must be at least two equal numbers among $\{a_{i_1-1};a_{i_2-1};...,a_{i_t-1}\}$. Therefore, there must be at least two equal pairs $\{...,l,1,...\}$ in our sequence. However, after the second number $l$ it must be at least 2. Contradiction.