China Mathematical Olympiad

We show by induction that for any integer $n>1$, $f(n)$ is uniquely determined by the value of $f(1)$, $f(2)$, $\dots$, $f(n-1)$, and $\frac{n}{2}\le f(n)\le n$.

For $n=2$, $f(2)=1$, the claim is true. Assume that for any $k$, $1\le k<n$ ($n\ge 3$), $f(k)$ is uniquely determined, and $\frac{k}{2}\le f(k)\le k$, then $1\le \frac{n-1}{2}\le f(n-1)\le n-1$, and $1\le n-f(n-1)\le n-1$, hence by induction hypothesis, the value of $f(f(n-1))$ and $f(n-f(n-1))$ is determined, and the value of $f(n)$, by definition, is $$f(n)=f(f(n-1))+f(n-f(n-1)),$$ which is uniquely determined. Furthermore, we have $$\begin{gathered} \frac{1}{2}f(n-1)\le f(f(n-1))\le f(n-1), \\ \frac{1}{2}(n-f(n-1))\le f(n-f(n-1))\le n-f(n-1). \end{gathered}$$ Equality above implies $\frac{n}{2}\le f(n)\le f(n-1)+(n-f(n-1))=n$. The claim is also true for $n$. By induction, we proved that there exists a unique function $f:N^{\ast }\to N^{\ast }$ satisfying the required properties, and $\frac{n}{2}\le f(n)\le n$.

Next, we show by induction that for any positive integer $n$, we have $$f(n+1)-f(n)\in \{0,1\}.$$ When $n=1$, this is true. Assume that it is true for $n\le k$. By the recurrence, $$\begin{array}{rl}& f(k+2)-f(k+1)\\ & =(f(f(k+1))+f(k+2-f(k+1)))-(f(f(k))+f(k+1-f(k)))\\ & =(f(f(k+1))-f(f(k)))+(f(k+2-f(k+1))-f(k+1-f(k))).\end{array}$$ By induction hypothesis, $f(k+1)-f(k)\in \{0,1\}$. If $f(k+1)=f(k)+1$, since $1\le f(k)\le k$, it follows, from above and induction hypothesis, that $$f(k+2)-f(k+1)=f(f(k)+1)-f(f(k))\in \{0,1\}.$$ If $f(k+1)=f(k)$, since $1\le k+1-f(k)\le k$, it follows from above and the induction hypothesis that $$f(k+2)-f(k+1)=f(k+2-f(k))-f(k+1-f(k))\in \{0,1\}.$$ Thus, the claim is true for $n=k+1$. By induction, it is true for any positive integer $n$.

Finally, we show by induction that for any positive integer $m$, we have $f(2^m)=2^{m-1}$. For $m=1$, the result is clear. Assume that the result is true for $m=k$, i.e., $f(2^k)=2^{k-1}$, consider the case for $m=k+1$. Assume on the contrary that $f(2^{k+1})\ne 2^k$, since $f(2^{k+1})\ge 2^k$, and $f(2^{k+1})$ is an integer, we have $f(2^{k+1})\ge 2^k+1$. Since $f(1)=1$, by the previous claim, let $n$ be the smallest integer such that $f(n)=2^k+1$, we have $n\le 2^{k+1}$, by the minimality of $n$, $f(n-1)=2^k$. Notice that $n-2^k\le 2^k$, we have $$2^k+1=f(n)=f(f(n-1))+f(n-f(n-1))=f(2^k)+f(n-2^k)\le 2f(2^k)=2^k,$$ which is a contradiction. It follows that $f(2^{k+1})=2^k$, the result is also true for $m=k+1$. By induction, $f(2^m)=2^{m-1}$ for any positive integer $m$.

$\boxed{f(2^m)=2^{m-1}}$ for integer $m\ge 2$.