ISL 2023 N8

$f(1)=c$とする。
$ S=\{f^{c}(2),f^{2c}(2),f^{3c}(2),\cdots\}$と定める。 $P(a,b)$ で$a$を動かすことで$f$の値域は無限集合であり$ P(1,b)$ で$f^{bc}(2)=2f(b)$であるから$b$を動かすことで$ S$は無限集合となる。
$f(x)=f(y),x-y=k>0$となる正の整数$x,y$が存在したと仮定して矛盾を導く。
$ P(1,x),P(1,y)$より$f^{(y+k)c}(2)=f^{xc}(2)=f^{yc}(2)$である。また非負整数$n$において$f^{(y+k+n)c}(2)=f^{(y+n)c}(2)$が成り立つ。この等式を繰り返し用いることで任意の$b≧y$において$f^{bc}(2)$は$f^{yc}(2),f^{(y+1)c}(2),\cdots,f^{(y+k-1)c}(2)$のいずれかと値が同じであるから$ S$が無限集合であることと矛盾する。よって補題は示せた。

$ P(1,n)$より$f^{nc}(2)=2$であるから
$ f^{2nc}(2)=f^{nc}(2)=2$であるが$ P(1,2n)$から$2=f^{2nc}(2)=2f(2n)$
$⇒f(2n)=1=f(n)$これは単射性に矛盾する。

$(i)$に$b=1$を代入し単射性から$f(f(a)-1)-af(f(1)-1)>0⇒f^{f(f(a)-1)-af(f(1)-1)}(a)=1$ $f(f(a)-1)-af(f(1)-1)<0⇒f^{af(f(1)-1)-f(f(a)-1)}(1)=a$
$f(f(a)-1)-af(f(1)-1)=0⇒a=1$
1番上のときは補題2より矛盾であるので$a≠1$で$f^{af(f(1)-1)-f(f(a)-1)}(1)=a$を得る。$a$は任意に取れるので$f$の値域は$2$以上の全ての整数である。

$f^x(a)=f^y(a),x>y$と仮定して矛盾を示す。単射性から
$f^{x-y}(a)=a⇒f^{n(x-y)}(a)=a$
$a=1$なら補題2から矛盾だから$a>1$とする。$P(a-1,x-y)$から$a=f^{(x-y)f(a-1)}(a)=af(x-y)$
$⇒f(x-y)=1$補題2から矛盾。

$f^k(a)f(f(a)-1)=af(f^{k+1}(a)-1)+k $において$k=1$から$a$と$f(f(a)-1)$は互いに素であるから補題の主張はすぐに分かる。

$ P(a-1,b)$から
$f^{bf(a-1)}(a)=af(b)$で$f^{bf(a-1)}(a) $は$a$の倍数。補題5より
$bf(a-1)$は$a$の倍数、$b$は$a$と互いに素となるように取れば$f(a-1)$は$a$の倍数となる。

補題3より$f(t)=2$となる$t$が存在するが補題6から$f(a)≧a+1$であるから$2=f(t)≧t+1$より$t=1$。以下帰納法で示す。$f(n)=n+1$が$n≦k-1$で成り立つと仮定する。補題3より$f(t)=k+1$となる$t$が存在する。$k+1=f(t)≧t+1⇒k≧t,k>t$と仮定すると帰納法の仮定より$ t+1=f(t)=k+1$となり矛盾。よって$t=k,f(k)=k+1$となる。帰納法より$f(n)=n+1\quad\forall n\in\mathbb{Z}_{>0}$となる。
十分性はすぐに分かる。