设 $f,g:\mathbb{N}^{\ast}\rightarrow \mathbb{N}^{\ast}$ 是严格递增函数，且 $f(\mathbb{N}^{\ast})\bigcup g(\mathbb{N}^{\ast})=\varnothing,g(n)=f(f(n))+1$．求 $f(240)$．（英国）
【难度】
【出处】
1978年第20届IMO试题
【标注】
【答案】
略
【解析】
设 $A=\{f(k)\},B=\{g(k)\},k\in\mathbb{N}^{\ast}$．
每个正整数或在 $A$ 中或在 $B$ 中，但不能同时在二者之内．当 $k\ne 1$ 时，$f(1)$ 小于 $f(k)$ 和 $g(k)$，所以 $f(1)=1$．
又由题意知，第 $n$ 个不在 $A$ 中的正整数是 $g(n)=f(f(n))+1$，故在正整数片段 $1~g(n)$ 中有 $n$ 个值不在 $B$ 中，有 $f(n)$ 个值在 $A$ 中，因此有 $f(n)+n=g(n)$，或 $f(f(n))=f(n)+n-1.$
利用这个递推公式及 $f(1)=1$，可得
$\begin{aligned}
f(1)=1,g(1)&=2,f(2)=3\\
f(f(2))=f(3)&=f(2)+2-1=4\\
f(f(3))=f(4)&=f(3)+3-1=6\\
f(f(4))=f(6)&=f(4)+4-1=9\\
f(f(6))=f(9)&=f(6)+6-1=14\\
f(f(9))=f(14)&=f(9)+9-1=22\\
f(f(14))=f(22)&=f(14)+14-1=35\\
f(f(22))=f(35)&=f(22)+22-1=56\\
f(f(35))=f(56)&=f(35)+35-1=90\\
g(35)=f(f&(35))+1=91\\
f(57)&=92\\
f(f(57))=f(92)&=f(57)+57-1=148\\
f(f(92))=f(148)&=f(92)+92-1=239\\
f(f(148))=f(239)&=f(148)+148-1=386\\
g(148)=f(f(148))&+1=f(239)+1=387\\
\end{aligned}$
所以 $f(240)=388$．
说明：其实这两个函数的表达式为 $f(n)=\left[\dfrac{\sqrt{5}+1}{2}n\right],g(n)=\left[\dfrac{\sqrt{5}+3}{2}n\right]$．
这是下面贝特（Betty）定理的特例．
贝特定理：若两个无理数 $\alpha,\beta$ 均大于 $1$，且满足 $\dfrac{1}{\alpha}+\dfrac{1}{\beta}=1$，则函数 $f(n)=[n\alpha],g(n)=[n\beta]$ 满足
（1）$f(n),g(n)$ 是 $\mathbb{N}^{\ast}\rightarrow \mathbb{N}^{\ast}$ 上的递增函数；
（2）$f(\mathbb{N}^{\ast})\bigcup g(\mathbb{N}^{\ast})=\mathbb{N}^{\ast}$；
（3）$f(\mathbb{N}^{\ast})\bigcap g(\mathbb{N}^{\ast})=\varnothing$．
在本题中，$\alpha=\dfrac{\sqrt{5}+1}{2},\beta=\dfrac{\sqrt{5}+3}{2}$．
每个正整数或在 $A$ 中或在 $B$ 中，但不能同时在二者之内．当 $k\ne 1$ 时，$f(1)$ 小于 $f(k)$ 和 $g(k)$，所以 $f(1)=1$．
又由题意知，第 $n$ 个不在 $A$ 中的正整数是 $g(n)=f(f(n))+1$，故在正整数片段 $1~g(n)$ 中有 $n$ 个值不在 $B$ 中，有 $f(n)$ 个值在 $A$ 中，因此有 $f(n)+n=g(n)$，或 $f(f(n))=f(n)+n-1.$
利用这个递推公式及 $f(1)=1$，可得
$\begin{aligned}
f(1)=1,g(1)&=2,f(2)=3\\
f(f(2))=f(3)&=f(2)+2-1=4\\
f(f(3))=f(4)&=f(3)+3-1=6\\
f(f(4))=f(6)&=f(4)+4-1=9\\
f(f(6))=f(9)&=f(6)+6-1=14\\
f(f(9))=f(14)&=f(9)+9-1=22\\
f(f(14))=f(22)&=f(14)+14-1=35\\
f(f(22))=f(35)&=f(22)+22-1=56\\
f(f(35))=f(56)&=f(35)+35-1=90\\
g(35)=f(f&(35))+1=91\\
f(57)&=92\\
f(f(57))=f(92)&=f(57)+57-1=148\\
f(f(92))=f(148)&=f(92)+92-1=239\\
f(f(148))=f(239)&=f(148)+148-1=386\\
g(148)=f(f(148))&+1=f(239)+1=387\\
\end{aligned}$
所以 $f(240)=388$．
说明：其实这两个函数的表达式为 $f(n)=\left[\dfrac{\sqrt{5}+1}{2}n\right],g(n)=\left[\dfrac{\sqrt{5}+3}{2}n\right]$．
这是下面贝特（Betty）定理的特例．
贝特定理：若两个无理数 $\alpha,\beta$ 均大于 $1$，且满足 $\dfrac{1}{\alpha}+\dfrac{1}{\beta}=1$，则函数 $f(n)=[n\alpha],g(n)=[n\beta]$ 满足
（1）$f(n),g(n)$ 是 $\mathbb{N}^{\ast}\rightarrow \mathbb{N}^{\ast}$ 上的递增函数；
（2）$f(\mathbb{N}^{\ast})\bigcup g(\mathbb{N}^{\ast})=\mathbb{N}^{\ast}$；
（3）$f(\mathbb{N}^{\ast})\bigcap g(\mathbb{N}^{\ast})=\varnothing$．
在本题中，$\alpha=\dfrac{\sqrt{5}+1}{2},\beta=\dfrac{\sqrt{5}+3}{2}$．
答案
解析
备注
