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
$$\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).$$
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^* \to N^*$ 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{align*} & 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{align*}$$
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$.