Silk Road Mathematics Competition

We first prove that: $$(1)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$

$$\begin{gathered} a(n+1)-a(n)=a(a(n))-a(a(n-1))+a(n+1-a(n))-a(n-a(n-1))= \\ =\{\begin{array}{ll}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{array} \end{gathered}$$ 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.