Selection tests for the Balkan Mathematical Olympiad 2013

Let $n$ be a nonnegative integer. We have $$f(2n{)}^2<f(2n{)}^2+6f(n)+1=f(2n+1{)}^2<f(2n{)}^2+6f(2n)+9=(f(2n)+3{)}^2.$$ Therefore, $$f(2n)<f(2n+1)<f(2n)+3.$$ Assume that $f(2n+1)=f(2n)+2$. In this case $$6f(n)+1=f(2n+1{)}^2-f(2n{)}^2=4f(2n)+4.$$ This is impossible since the left hand side is odd while the right hand side is even. Therefore $f(2n+1)=f(2n)+1$.

On the other hand, $$6f(n)+1=f(2n+1{)}^2-f(2n{)}^2=2f(2n)+1.$$ We deduce that $f(2n)=3f(n)$, and $f(0)=0$.

Now, let $n\ge 0$ and write $n={\overline{a_1{a}_2\cdots a_k}}_{(2)}$ in basis 2. We prove by induction on $k$ that $f(n)={\overline{a_1{a}_2\cdots a_k}}_{(3)}$ in basis 3.

For $k=1$, we have $$f\left({\overline{0}}_{(2)}\right)=f(0)=0={\overline{0}}_{(3)}\text{and}f\left({\overline{1}}_{(2)}\right)=f(1)=f(0)+1=1={\overline{1}}_{(3)}.$$ Assume this true for $k$. We have $$\begin{array}{rl}f\left({\overline{a_1{a}_2\cdots a_k{a}_{k+1}}}_{(2)}\right)& =f\left(2{\overline{a_1{a}_2\cdots a_k}}_{(2)}+a_{k+1}\right)\\ & =f\left(2{\overline{a_1{a}_2\cdots a_k}}_{(2)}\right)+a_{k+1}\\ & =3f\left({\overline{a_1{a}_2\cdots a_k}}_{(2)}\right)+a_{k+1}\\ & =3{\overline{a_1{a}_2\cdots a_k}}_{(3)}+a_{k+1}\\ & ={\overline{a_1{a}_2\cdots a_k{a}_{k+1}}}_{(3)}\\ & .\end{array}$$ This completes the induction.

Applying this to 1000, we have $$1000={\overline{1101001}}_{(3)}=f\left({\overline{1101001}}_{(2)}\right)=f(105).$$