放物線と格子点のお話

放物線内を埋め尽くす！

$y = f_{n} (x) = n - x^{2} (n \in z, n ≧ 0)$ と $x$ 軸とで囲まれる領域とその領域の周によって作られる領域を $D_{n}$ とする。この時 $D_{n}$ に含まれる格子点を全て通るように軸が $y$ 軸と並行であるような二次関数を配置する時必要な二次関数の数のうち最も小さいものを $F_{n}$ とする。 $F_{n}$ を求めよ。
ただし格子点とは $x$ 座標と $y$ 座標がともに整数である点とする。

まず題意を満たす範囲にある格子点の数 $a_{n}$ を求める。
$n - x^{2} = 0$ となるのは $x = \pm \sqrt{n}$ となるときなので $m ≦ \sqrt{n} < m + 1 (m \in Z)$ なる $m$ を用いて $x = k (- m ≦ k ≦ m)$ 上の題意を満たす格子点は $(x, y) = (k, 0) (k, 1) (k, 2) \dots (k, n - k^{2})$
の計 $n - k^{2} + 1$ 個なのでこれを $- m$ から $m$ の範囲で足し合わせればよい。
$y = n - x^{2}$ は $y$ 軸で対称ゆえ
$\begin{aligned} a_{n} & = \sum_{k = - m}^{m} n - k^{2} + 1 \\ = (n + 1) + 2 \sum_{k = 1}^{m} n - k^{2} + 1 \\ = (2 m + 1) (n + 1) - \frac{1}{3} m (m + 1) (2 m + 1) \end{aligned}$
となり、特に $n = m^{2}$ の時
$a_{m^{2}} = \frac{1}{3} (2 m + 1) (2 m^{2} - m + 3)$

実際に $n = 4 (m = 2)$ を代入してみれば $a_{4} = 15$ であり図 $1$ からも $a_{4} = 15$ であることが伺える。
!FORMULA[28][36584035][0]の時 $n = 4$ の時

$y = f_{n} (x) = n - x^{2} (y ≧ 0)$ 上に存在する格子点の数を $b_{n}$ とした時 $a_{n} = \sum_{k = 0}^{n} b_{k}$

まず（当たり前だが） $0 ≦ i < j ≦ n$ を満たす $i, j (\in Z)$ に対して $y = f_{i} (x)$ と $y = f_{j} (x)$ が共有点を持たないことを示す。
$\begin{aligned} f_{j} (x) - f_{i} (x) & = (j - x^{2}) - (i - x^{2}) \\ = j - i (\neq 0) \end{aligned}$
よって $f_{j} (x) - f_{i} (x) \neq 0$ であるので $f_{i} (x)$ と $f_{j} (x)$ は共有点を持たない $\dots ①$

次に $f_{n} (x) < y < f_{n + 1} (x) \land y ≧ 0 \dots ②$ を満たす範囲に有利点が存在しないことを示す。
もし $②$ を満たす範囲に格子点が存在するならばその点の $x$ 座標は $- \sqrt{n + 1} ≦ x ≦ \sqrt{n + 1} \land x \in z \dots ③$
を必ず満たす。しかし $③$ を満たす $k$ を用意して $x = k$ 上で $②$ を満たす点について調べると $f_{n} (k) = n - k^{2}, f_{n + 1} (k) = n + 1 - k^{2}$ であり $n - k^{2} < y < n + 1 - k^{2}$ を満たす整数 $y$ が存在しない。
故に $②$ を満たす範囲に格子点は存在しない $\dots ④$
$①, ④$ より $D_{n}$ には含まれるが $D_{n - 1}$ には含まれないような点は全て $y = f_{n} (x) \land y ≧ 0$ 上に存在するこのような点の個数はまさに $b_{n}$ であるので $a_{n}$ と $b_{n}$ について次のような漸化式がもとまり
$a_{n} = a_{n - 1} + b_{n} ⟺ a_{n} = a_{0} + \sum_{k = 1}^{n} b_{k}$
また、 $a_{0} = b_{0}$ より
$\begin{aligned} a_{n} & = b_{0} + \sum_{k = 1}^{n} b_{k} \\ = \sum_{k = 0}^{n} b_{k} \end{aligned}$
補題 $1$ は示された $◼$

グラフを実際に眺めてみると感覚的にもわかりやすい！
!FORMULA[66][36584035][0]の場合 $n = 4$ の場合

補題 $1$ より次のことがわかる

F_{n}

上からの評価

$F_{n} ≦ n + 1$

補題 $1$ より $n + 1$ 個の放物線によって $D_{n}$ に含まれる格子点を全て通ることができるので $F_{n} ≦ n + 1$ となり、補題 $2$ は示された $◼$

F_{n}

下からの評価

$n + 1 ≦ F_{n}$

用意した二次関数が $D_{n}$ 上の格子点を全て通るには $D_{n} \land x = 0$ すなわち $D_{n}$ の $y$ 軸上の格子点を全て通る二次関数が用意した二次関数の中に存在することが必要である。
軸が $y$ 軸と並行であるような二次関数は $1$ 点でしか $y$ 軸と交点を持たないので、 $D_{n}$ の $y$ 軸上の格子点
$(x, y) = (0, 0), (0, 1), \dots, (0, n)$
計 $n + 1$ 個を全て通るためには二次関数が $n + 1$ 個必要である。よって用意した二次関数が $D_{n}$ 上の格子点を全て通るには $n + 1 ≦ F_{n}$ が必要なので補題 $3$ は示された $◼$

答え！

$F_{n} = n + 1$

補題 $2, 3$ より $n + 1 ≦ F_{n} ≦ n + 1 \dots$ ⭐︎である。 $F_{n}$ は整数であるので⭐︎を満たすような $F_{n}$ は $F_{n} = n + 1$ のみ！よって答えは $F_{n} = n + 1$

おまけ

補題 $1$ を用いて $a_{n}$ の数を求めてみる。
一般に先ほど用いた $m ≦ \sqrt{n} < m + 1 (m \in Z)$ なる $m$ を用いて $b_{n}$ は $b_{n} = 2 m + 1$ と表される。

$m ≦ \sqrt{n} < m + 1$ を満たす整数 $n$ は
$m ≦ \sqrt{n} < m + 1 ⟺ m^{2} ≦ n < (m + 1)^{2}$
より $2 m + 1$ 個存在するので $y = f_{m^{2}} (x), f_{m^{2} + 1}, f_{m^{2} + 3}, \dots, f_{(m + 1)^{2} - 1} (x)$ の $y ≧ 0$ の部分に含まれる格子点の数は
$\begin{aligned} \sum_{k = m^{2}}^{(m + 1)^{2} - 1} b_{k} & = \sum_{k = m^{2}}^{(m + 1)^{2} - 1} 2 m + 1 \\ = (2 m + 1) (2 m + 1) \\ = 4 m^{2} + 4 m + 1 \end{aligned}$
よって $n = N$ であり $N$ が $M ≦ \sqrt{N} < M + 1$ と表される時
$\begin{aligned} a_{N} & = \sum_{k = 0}^{N} b_{k} \\ = \sum_{k = 0}^{M - 1} {\sum_{i = k^{2}}^{(k + 1)^{2} - 1} b_{i}} + \sum_{k = M^{2}}^{N} b_{k} \\ = \sum_{k = 0}^{M - 1} (4 k^{2} + 4 k + 1) + \sum_{k = M^{2}}^{N} 2 M + 1 \\ = 1 + \sum_{k = 1}^{M - 1} (4 k^{2} + 4 k + 1) + (N - M^{2} + 1) (2 M + 1) \\ = 1 + \frac{1}{3} (4 M^{3} - M - 3) + (N - M^{2} + 1) (2 M + 1) \\ = (2 M + 1) (N + 1) - \frac{1}{3} M (M + 1) (2 M + 1) \end{aligned}$
と求まり、最初に $x = k$ で固定したものを足し合わせる方法の答えと一致することも確認できる。
(※Wolfram Alphaが計算したから間違いない　図 $3$ 参照)
愛してるよ！Wolfram Alpha！