NF杯2024のS問題を微分方程式を用いて解く

はじめに

　先日行われた NF杯2024 の S問題 を近似と微分方程式を用いて解きます．正確な評価はしません．

本文

　$x>0$が十分小さいとき\begin{equation} \sqrt{1+x}=1+\frac{1}{2}x-\frac{1}{8}x^2+O(x^3) \end{equation}
が成り立つことに注意すると，$k>0$が十分小さいとき\begin{align} x_3&=\frac{314+\sqrt{314^2+1256k-4k^2}}{2}\\ &=\frac{314}{2}\left(1+\sqrt{1+\frac{2}{157}k-\frac{1}{157^2}k^2}\right)\\ &=\frac{314}{2}\left(1+1+\frac{1}{2}\left(\frac{2}{157}k-\frac{1}{157^2}k^2\right)-\frac{1}{8}\left(\frac{2}{157}k-\frac{1}{157^2}k^2\right)^2+O(k^3)\right)\\ &=314+k-\frac{k^2}{157}+O(k^3) \end{align}
となり，$x_2$と$x_3$の値はかなり近くなる．ここで$x_i$と$x_{i+1}$の差$\varepsilon_i$が小さい場合を考えてみる．\begin{align} x_{i+2}&=\frac{x_i+\varepsilon_i+\sqrt{(x_i+\varepsilon_i)^2+4x_i(x_i+\varepsilon_i)-4x_i^2}}{2}\\ &=\frac{x_i+\varepsilon_i+\sqrt{x_i^2+6x_i\varepsilon_i+\varepsilon_i^2}}{2}\\ &=\frac{x_i+\varepsilon_i+x_i\sqrt{1+\frac{6\varepsilon_i}{x_i}+\frac{\varepsilon_i^2}{x_i^2}}}{2}\\ &=x_i+2\varepsilon_i-\frac{2\varepsilon_i^2}{x_i}+O\left(\frac{\varepsilon_i^3}{x_i^2}\right) \end{align}
となるから$k$が十分小さいとき数列$\{x_n\}$は単調増加数列であり，その差分を取った数列$\{\Delta x_n\}=\{x_{n+1}-x_n\}$は各項が小さな正の値かつ単調減少な数列とわかる．$\varepsilon_i$を$x_{i+1}-x_i$に戻すと\begin{align} &x_{i+2}=2x_{i+1}-x_i-\frac{2(x_{i+1}-x_i)^2}{x_i}\\ &\Leftrightarrow((x_{i+2}-x_{i+1})-(x_{i+1}-x_i))=-\frac{2(x_{i+1}-x_i)^2}{x_i} \end{align}となる．この差分方程式を微分方程式\begin{equation} \frac{d^2y}{dt^2}=-2\left(\frac{dy}{dt}\right)^2y^{-1}\quad y(0)=314,\ \frac{dy}{dt}(0)=k \end{equation}と見て考える．両辺を$\displaystyle\frac{dy}{dt}$で割って$t$で積分することで\begin{equation} \log\frac{dy}{dt}=\log y^{-2}+(\text{定数}) \end{equation}を得るので初期条件を踏まえて\begin{equation} y=\sqrt[3]{3\cdot314^2kt+314^2} \end{equation}と分かる．$y(t)=2024$となる$t$を$t_0$とすると\begin{equation} kt_0=\frac{2024^3-314^3}{3\cdot314^2} \end{equation}であり，これが求める値である．

おわりに

　差分方程式を微分方程式と見ても解答が一致するのは，$\{\Delta x_n\}$(あるいは$\displaystyle\frac{dy}{dt}$)がほとんど一定であることと平均値の定理より\begin{equation} y(i+1)-y(i)=\frac{dy}{dt}(c)\quad(i\leq c\leq i+1) \end{equation}となる$c$が存在することをイメージすると分かりやすい気がします．

追記

　作問者のU.N.Owenさんが何点級の問題か意見が欲しいとおっしゃっていたので私見を書くと700点級，Difficultyは橙下位程度だと思います．青solverが3時間ほどかけて解いたのであまり当てにならないかもしれません．