OMC144(E)

　$f(1)=a, f(2)=b$ とする．このとき $$f(3)=f(1)^2+f(2)^2=a^2+b^2, \quad f(4)=f(1)f(2)+f(2)f(3)=a^2b+ab+b^3$$ である．また，$f(5)=f(1)f(3)+f(2)f(4)=f(2)f(2)+f(3)f(3)$ であるから，代入して解くことで $a=1$ が分かる．従って，与式に $m=1$ を代入し， $$f(1)=1,\quad f(2)=b,\quad f(n+2)=f(n)+bf(n+1)$$ が任意の正の整数 $n$ について成立することがわかる．逆に，これらが成立するとき，$b$ によらず任意の正の整数 $m,n$（ただし $m\geq 2$ ）について， $$\begin{aligned} f(m)f(n) + f(m+1)f(n+1) &= f(m)f(n) + \bigl(f(m-1)+bf(m)\bigr)f(n+1) \\ &= f(m-1)f(n+1) + f(m)\bigl(f(n)+bf(n+1)\bigr) \\ &= f(m-1)f(n+1) + f(m)f(n+2) \end{aligned}$$ が成り立つことから，与式が満たされることが帰納的に確かめられるので，求める関数はある正の整数 $b$ に対して上の漸化式を満たす $f$ 全てである．
　このような関数の $f(4)$ の値は $b^3+2b$ であるから，$\left| f(4)-10^6\right|$ が最も小さくなるような $b$ の値は $100$ である．また，$3$ 以上の整数 $n$ について以下が成立するので，求める答えは $\bf{10001}$ である． $$\begin{aligned} \left\lfloor \dfrac{f(n+2)}{f(n)} \right\rfloor & = \left\lfloor\dfrac{f(n)+bf(n+1)}{f(n)} \right\rfloor \\ & = 1+b^2+ \left\lfloor \dfrac{bf(n-1)}{f(n)} \right\rfloor \\ & = 1+b^2 +\left\lfloor \dfrac{bf(n-1)}{f(n-2)+bf(n-1)} \right\rfloor \\ & = 1+b^2. \end{aligned}$$