今回解くのは，数学オリンピックの2024 代表選考合宿の問題です．
正の整数に対して定義され正の整数値を取る関数\(f\)であって，任意の正の整数\(a\)，\(b\)に対して \[f^{bf(a)}(a+1)=(a+1)f(b)\] が成り立つようなものをすべて求めよ．ただし，\(f^k(n)\)で\(\displaystyle \underbrace{f(f(\cdots f(n)\cdots))}_{k\text{個}}\)を表すものとする．
関数の反復があり，その反復回数にも\(f\)が入っています．
まずは小さい数をいくつか代入してみましょう． \[f^{f(a)}(a+1)=(a+1)f(1)\] \[f^{bf(1)}(2)=2f(b)\] \[f^{f(1)}(2)=2f(1)\] 反復回数に\(f\)が残るのでここから情報を得るのは難しそうです．
単射であることを示せるか見てみましょう．\(f(x)=f(x+y)\) \((y\neq0)\)とします．\(z\)を自由に取ります． \[\begin{aligned} (a+1)f(x+y+z)&=f^{(x+y+z)f(a)}(a+1)\\ &=f^{zf(a)}\circ f^{(x+y)f(a)}(a+1)\\ &=f^{zf(a)}\left((a+1)f(x+y)\right)\\ &=f^{zf(a)}\left((a+1)f(x)\right)\\ &=f^{zf(a)}\circ f^{xf(a)}(a+1)\\ &=f^{(x+z)f(a)}(a+1)\\ &=(a+1)f(x+z) \end{aligned}\] \(f(x+z)=f(x+y+z)\)となることがわかりました． \[\begin{aligned} (x+y+z+1)f(b)&=f^{bf(x+y+z)}(x+y+z+1)\\ &=f^{bf(x+y+z)-1}\circ f(x+y+z+1)\\ &=f^{bf(x+z)-1}\circ f(x+z+1)\\ &=f^{bf(x+z)}(x+z+1)\\ &=(x+z+1)f(b) \end{aligned}\] \(yf(b)=0\)となりました．しかし，\(y\neq0\)，\(f(b)\)も正整数なのでこれは矛盾です．
\(f\)は単射である．
不動点や周期点を持つか調べてみましょう．\(f^n(x)=x\)とします．\(x\)を1以外とします．\(y\)を自由に取ります． \[\begin{aligned} xf(ny)&=f^{nyf(x-1)}(x)\\ &=\left(f^n\right)^{yf(x-1)}(x)\\ &=x \end{aligned}\] \(f(ny)=1\)になりました．これは，\(f(n)=1=f(2n)\)となるので矛盾です．
\(f\)は1以外の周期点を持たない．
\(f\)で送って1になる数があるか考えます．\(f(n)=1\)とします． \[\begin{aligned} f^{nf(a)}(a+1)&=(a+1)f(n)\\ &=a+1 \end{aligned}\] \(a+1\)が周期点になってしまい矛盾です．
\(f(n)=1\)となる\(n\)は存在しない．
\(f\)は周期点を持たない．
\(f\)についての性質が少しわかってきましたが，まだ具体的な値などは一切わかってないです． 具体的な形を調べるために，\(f:\mathbb{N}_{>0}\to\mathbb{N}_{>0}\)を自然数の関数\(g:\omega\to\omega\)に拡張できると信じて計算してみましょう(#0は自然数)． 0は特殊なので，代入すると確定するものがあるかもしれません． \[g^0(a+1)=(a+1)g(0)\] \[g^{bg(0)}(1)=g(b)\] 1つ目の式から\(g(0)=1\)となります．\(g(n)=1\)となる\(n\)は0のみなので\(g\)も単射です．よって2つ目の式から\(g^{b-1}(1)=b\)がわかります． \[\begin{aligned} g(n)&=g\circ g^{n-1}(1)\\ &=g^n(1)\\ &=n+1 \end{aligned}\] \(g(n)=n+1\)を得ました．これが関数方程式を満たすか一応確認しておきましょう． \[\begin{aligned} g^{bg(a)}(a+1)&=g^{b(a+1)}(a+1)\\ &=a+1+b(a+1)\\ &=(a+1)(b+1)\\ &=(a+1)g(b) \end{aligned}\] \(g(n)=n+1\)が関数方程式を満たすことが確認できました．また，\(f=g|_{\mathbb{N}_{>0}}\)はもとの関数方程式の解です．
\(f(n)=n+1\)は解のうちの1つである．
\(f\)についての式に\(f(n)=n+1\)を代入して偽になるとき，その式はもとの関数方程式から導くことはできない．
この系は式変形などで複雑な式がでたとき，その過程が間違ってないか確認するのに役立ちます．合ってるか心配になったら\(f(n)=n+1\)を代入してみるといいでしょう．
未知の関数の反復を考えるのは難しいので，反復のない形の等式がほしいです．そこで，\(f^{mf(a)f((a+1)f(n)-1)}\circ f^{f(a)n}(a+1)\)という式を考えます． \[\begin{aligned} f^{mf(a)f((a+1)f(n)-1)}\circ f^{f(a)n}(a+1)&=f^{mf(a)f((a+1)f(n)-1)}((a+1)f(n))\\ &=((a+1)f(n))f(mf(a)) \end{aligned}\] \[\begin{aligned} f^{mf(a)f((a+1)f(n)-1)}\circ f^{f(a)n}(a+1)&=f^{f(a)(mf((a+1)f(n)-1)+n)}(a+1)\\ &=(a+1)f(mf((a+1)f(n)-1)+n) \end{aligned}\] これらを\(a+1\)で割ることで次の式が得られます．
任意の\(n\)，\(m\)，\(a\)に対し，\(f(n)f(mf(a))=f(mf((a+1)f(n)-1)+n)\)が成り立つ．
複雑な式がでてきましたが，\(f(n)=n+1\)を代入しても成り立つことから，大きなミスなどはしてないでしょう．
ここで，次の数を定義します．
\(\mathbb{P}=\min(\{n\in\mathbb{N}_{>0}|n\neq1,n< f(n-1)\}\cup\{\infty\})\)
これは，\(f\)がどこまで\(n+1\)と一致するかを表すもので，\(1< n< \mathbb{P}\)なら\(n=f(n-1)=f^{n-1}(1)\)，\(f^n(1)=f(n)\)です． \(\mathbb{P}=\infty\)のときは，任意の\(n\)で\(f(n)=n+1\)です． ちなみにこれがwell-definedであることは自然数全体の整列性からわかります． \(f\)の具体的な値は全くわかっていないので，\(\mathbb{P}\)についての仮定を追加して考えてみることにします．
まずは\(\mathbb{P}\)が合成数の場合を考えます．\(\mathbb{P}=ml\) \((1< m,l< \mathbb{P})\)とします． \[\begin{aligned} f(\mathbb{P}-1)&=f^{\mathbb{P}-1}(1)\\ &=f^{(m-1)l}\circ f^{l-1}(1)\\ &=f^{(m-1)f(l-1)}(l)\\ &=lf(m-1)\\ &=lm\\ &=\mathbb{P} \end{aligned}\] これは\(\mathbb{P}< f(\mathbb{P}-1)\)に反するので矛盾です．\(\mathbb{P}\)は合成数になりえないことがわかりました．
\(\mathbb{P}\)は素数もしくは\(\infty\)である．
また，上記の証明とほとんど同じ式変形により，このこともわかります．
\(n=ml\) \((1< m,l< \mathbb{P})\)のとき，\(f^{n-1}(1)=n\)が成り立つ．
考えていた証明にミスがあったのでまだ証明できていません．100未満の場合に成り立つことは確認したので多分成り立ちはします．
\(\mathbb{P}\)は\(\infty\)を除いて7以上になることはない．
\(\mathbb{P}\)としてありえるのは，\(\infty\)を除けば2,3,5のみです．\(\mathbb{P}=5\)の場合を調べてみましょう． この場合，\(f(1)=2,f(2)=3,f(3)=4,f(4)>5\)となります． \[\begin{aligned} f^2(4)&=f^4(2)\\ &=f^{2f(1)}(1+1)\\ &=(1+1)f(2)\\ &=f(1)f(1f(1))\\ &=f(1f((1+1)f(1)-1)+1)\\ &=f(f(3)+1)\\ &=f(5) \end{aligned}\] \(f\)は単射なので\(f(4)=5\)で仮定に反します．
\(\mathbb{P}\)は5ではない．
次は\(\mathbb{P}=3\)を仮定しましょう．\(f(1)=2,f(2)>3\)です．値がわかっているのが\(f(1)\)のみなので，ここから確定する情報は限られます． \[\begin{aligned} 4&=(1+1)f(1)\\ &=f^{1f(1)}(1+1)\\ &=f^2(2)\\ &=f^3(1) \end{aligned}\] \[\begin{aligned} f^2(4)&=f^4(2)\\ &=f^{2f(1)}(1+1)\\ &=(1+1)f(2)\\ &=f(1)f(1f(1))\\ &=f(1f((1+1)f(1)-1)+1)\\ &=f(f(3)+1)\\ \therefore f(4)&=f(3)+1 \end{aligned}\] \[\begin{aligned} 2f(4)&=2(f(3)+1)\\ &=(1+1)f(3)+2\\ &=f^{3f(1)}(1+1)+2\\ &=f^6(2)+2\\ &=f^7(1)+2 \end{aligned}\] 値が全然確定しません．倍数，約数にも注目してみましょう．\(f(4)\)が偶数であると仮定します． \[\begin{aligned} f^3(1)&=f(4)\\ &=2(a+1)\\ &=(a+1)f(1)\\ &=f^{1f(a)}(a+1) \end{aligned}\] 1は\(f\)の像に入らないので\(3>f(a)\)となる必要があります．こうなりうる\(a\)は1のみですが，その場合は\(f(4)=4\)で不動点を持たないことと矛盾します．つまり\(f(4)\)は奇数です． このことから，\(f^7(1)\)が4の倍数であるとわかります．4になることはありえないので，\(f^7(1)=4(a+1)\)と書けます． \[\begin{aligned} f^7(1)&=4(a+1)\\ &=(a+1)f(f(2))\\ &=f^{f(2)f(a)}(a+1) \end{aligned}\] これもさっきと同様に，\(7>f(2)f(a)\)となる必要がありますが，\(f(2)>3,f(a)\neq1\)より不可能です．
\(\mathbb{P}\)は3ではない．
残り考えるべきなのは\(\mathbb{P}=2\)，つまり\(f(1)\neq2\)の場合のみです． その場合を考える前に，\(f\)の一般的な性質についての補題を1つ証明します．\(f(n)\neq1\)なので，\(f(n)-1\)を考えることができます． \[\begin{aligned} f^{nf(f(1)-1)+1}(1)&=f^{nf(f(1)-1)}(f(1))\\ &=f(1)f(n)\\ &=f^{1f(f(n)-1)}(f(n))\\ &=f^{f(f(n)-1)+1}(n) \end{aligned}\] さっきまでと同様\(nf(f(1)-1)+1\ge f(f(n)-1)+1\) (\(n=1\)の場合は等号)となるので，\(f^{nf(f(1)-1))-f(f(n)-1)}(1)=n\)となります．
任意の正整数\(n\)に対し，ある自然数\(m\)が存在して\(n=f^m(1)\)となる．
\(f''\mathbb{N}_{>0}=\mathbb{N}_{>0}-\{1\}\)
\(f(1)\neq2\)と仮定します．\(f(1)\)が偶数だとします．\(f(1)\)は2ではないので1でない\(n\)を使って\(f(1)=2n\)と書けます．\(n\)は1でないのである\(m\)で\(n=f(m)\)と書けます． \[\begin{aligned} f(1)&=2n\\ &=(1+1)f(m)\\ &=f^{mf(1)}(1+1) \end{aligned}\] 1は\(f\)の像に入らないので矛盾です．よって\(f(1)\)は奇数です．次に，\(f^m(1)f^l(1)\)という式を考えます． \[\begin{aligned} f^m(1)f^l(1)&=f^{f^{l-1}(1)f(f^m(1)-1)}(f^m(1))\\ &=f^{m+f^{l-1}(1)f(f^m(1)-1)}(1)\\ f^{m+f^{l-1}(1)f(f^m(1)-1)}(1)&=f^{l+f^{m-1}(1)f(f^l(1)-1)}(1)\\ \therefore m+f^{l-1}(1)f(f^m(1)-1)&=l+f^{m-1}(1)f(f^l(1)-1) \end{aligned}\] ここから，\(m+l\)と\(f^{l-1}(1)f(f^m(1)-1)+f^{m-1}(1)f(f^l(1)-1)\)の偶奇は一致することがわかります．\(m=1,2\)，\(l=2n+2,2n+3\)の場合を考えます． \[\begin{aligned} 1f(f^{2n+2}(1)-1)+f^{2n+1}(1)f(f(1)-1)\ &:\text{奇数} \\ 1f(f^{2n+3}(1)-1)+f^{2n+2}(1)f(f(1)-1)\ &:\text{偶数} \\ f(1)f(f^{2n+2}(1)-1)+f^{2n+1}(1)f(f^2(1)-1)\ &:\text{偶数} \\ f(1)f(f^{2n+3}(1)-1)+f^{2n+2}(1)f(f^2(1)-1)\ &:\text{奇数} \end{aligned}\] \(f(1)\)は奇数で，奇数の積は偶奇を変えないのでこう書けます． \[\begin{aligned} f(f^{2n+2}(1)-1)+f^{2n+1}(1)f(f(1)-1)\ &:\text{奇数} \\ f(f^{2n+3}(1)-1)+f^{2n+2}(1)f(f(1)-1)\ &:\text{偶数} \\ f(f^{2n+2}(1)-1)+f^{2n+1}(1)f(f^2(1)-1)\ &:\text{偶数} \\ f(f^{2n+3}(1)-1)+f^{2n+2}(1)f(f^2(1)-1)\ &:\text{奇数} \end{aligned}\] 項がかぶっている行でそれぞれ足します． \[\begin{aligned} 2f(f^{2n+2}(1)-1)+f^{2n+1}(1)(f(f(1)-1)+f(f^2(1)-1))\ &:\text{奇数} \\ 2f(f^{2n+3}(1)-1)+f^{2n+2}(1)(f(f(1)-1)+f(f^2(1)-1))\ &:\text{奇数} \end{aligned}\] \(f^{2n+1}(1)\)と\(f^{2n+2}(1)\)はともに奇数になります．よって，任意の\(n\)に対し\(f^n(1)\)は奇数です．これは\(f^n(1)=2\)を満たす\(n\)の存在に反します．
\(\mathbb{P}\)は2ではない．
解は\(f(n)=n+1\)のみである．
この問題は本来は1時間半で解く問題のようです．自分は解くのに1週間以上かかってます... 1時間半でこの議論をするのは難しいのでもっとかんたんな方法があると思います．