f³(n)=f(n+1)+1 2013ISL-A5

$$f^4(n)=f(f(n)+1)+1=f(f(n+1)+1)$$なので，$$f(f(n)+1)=n+f(f(0)+1).$$よって，$$\begin{array}{}\text{(2)}& f^4(n)=n+c\end{array}$$ここで,$c=f(f(0)+1)+1$とした.同じように，$$f^5(n)=f(n+c)=f(n)+c.$$つまり,$f(0),f(1),\cdots ,f(c-1)$だけ決めればいい.$g:{\mathbb{Z}}_{⩾0}\to {\mathbb{Z}}_{⩾0},h:{\mathbb{Z}}_{⩾0}\to S(S=\{0,\cdots ,c-1\})$が一意に存在して，$$f(n)=cg(n)+h(n)(n⩾0)$$が成り立つ.特に，$$\begin{array}{}\text{(3)}& g(n+c)=g(n)+1,h(n+c)=h(n) \end{array}$$が成り立つ.$(2)$より，$$\begin{array}{}\text{(4)}& cg(n)+cg(h(n))+cg(h^2(n))+cg(h^3(n))+h^4(n)=n+c.\end{array}$$$c\mid h^4(n)-n$であるが,$0⩽r⩽c-1$に対して,$|h^4(r)-r|<c$なので，$$\begin{array}{}\text{(5)}& h^4(r)=r.\end{array}$$ $(4)$に$(5)$を使うと，$$\begin{array}{}\text{(6)}& g(r)+g(h(r))+g(h^2(r))+g(h^3(r))=1.\end{array}$$つまりは$g(r),g(h(r)),g(h^2(r)),g(h^3(r))$のうち$1$つが$1$で他は$0$.$(5)$より,$h(S)=\{h(x):x\in S\}=S$なのを考えると,$c$は$4$の倍数で,$A=\{r\in S:g(r)=1\}$とすると.$\left|A\right|=\frac{c}{4}$が分かる.軽く説明しておくと,$S$上に二項関係$\sim$を以下のように定義すると:
$$x\sim y⟺\mathrm{\exists }n\in {\mathbb{Z}}_{>0},x=h^n(y)$$$\sim$は同値関係である.任意の$a$に対して,$|C(a)|=4$で$x\in C(r)$が一意に存在して,$g(x)=1$をみたすことを考えればいい.さて,$(1)$に$h(r)$を代入すると，$$cg(h(r))+cg(h^2(r))+cg(h^3(r))+h^4(r)=cg(h(r)+1)+h(h(r)+1)+1.$$これに,$(5),(6)$を使うと，$$c[g(r)+g(h(r)+1)-1]=r-h(h(r)+1)-1.$$特に,$c\mid r-h(h(r)+1)-1$であり,$0<r<c$においては,$|r-h(h(r)+1)-1|<c$なので，$$\begin{array}{}\text{(7)}& h(h(r)+1)=r-1,g(r)+g(h(r)+1)=1(0<r<c).\end{array}$$また,$r=0$のときは,$-c⩽0-h(h(0)+1)-1<0$なので，$$\begin{array}{}\text{(8)}& h(h(0)+1)=c-1,g(0)=g(h(0)+1)=0.\end{array}$$$h(x)=c-1$をみたす$0⩽x<c$が一意に存在し,そのような$x$を$l$としたとき$l\ne 0$である.なぜなら,$h(0)=c-1$なら,$g(c)=0$となり,$(3)$より矛盾するからである.$(7),(8)$より,$g(l)=0,h(0)+1=l$.$B=S\setminus \{0,l\}$として,$C_0=\{b\in B:g(b)=0\},C_1=\{b\in B:g(b)=1\}$とおく.このとき,$|C_0|=|C_1|=\frac{|B|}{2}=\frac{c-2}{2}$が成り立つ.ここも一応説明すると,$h^{\prime }:B\to B;x\mapsto h(x)+1$とすると,$(7)$より以下がわかる.
$$h^{\prime 2}(b)=b,g(b)+g(h^{\prime }(b))=1.$$$B$上に二項関係${\sim }^{\prime }$を以下のように定義すると:
$$x{\sim }^{\prime }y⟺\mathrm{\exists }n\in {\mathbb{Z}}_{>0},x=h^{\prime n}(y)$$${\sim }^{\prime }$は同値関係である.こっから先は,さっきのと同じ.さて,$|C_1|=|A|$なので,$\frac{c-2}{2}=\frac{c}{4}\mathrm{i}.\mathrm{e}.c=4$.$h(0)=0$なら,$h$に不動点は存在しないのでだめ.$h(0)=2$なら,$f(0)=2$で$f(f(0)+1)=f(3)=3=c-1$で$h(3)=3$はだめ.$h(0)=3$は普通にだめ.よって,$h(0)=1$.$(8)$より,$h(2)=3$.$h(1)=0$なら$h^2(0)=0$でだめ.よって,$(h(0),h(1),h(2),h(3))=(1,2,3,0)$.あとは,$g(1)=1,g(3)=1$のそれぞれの時で,代入すれば$f$はこの$2$つしかないことが分かる.具体的に,$f(n)=n+i(n-4\lfloor \frac{n}{4}\rfloor )(i(0)=1,i(1)=2+{\epsilon }_1,i(2)=3,i(3)={\epsilon }_3,\{{\epsilon }_1,{\epsilon }_3\}=\{0,4\})$

おわり

有名な一変数のFEでした.次は丁寧な解答編です(2014の方を解くかも？).