1

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

102
0
$$$$

$\textbf{ISL2013-A5}$ $\mathrm{Let}\ \mathbb{Z}_{\geqslant 0}\mathrm {\ be \ the \ set \ of \ all \ nonnegative \ integers. Find\ all \ the \ functions\ }$ $f: \mathbb{Z}_{\geqslant 0} \rightarrow \mathbb{Z}_{\geqslant 0} $ $\mathrm{satisfying \ the \ relation}$
$$ f(f(f(n))) = f(n+1 ) +1\tag{1} $$
$\mathrm{for \ all}\ n\in \mathbb{Z}_{\geqslant 0}$.

$$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)=n+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の方を解くかも?).

投稿日:202329
更新日:118

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

kk2
kk2
54
7018
2006年に生まれました

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中