设 $\mathbf{N}$ 表示自然数集合，$f : \mathbf{N} \rightarrow \mathbf{N}$ 适合条件：$f(1)=1$，且对任何自然数 $n$ 都有
$\left\{\begin{array}{l}{3 f(n) f(2 n+1)=f(2 n)(1+3 f(n))} \\ {f(2 n)<6 f(n)}\end{array}\right.$
试求方程 $f(k)+f(l)=293, k<l$ 的所有解．
$\left\{\begin{array}{l}{3 f(n) f(2 n+1)=f(2 n)(1+3 f(n))} \\ {f(2 n)<6 f(n)}\end{array}\right.$
试求方程 $f(k)+f(l)=293, k<l$ 的所有解．
【难度】
【出处】
1995第10届CMO试题
【标注】
【答案】
略
【解析】
因3 $f(n)$ 与 $1+3 f(n)$ 互质，故由已知等式 $3 f(n) f(2 n+1)=f(2 n)(1+3 f(n))$ 得 $3 f(n) | f(2 n)$ 又 $f(2 n)<6 f(n)$，故 $f(2 n)=3 f(n)$ ①
$f(2 n+1)=1+3 f(n)$ ②
设 $n=2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_{m}}$ 为 $n$ 的二进制展开式（$a_{m}>a_{m-1}>\cdots>a_{1}$，为非负整数），以下证明 $f(n)=3^{{a}_{1}}+3^{a_{2}}+\cdots+3^{a_m}$ ③
当 $n=1$ 时 ③ 即为条件 $f(1)=1$．
设 ③ 在 $n<2s$ 时成立，则当 $n=2s$ 时，设 $s=2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_m}$，则 $\begin{aligned} f(2 s)=& 3 f(s)=3\left(3^{a_{1}}+3^{a_{2}}+\cdots+3^{a_{m}}\right)= 3^{a_{1}+1}+3^{a_{2}+1}+\cdots+3^{a_{m}+1} \end{aligned}$ 而 $2 s+1=1+2^{a_{1}+1}+\cdots+2^{a_{m}+1}$
故 $n=2s+1$ 时式 ③ 也成立．证得式 ③ 对一切 $n$ 成立．因 $293=3^{5}+3^{3}+2 \times 3^{2}+3+2 \times 1$ 故 $\left\{\begin{aligned} f(l) &=3^{5}+3^{3}+3^{2}+3+1,3^{5}+3^{3}+3^{2}+1,3^{5}+3^{2}+3+1 , 3^{5}+3^{2}+1 \\ f(k) &=3^{2}+1,3^{2}+3+1,3^{3}+3^{2}+1,3^{3}+3^{2}+3+1 \end{aligned}\right.$
既满足题设的 $(k, l)=(5,47),(7,45),(13,39),(15,37)$．
$f(2 n+1)=1+3 f(n)$ ②
设 $n=2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_{m}}$ 为 $n$ 的二进制展开式（$a_{m}>a_{m-1}>\cdots>a_{1}$，为非负整数），以下证明 $f(n)=3^{{a}_{1}}+3^{a_{2}}+\cdots+3^{a_m}$ ③
当 $n=1$ 时 ③ 即为条件 $f(1)=1$．
设 ③ 在 $n<2s$ 时成立，则当 $n=2s$ 时，设 $s=2^{a_{1}}+2^{a_{2}}+\cdots+2^{a_m}$，则 $\begin{aligned} f(2 s)=& 3 f(s)=3\left(3^{a_{1}}+3^{a_{2}}+\cdots+3^{a_{m}}\right)= 3^{a_{1}+1}+3^{a_{2}+1}+\cdots+3^{a_{m}+1} \end{aligned}$ 而 $2 s+1=1+2^{a_{1}+1}+\cdots+2^{a_{m}+1}$
故 $n=2s+1$ 时式 ③ 也成立．证得式 ③ 对一切 $n$ 成立．因 $293=3^{5}+3^{3}+2 \times 3^{2}+3+2 \times 1$ 故 $\left\{\begin{aligned} f(l) &=3^{5}+3^{3}+3^{2}+3+1,3^{5}+3^{3}+3^{2}+1,3^{5}+3^{2}+3+1 , 3^{5}+3^{2}+1 \\ f(k) &=3^{2}+1,3^{2}+3+1,3^{3}+3^{2}+1,3^{3}+3^{2}+3+1 \end{aligned}\right.$
既满足题设的 $(k, l)=(5,47),(7,45),(13,39),(15,37)$．
答案
解析
备注
