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).$$よって，$$f^4(n)=n+c\tag{2}$$ここで,$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_{\geqslant0}\rightarrow\mathbb Z_{\geqslant0},h:\mathbb Z_{\geqslant0}\rightarrow S \ (S=\{0,\cdots,c-1\})$が一意に存在して，$$f(n)=cg(n)+h(n)\ (n\geqslant0)$$が成り立つ.特に，$$　g(n+c)=g(n)+1,h(n+c)=h(n)\tag{3}　$$が成り立つ.$(2)$より，$$cg(n)+cg(h(n))+cg(h^2(n))+cg(h^3(n))+h^4(n)=n+c. \tag{4}$$$c\mid h^4(n)-n$であるが,$0\leqslant r\leqslant c-1$に対して,$\left| h^4(r)-r\right|< c$なので，$$h^4(r)=r. \tag{5}$$ $(4)$に$(5)$を使うと，$$g(r)+g(h(r))+g(h^2(r))+g(h^3(r))=1. \tag{6}$$つまりは$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\Longleftrightarrow \exists n\in\mathbb Z_{>0},x=h^n(y)$$$\sim$は同値関係である.任意の$a$に対して,$\left|C(a)\right|=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$なので，$$h(h(r)+1)=r-1,g(r)+g(h(r)+1)=1 \ (0< r< c).\tag{7}$$また,$r=0$のときは,$-c\leqslant0-h(h(0)+1)-1<0$なので，$$h(h(0)+1)=c-1,g(0)=g(h(0)+1)=0.\tag{8}$$$h(x)=c-1$をみたす$0\leqslant x< c$が一意に存在し,そのような$x$を$l$としたとき$l\ne0$である.なぜなら,$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':B\rightarrow B;x\mapsto h(x)+1$とすると,$(7)$より以下がわかる.
$$h'^2(b)=b,g(b)+g(h'(b))=1.$$$B$上に二項関係$\sim'$を以下のように定義すると:
$$x\sim'y \Longleftrightarrow \exists n\in\mathbb Z_{>0},x=h'^n(y)$$$\sim'$は同値関係である.こっから先は,さっきのと同じ.さて,$|C_1|=|A|$なので,$\frac{c-2}{2}=\frac{c}{4}\ \mathrm{i.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)=\left\lfloor\frac{n}{4}\right\rfloor+i(n-4\left\lfloor\frac{n}{4}\right\rfloor) \ (i(0)=1,i(1)=2+\varepsilon_1,i(2)=3,i(3)=\varepsilon_3,\{\varepsilon_1,\varepsilon_3\}=\{0,4\})$

おわり

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