PILAME杯2026 day1 P4

関数方程式,整数問題

123

はじめに

　PILAME杯本番で解けなかった問題をその日の夜に解いたので，そのときの解法を書きます．

PILAME杯2026 day1 P4

　正の整数に対して定義され正の整数値をとる関数$f$であって，任意の正の整数$m,n$に対して
$$　f(m+f(n))^2 - 4f(m)n$$
が平方数になるものを全て求めよ．

解法

　解は$f(n)=n$のみです．これを示します．以下では与式に$(m,n)=(m^{\prime},n^{\prime})$を代入したものを$P(m^{\prime},n^{\prime})$と表します．

不等式評価

　まず，平方数の離散性で不等式が立てられそうなので，これで$f(n)$についての不等式を得ます．

平方数の離散性

　正の整数$a,b$について，$a^2-4b$が平方数ならば$a \leq b+1$．

　$a^2-4b$は$a^2$と偶奇が等しく，かつ$a^2$未満の平方数なので$(a-2)^2$以下である．$a^2-4b \leq (a-2)^2$を整理して$a \leq b+1$を得る．

　$f(1)=c$とおく．ある正の整数$d$が存在して，任意の$n$について$f(n) \leq \dfrac{n}{c} + d$が成り立つ．

　$P(m,1)$と補題1より，$f(m+c) \leq f(m)+1$が成り立つ．これを繰り返し用いることで任意の$m,k$について$f(m+ck) \leq f(m)+k$が成り立つため，$d=\max(f(1),f(2),\ldots,f(c))$とし，$n=ck+l ~ (1 \leq l \leq c)$とおくと，
$$f(n) = f(ck+l) \leq f(l)+k \leq d+\dfrac{n}{c}$$
より示された．

　命題2だけでも色々分かりそうだと思ったのですが，何も得られなかったので別の議論をすることにしました．

素因数の議論

　なぜ素因数の議論がうまくいくかというと，次のことが分かるからです．

　$p$を奇素数とする．$m \gt f(p)$かつ$f(m)$が$p$の倍数ならば，$f(m-f(p))$も$p$の倍数である．

　$P(m-f(p),p)$より$f(m)^2-4f(m-f(p))p$は平方数で，かつ$p$で割り切れるので，$p^2$でも割り切れる．$p \neq 2$であるから$f(m-f(p))$は$p$で割り切れる．

　これと命題2を使って$f(1)$の議論をします．以下，$f$の行き先とは$\{f(n) ~ | ~ n=1,2,\ldots \}$を指します．

　$f$の行き先に含まれる素因数が無限個あれば，$f(1)=1$．

　命題2より十分大きな素数に対しては$f(p) \lt p$が成り立ち，仮定より$f(m)$がそのような$p$で割り切れる$m$が存在する．命題3を繰り返し用いることで，$1 \leq m-kf(p) \leq f(p)$となるような$k$について$f(m-kf(p))$が$p$の倍数，特に$p$以上になるため，命題2より
$$p \leq f(m-kf(p)) \leq \dfrac{f(p)}{c}+d \lt \dfrac{p}{c}+d$$
である．$p$はいくらでも大きくできるため，$c=1$がいえる．

　なので，$f$の行き先に含まれる素因数が無限個あることをいえば$f(1)=1$が示せます．与式には$f$がかかってない$n$があるので，それをいい感じに設定することで矛盾を導きます．

　$f$の行き先に含まれる素因数は無限個ある．

　有限個だと仮定し，それらを$p_1,p_2,\ldots,p_s$とおく．$P(1,n)$より$f(f(n)+1)^2-4cn$は平方数である．ここで$n_f$を次のように定める．

$k=1,2,\ldots,s$について$v_{p_k}(4cn)$が奇数となるような$n$．

　このとき，$k=1,2,\ldots,s$について$v_{p_k}(f(f(n)+1)^2) \neq v_{p_k}(4cn)$であり，$v_{p_k}(f(f(n)+1)^2-4cn)$は偶数であるから，$v_{p_k}(f(f(n)+1)^2) \lt v_{p_k}(4cn)$だが，このとき$f(f(n)+1)^2 \lt 4cn$であるため矛盾する．よって示された．

　$f(1)=1$．

　命題4と命題5より．

最後の詰め

　$f(1)=1$が言えたので後は簡単です．任意の$n$について$f(n)=n$ならば$f(m+f(n))^2 - 4f(m)n = (m-n)^2$なので，$n,m$が近いときの不等式を使うと良さそうだと分かります．

　任意の$n$について$f(n) \leq n$．

　$P(m,1)$と補題1より，$f(m+1) \leq f(m)+1$が成り立つため，これを繰り返し用いれば良い．

　任意の$n$について$f(n) = n$．

　$n=1$のときは良い．$n=1,2,\ldots,l-1$で成り立つならば$n=l$でも成り立つことを示す．
　$l$が偶数のとき，$P \big(\dfrac{l}{2},\dfrac{l}{2} \big)$より$f(l)^2-l^2 \geq 0$である．命題7とあわせて$f(l)=l$．
　$l$が奇数のとき，$P \big(\dfrac{l-1}{2},\dfrac{l+1}{2} \big)$より$f(l)^2-l^2+1 \geq 0$である．命題7とあわせて$f(l)=l$．
　よって示された．