证明存在唯一的函数 $f : Z_{+} \rightarrow Z_{+}$ 满足 $f(1)=f(2)=1,f(n)=f(f(n-1))+f(n-f(n-1))(n \geqslant 3)$ ①
并对每个整数 $m\geqslant 2$，求 $f(2^m)$ 的值．
并对每个整数 $m\geqslant 2$，求 $f(2^m)$ 的值．
【难度】
【出处】
2013第29届CMO试题
【标注】
【答案】
略
【解析】
由 $f(1)=1$，知 $\frac{1}{2} \leqslant f(1) \leqslant 1$．
首先用数学归纳法证明：对任意的整数 $n> 1$，$f(n)$ 可由 $f(1), f(2), \cdots, f(n-1)$ 的值唯一确定，且 $\dfrac{n}{2} \leqslant f(n) \leqslant n$ ②
当 $n=2$ 时，$f(2)= 1$，结论成立．
假设对任意的整数 $k(1 \leqslant k<n(n \geqslant 3))$，$f(k)$ 的值唯一，且 $\dfrac{k}{2} \leqslant f(k) \leqslant k$．
则 $1 \leqslant \dfrac{n-1}{2} \leqslant f(n-1) \leqslant n-1\Rightarrow 1 \leqslant n-f(n-1) \leqslant n-1$．
故由归纳假设知 $f(f(n-1)) $ 与 $ f(n-f(n-1))$ 的值唯一确定．
从而，$f(n)$ 可由式 ① 唯一确定．
又 $\dfrac{1}{2} f(n-1) \leqslant f(f(n-1)) \leqslant f(n-1)$，$\dfrac{1}{2}(n-f(n-1)) \leqslant f(n-f(n-1)) \leqslant n-f(n-1)$
故由式 ① 知 $\dfrac{n}{2} \leqslant f(n) \leqslant n$．
因此，结论对 $n$ 也成立．
由数学归纳法，知存在唯一的函数 $f : \mathbf{Z}_{+} \rightarrow \mathbf{Z}_{+}$ 满足条件，且 $\dfrac{n}{2} \leqslant f(n) \leqslant n$．
其次证明：对任意的正整数 $n$ 有 $f(n+1)-f(n) \in\{0,1\}$ ③
当 $n=1$ 时，结论 ③ 成立．
假设结论 ③ 在 $ n\leqslant k$ 时成立．由式 ① 知
$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)) ④ $
由归纳假设知 $f(k+1)-f(k) \in\{0,1\}$．
（1）$f(k+1)=f(k)+1$．
由于 $1 \leqslant f(k) \leqslant k$，于是，由式 ④ 及归纳假设知
$f(k+2)-f(k+1)=f(f(k)+1)-f(f(k)) \in\{0,1\}$．
（2）$f(k+1)=f(k)$．
注意到，$1 \leqslant k+1-f(k) \leqslant k$．
千是，由式 ④ 及归纳假设知
$f(k+2)-f(k+1)=f(k+2-f(k))-f(k+1-f(k)) \in\{0,1 \}$
因此，结论 ③ 在 $n =k + 1 $ 时也成立．
由数学归纳法，知结论 ③ 对一切正整数 $n$ 成立．
最后证明：对任意的正整数 $m $ 有 $f(2^m)=2^{m-1}$．
当 $m=1$ 时，结论成立．
假设 $m=k$ 时，结论成立，即 $f\left(2^{k}\right)=2^{k-1}$．
接下来考虑 $m =k + 1$ 时的情形．
假如 $f\left(2^{k+1}\right) \neq 2^{k}$．
由式 ② 知 $f\left(2^{k+1}\right) \geqslant 2^{k}$，而 $f\left(2^{k+1}\right)$ 为整数，故 $f\left(2^{k+1}\right) \geqslant 2^{k}+1$．
又 $f(1)= 1$，于是，由结论 ③ 知存在一个最小 的正整数 $n \leqslant 2^{k+1}$，使得 $f(n)=2^{k}+1$．进而，由 $n$ 的最小性得 $f(n-1)=2^{k}$．
再注意到，$n-2^{k} \leqslant 2^{k}$．故 $2^{k}+1=f(n)=f(f(n-1))+f(n-f(n-1))=f\left(2^{k}\right)+f\left(n-2^{k}\right) \leqslant 2 f\left(2^{k}\right)=2^{k}$，矛盾（最后两步应用了结论 ③ 及归纳假设）．
因此，$f\left(2^{k+1}\right)=2^{k}$，即 $m=k+1$ 时结论亦 成立
由数学归纳法，知对任意的正整数 $m$ 有 $f\left(2^{m}\right)=2^{m-1}$．
首先用数学归纳法证明：对任意的整数 $n> 1$，$f(n)$ 可由 $f(1), f(2), \cdots, f(n-1)$ 的值唯一确定，且 $\dfrac{n}{2} \leqslant f(n) \leqslant n$ ②
当 $n=2$ 时，$f(2)= 1$，结论成立．
假设对任意的整数 $k(1 \leqslant k<n(n \geqslant 3))$，$f(k)$ 的值唯一，且 $\dfrac{k}{2} \leqslant f(k) \leqslant k$．
则 $1 \leqslant \dfrac{n-1}{2} \leqslant f(n-1) \leqslant n-1\Rightarrow 1 \leqslant n-f(n-1) \leqslant n-1$．
故由归纳假设知 $f(f(n-1)) $ 与 $ f(n-f(n-1))$ 的值唯一确定．
从而，$f(n)$ 可由式 ① 唯一确定．
又 $\dfrac{1}{2} f(n-1) \leqslant f(f(n-1)) \leqslant f(n-1)$，$\dfrac{1}{2}(n-f(n-1)) \leqslant f(n-f(n-1)) \leqslant n-f(n-1)$
故由式 ① 知 $\dfrac{n}{2} \leqslant f(n) \leqslant n$．
因此，结论对 $n$ 也成立．
由数学归纳法，知存在唯一的函数 $f : \mathbf{Z}_{+} \rightarrow \mathbf{Z}_{+}$ 满足条件，且 $\dfrac{n}{2} \leqslant f(n) \leqslant n$．
其次证明：对任意的正整数 $n$ 有 $f(n+1)-f(n) \in\{0,1\}$ ③
当 $n=1$ 时，结论 ③ 成立．
假设结论 ③ 在 $ n\leqslant k$ 时成立．由式 ① 知
$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)) ④ $
由归纳假设知 $f(k+1)-f(k) \in\{0,1\}$．
（1）$f(k+1)=f(k)+1$．
由于 $1 \leqslant f(k) \leqslant k$，于是，由式 ④ 及归纳假设知
$f(k+2)-f(k+1)=f(f(k)+1)-f(f(k)) \in\{0,1\}$．
（2）$f(k+1)=f(k)$．
注意到，$1 \leqslant k+1-f(k) \leqslant k$．
千是，由式 ④ 及归纳假设知
$f(k+2)-f(k+1)=f(k+2-f(k))-f(k+1-f(k)) \in\{0,1 \}$
因此，结论 ③ 在 $n =k + 1 $ 时也成立．
由数学归纳法，知结论 ③ 对一切正整数 $n$ 成立．
最后证明：对任意的正整数 $m $ 有 $f(2^m)=2^{m-1}$．
当 $m=1$ 时，结论成立．
假设 $m=k$ 时，结论成立，即 $f\left(2^{k}\right)=2^{k-1}$．
接下来考虑 $m =k + 1$ 时的情形．
假如 $f\left(2^{k+1}\right) \neq 2^{k}$．
由式 ② 知 $f\left(2^{k+1}\right) \geqslant 2^{k}$，而 $f\left(2^{k+1}\right)$ 为整数，故 $f\left(2^{k+1}\right) \geqslant 2^{k}+1$．
又 $f(1)= 1$，于是，由结论 ③ 知存在一个最小 的正整数 $n \leqslant 2^{k+1}$，使得 $f(n)=2^{k}+1$．进而，由 $n$ 的最小性得 $f(n-1)=2^{k}$．
再注意到，$n-2^{k} \leqslant 2^{k}$．故 $2^{k}+1=f(n)=f(f(n-1))+f(n-f(n-1))=f\left(2^{k}\right)+f\left(n-2^{k}\right) \leqslant 2 f\left(2^{k}\right)=2^{k}$，矛盾（最后两步应用了结论 ③ 及归纳假设）．
因此，$f\left(2^{k+1}\right)=2^{k}$，即 $m=k+1$ 时结论亦 成立
由数学归纳法，知对任意的正整数 $m$ 有 $f\left(2^{m}\right)=2^{m-1}$．
答案
解析
备注
