一道有趣的函數方程

$求f:mathbb{Z}_{ge 0} ightarrowmathbb{Z}_{ge 0},forall ninmathbb{Z}_{ge 0},f(f(f(n)))=f(n+1)+1 ag{1}$

（題源為IMO 2013 shortlist A5）

從封塵已久的競賽筆記中翻出了這道函數方程，現在看來這道題的解法依然不常規，但相當有趣

$egin{align} &解：記f^{(k)}(n)為f(n)的k次迭代，令A_{k}={f^{(k)}(n)|ninmathbb{Z}_{ge 0}},\&則mathbb{Z}_{ge 0}=A_{0}supseteq A_{1}supseteq A_{2}supseteqcdots\& 由(1)式,f^{(3)}(n)=f(n+1)+1,故f^{(4)}(n)=f(f(n+1)+1)\ &在(1)式中令n=f(n+1)，則f^{(4)}(n+1)=f(f(n+1)+1)+1\ &比較上面兩式，得f^{(4)}(n+1)=f^{(4)}(n)+1 ag{2}\ &故forall ain A_{4},a+1in A_{4}\ & hereforemathbb{Z}_{ge 0}ackslash A_{4}為有限集 end{align}$

首先先從映射的角度考慮問題，證明單射/滿射是一種常見思路

$egin{align} &先證：f是單射\ &反設不然，則exists m>n,f(m)=f(n)\ &由(1)式和數學歸納法可知,forall kinmathbb{N},f(m+k)=f(n+k)\ &故當x充分大時,f(x)是周期函數,因此A_{1}是有限集，\&這與A_{4}是無限集矛盾！ herefore f是單射 end{align}$

下一步的思路就不那麼常規了

$egin{align} &令S_{k}=A_{k-1}ackslash A_{k}(kinmathbb{N})\ &ecause mathbb{Z}_{ge 0}ackslash A_{4}=S_{1}cup S_{2}cup S_{3}cup S_{4} quad herefore S_{1},S_{2},S_{3},S_{4}均為有限集\ &ecause f是單射 quad herefore |S_{1}|=|f(S_{1})|=|f(f(S_{1}))|=cdots\ & herefore|S_{1}|=|S_{2}|=|S_{3}|=cdots(每f一次使值域集合減少的元素個數相等)\ &接下來我們研究S_{1}cup S_{2}cup S_{3}的元素的性質\ &i)若0in A_{3},則exists n,0=f^{(3)}(n)=f(n+1)+1,矛盾！\ &hspace{1.9ex} 因此0 otin A_{3},故0in S_{1}cup S_{2}cup S_{3}\ &ii)在(1)式中令n=0,得f(0)+1in S_{1}cup S_{2}cup S_{3}\& iii)若bin S_{1}cup S_{2}cup S_{3},且b e 0,f(0)+1,則必有b-1in S_{1}\&hspace{3.3ex} 否則b-1in A_{1},可設f(t)=b-1(tgeq 1),則b=f(t)+1=f^{(3)}(t-1)in A_{3},矛盾！\ \& 設|S_{1}|=|S_{2}|=|S_{3}|=r,\&則3r=|S_{1}cup S_{2}cup S_{3}|leq 1+1+r(分別對應上述三類情況)Rightarrow r=1\&設S_{1}={a},則S_{2}={f(a)},S_{3}={f(f(a))}\ & herefore{a,f(a),f(f(a))}=S_{1}cup S_{2}cup S_{3}={0,f(0)+1,a+1} end{align}$

至此我們取得了重大突破，接下來只需耐心討論和計算即可

$egin{align} &若a+1=f(f(a)),則f(a+1)=f^{(3)}(a)=f(a+1)+1,矛盾！\ &又a+1 e a,故f(a)=a+1\& i)a=0,則f(0)=1,f(1)=f(0)+1=2\ &hspace{1.9ex}由數學歸納法易證f(n)=n+1(ninmathbb{Z}_{ge 0})\ &ii)a=f(0)+1,則f(f(a))=0,故f(a+1)=0,f(0)=f^{(3)}(a)=f(a+1)+1=1\ & herefore a=2,f(3)=0,f(2)=3\ &由(1)(2)兩式,f(4)=f(f(2)+1)=f^{(4)}(1)=f^{(4)}(0)+1=f^{(3)}(1)+1=f(2)+2=5\ &故f(1)=f(f(0))=f^{(3)}(3)=f(4)+1=6\& 下用第二數學歸納法證明：f(x)=egin{cases} x+1(x=4k,4k+2)\ x+5(x=4k+1)\ x-3(x=4k+3) end{cases}\ &k=0時,由上知成立\ &假設leq k-1時,結論均成立\ &k時,f(4k)=f^{(3)}(4k-1)-1=f(f(4k-4))-1=f(4k-3)-1=4k+1\ &ecause f(4k+3)=f(f(4k-3)+1)=f^{(4)}(4k-4)=f^{(3)}(4k-3)=f(f(4k+2))\ & herefore 由f是單射,得f(4k+2)=4k+3\ &ecause f(4k)=f(f(4k-2)+1)=f^{(4)}(4k-3)=f^{(3)}(4k+2)=f(f(4k+3))\ & herefore 由f是單射,得f(4k+3)=4k\& f(4k+1)=f(f(4k))=f^{(3)}(4k+3)=f(4k+4)+1=f(f(4k+2)+1)+1\&hspace{9.5ex} =f^{(4)}(4k+1)+1=f^{(4)}(4k-1)+3=f^{(3)}(4k-4)+3\&hspace{9.5ex}=f(f(4k-3))+3=f(4k+2)+3=4k+6,成立 end{align}$