Problem 1337

We first prove that:
$$(1) \qquad a(n+1) - a(n) = 0 \text{ or } 1$$
for all positive integers $n$. It is true if $n = 1, 2$, since $a(3) = 2$. Assume that $n \ge 3$ and (1) is true for all $k \le n$. In particular, $1 \le a(k) \le k$ for all $k \le n$

$$a(n+1) - a(n) = a(a(n)) - a(a(n-1)) + a(n+1 - a(n)) - a(n - a(n-1)) = \\ = \begin{cases} a(n - a(n) + 1) - a(n - a(n)), & \text{if } a(n) = a(n-1), \\ a(a(n-1) + 1) - a(a(n-1)), & \text{if } a(n) = a(n-1) + 1, \end{cases}$$
and (1) follows by induction.

Now assume that $a(2n) \le 2a(n)$ not for all $n \ge 1$, and let $m$ be the smallest integer for which this inequality is false. Hence, $a(2m) > 2a(m)$ and $a(2(m-1)) \le 2a(m-1)$. Moreover, if $a(m) = a(m-1)+1$, then $a(2m) > 2a(m) = 2(a(m-1)+1) \ge a(2(m-1))+2$ and we get a contradiction to (1). Therefore, $a(m) = a(m-1)$.

Let $M = a(m) = a(m-1)$. Since $a(2m) > 2M$ and $a(2m-2) \le 2M$, we have $a(2m-1) = 2M$ or $2M+1$.

If $a(2m-1) = 2M$, then $a(2m) = a(2M) + a(2m-2M) \le 2a(M) + 2a(m-M) = 2a(m)$, which contradicts with our assumption $a(2m) > 2a(m)$.

If $a(2m-1) = 2M+1$, then $a(2m-2) = 2M$ and $a(2m-1) = a(2M) + a(2m-1-2M) \le a(2M) + a(2m-2M) \le 2a(M) + 2a(m-M) = 2a(m)$, which means $2M+1 \le 2M$, a contradiction.