函数 $f:\ \mathbb{Z}^+\rightarrow\mathbb{Z}^+$ 满足下列条件: (1) $f(n) < f(n+1)$, (2) $f(f(n))=3n$.求 $f(n)$.
函数 $f:\ \mathbb{Z}^+\rightarrow\mathbb{Z}^+$ 满足下列条件:
(1) $f(n) < f(n+1)$,
(2) $f(f(n))=3n$.
求 $f(n)$.
Remark:
题目来源: 周久儒
函数 $f:\ \mathbb{Z}^+\rightarrow\mathbb{Z}^+$ 满足下列条件:
(1) $f(n) < f(n+1)$,
(2) $f(f(n))=3n$.
求 $f(n)$.
Remark:
题目来源: 周久儒
1
The proof is provided by Jiuru Zhou.
Claim 1. $f(1)=2$.
Pf. 若 $f(1)=1$, 则 $f(f(1))=f(1)=1$. 而由条件 (2), 得 $f(f(1))=3$, 矛盾. 因此 $f(1)\geqslant 2$.
若 $k:=f(1) > 2$, 则 $f(k)=f(f(1))=3$. 结合条件 (1), 可得 $k\leqslant 1$. (事实上, $f(3) > f(2) > f(1) > 2$.) 矛盾.
因此 $f(1)=2$.
Claim 2. $f(3n)=3f(n)$.
Pf. 由条件 (2), $f(3n)=f\bigl(f(f(n))\big)=3f(n)$.
Claim 3. $f(n) > n$.
Pf. 由条件 (1) 及 Claim 1, 得 $1 < f(1)=2 < f(2) < f(3) < \cdots < f(n) < \cdots$, 因此 $f(n) > n$.
Claim 4. $f(2)=3$.
Pf. 由 Claim 3, $f(2) > 2$. 现假设 $a:=f(2) > 3$. 则 $f(a)=f(f(2))=3\cdot 2=6$. 又由 Claim 2, $f(3)=3f(1)=3\cdot 2=6$.
于是 $f(6)=f(f(a))=3a > 9$, 但另一方面 $f(6)=f(f(3))=3\cdot 3=9$. 矛盾. 因此 $f(2)=3$.
Claim 5. $f(3^k)=2\cdot 3^k$. $f(2\cdot 3^k)=3^{k+1}$.
Pf. 根据 Claim 1,2,4 即得.
Claim 6.
\[
\begin{cases}
f(3^k+j)=2\cdot 3^k+j,\quad\forall\ j=1,2,\ldots, 3^k.\\
f(2\cdot 3^k+j)=3^{k+1}+3j.\quad\forall\ j=1,2,\ldots, 3^k.\\
\end{cases}
\]
Pf.
\[
f(3^k) < f(3^k+1) < f(3^k+2) < \cdots < f(3^k+3^k-1) < f(2\cdot 3^k)
\]
由于 $f(3^k)=2\cdot 3^k$, $f(2\cdot 3^k)=3\cdot 3^k$, 故 $f(2\cdot 3^k)-f(3^k)=3^k$, 于是推出 $f(3^k+j)=2\cdot 3^k+j$.
于是
\[
f(2\cdot 3^k+j)=f(f(3^k+j))=3(3^k+j)=3^{k+1}+3j.
\]
证完.