コンテストリレーDay5のL問題の「愚直な」解法

(1)
与式に$(m, n)=(1, 1)$を代入することで$f(1)+1\mid f(1)^2+2f(1)+f(1)$, $f(1)+1\mid 2$が成り立つ. $f(1)\geq 1$より$f(1)=1$である.

(2)
$(m, n)=(n, 1)$を代入すると$f(n)+1\mid f(n)^2+2n+1$. $f(n)\equiv -1\pmod {f(n)+1}$に注意すると$f(n)+1\mid 2n+2$.

(3)
$(m, n)=(n, n)$を代入すると$f(n)+n\mid f(n)^2+2nf(n)+f(n^2)$であり, $f(n)\equiv -n\pmod {f(n)+n}$であるから
$$ \begin{align*} f(n)^2+2nf(n)+f(n^2)&\equiv n^2-2n^2+f(n^2)\pmod {f(n)+n}\\ \implies f(n^2)&\equiv n^2\pmod {f(n)+n}. \end{align*} $$

定理1の(2)より$f(2)+1\mid 6$であるから, $f(2)=1, 2, 5$.

$f(2)=1$の場合, 定理1の(3)より$f(4)\equiv 4\pmod 3$. また$(m, n)=(1, 2)$とすれば$3\mid 1+2+f(4)$より$3\mid f(4)$. これは矛盾.

$f(2)=5$の場合, $f(4)\equiv 4\pmod 7$. $f(4)+1\mid 10$と併せて$f(4)=4$. $(m, n)=(3, 2)$とすれば, $f(3)+2\mid 38$であり, また定理1の(2)より$f(3)+1\mid 10$であるが, これをともに満たす$f(3)$は存在しない.

よって$f(2)=2$である. また, $f(4)\equiv 4\pmod 4$及び$f(4)+1\mid 10$から$f(4)=4$.

$(m, n)=(n, 2)$とすれば$f(n)+2\mid f(n)^2+4n+4$で例によって$f(n)\equiv -2\pmod {f(n)+2}$なので, $f(n)+2\mid 4n+8$.

定理1の(2)より, $f(n)+1\mid 2n+2$であるから, $f(n)+1=2n+2$を棄却できれば, $f(n)+1\leq n+1$, $f(n)\leq n$が示される.

$f(s)+1=2s+2$なる正整数$s$が存在したと仮定する. このとき, 定理2より
$$ f(s)+2\mid 4s+8\implies 2s+3\mid 4s+8\implies 2s+3\mid 2 $$
となるがこれは不可能. よって$f(n)+1\neq 2n+2$である. $2n+2$の約数は大きい順に$2n+2, n+1, \dots$なので$f(n)+1\leq n+1$, よって$f(n)\leq n$である.

$(m, n)=(t, s)$を代入すれば$s+t\mid t^2+2t^2+f(s^2)$であり, 定理1の(3)より$f(s^2)\equiv s^2\equiv t^2\pmod {s+t}$であるので$s+t\mid 4t^2$であり, 故に$4t^2>s$である.

$s>25$を仮定する.

$k^2< s$なる任意の正整数$k$に対し, $t+k\mid 2t(s-t)$が成立する(先ほどの議論). このとき$k=1, 2, 3, 4, 5$は必ず取ることができる.

$t\equiv 0, 1\pmod 3$のとき, $t+1, t+2, t+3, t+4$の最小公倍数は$(t+1)(t+2)(t+3)(t+4)/2$である(※).

また, $t\equiv 2\pmod 3$のとき, $t+2, t+3, t+4, t+5$の最小公倍数は$(t+2)(t+3)(t+4)(t+5)/2$である(※).

よって, $t\pmod 3$によらず
$$ \begin{align*} (t+1)(t+2)(t+3)(t+4)/2&\leq 2t(s-t)< 8t^3\\ t^4+10t^3+35t^2&\leq 16t^3 \end{align*} $$
である(一段目最後の不等式は定理4を用いた)が, これが満たされることはない.

よって, $s\leq 25$である.