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.