トップ› 北海道大学› 2020年› 理系第2問

北海道大学 2020年理系第2問解説

方針・初手

(1) は、与えられた2点から直線の方程式を立て、それが一次不定方程式になることを利用して解く。ユークリッドの互除法などを用いて特殊解を1つ見つけ、一般解を求める。

(2) は、(1)で求めた一般解の座標を用いて、原点との距離の2乗を計算し、最小となる格子点を2つ特定する。後半は、特定された3点で構成される直角三角形内の格子点の個数を求める問題となる。格子点を含む長方形を考え、その対称性を利用することで効率よく個数を数えることができる。

解法1

(1)

直線 $l$ の方程式は、$x$ 切片が $\frac{1}{16}$、$y$ 切片が $\frac{1}{9}$ であるから、

$$ \frac{x}{\frac{1}{16}} + \frac{y}{\frac{1}{9}} = 1 $$

すなわち、

$$ 16x + 9y = 1 $$

である。この不定方程式の整数解を求める。

$16 = 9 \times 1 + 7$、$9 = 7 \times 1 + 2$、$7 = 2 \times 3 + 1$ より、

$$ 1 = 7 - 2 \times 3 = 7 - (9 - 7) \times 3 = 16 \times 4 - 9 \times 7 $$

となるため、$x = 4, y = -7$ は特殊解の1つである。したがって、

$$ 16 \times 4 + 9 \times (-7) = 1 $$

が成り立つ。辺々引いて、

$$ 16(x - 4) + 9(y + 7) = 0 $$

$$ 16(x - 4) = -9(y + 7) $$

$16$ と $9$ は互いに素であるから、$k$ を整数として、

$$ x - 4 = 9k $$

$$ y + 7 = -16k $$

と表せる。以上より、求める格子点の座標は、整数 $k$ を用いて

$$ (9k + 4, -16k - 7) $$

と表されるすべての点である。

(2)

(1)より、$l$ 上の格子点 $(9k + 4, -16k - 7)$ と原点との距離の2乗を $f(k)$ とすると、

$$ \begin{aligned} f(k) &= (9k + 4)^2 + (-16k - 7)^2 \\ &= 81k^2 + 72k + 16 + 256k^2 + 224k + 49 \\ &= 337k^2 + 296k + 65 \end{aligned} $$

これを平方完成すると、

$$ f(k) = 337 \left( k + \frac{148}{337} \right)^2 + 65 - \frac{148^2}{337} $$

放物線の軸は $k = -\frac{148}{337} = -0.43\cdots$ である。

$k$ は整数であるため、$f(k)$ が最小となるのは軸に最も近い整数 $k = 0$ のときであり、次に小さくなるのは $k = -1$ のときである。

$k = 0$ のとき、$(x, y) = (4, -7)$。距離の2乗は $f(0) = 65$。 $k = -1$ のとき、$(x, y) = (-5, 9)$。距離の2乗は $f(-1) = 337 - 296 + 65 = 106$。

よって、原点との距離が最小となる点 $A$ は $(4, -7)$、次に最小となる点 $B$ は $(-5, 9)$ である。これより、$A$ の $x$ 座標と $B$ の $y$ 座標からなる点 $C$ は $(4, 9)$ となる。

三角形 $ABC$ は、辺 $AC$ が $y$ 軸に平行、辺 $BC$ が $x$ 軸に平行な、$\angle C = 90^\circ$ の直角三角形である。ここで、点 $D(-5, -7)$ をとると、四角形 $ADBC$ は各辺が座標軸に平行な長方形となる。

この長方形の $x$ 座標は $-5 \le x \le 4$、 $y$ 座標は $-7 \le y \le 9$ であり、周上および内部に含まれる格子点の総数は、

$$ (4 - (-5) + 1) \times (9 - (-7) + 1) = 10 \times 17 = 170 \text{ （個）} $$

長方形は対角線 $AB$ の中点 $M \left( -\frac{1}{2}, 1 \right)$ を中心に点対称な図形である。

格子点 $(x, y)$ の $M$ に関する対称点は $(-1 - x, 2 - y)$ であり、これも整数となるため、長方形内の格子点の配置も $M$ に関して対称である。

対角線 $AB$ （線分 $AB$）上にある格子点は、$(9k + 4, -16k - 7)$ のうち $-5 \le 9k + 4 \le 4$ を満たすものであり、$k = 0, -1$ の2点（すなわち点 $A$ と点 $B$）のみである。

三角形 $ABC$ の内部および周上にある格子点の個数を $N$ とすると、対称性より三角形 $ABD$ の内部および周上にある格子点の個数も $N$ である。

長方形全体に含まれる格子点は、これら2つの三角形に含まれる格子点の和から、対角線 $AB$ 上で重複して数えられた格子点を引いたものに等しいため、

$$ 2N - 2 = 170 $$

これを解いて、

$$ N = 86 $$

したがって、三角形 $ABC$ の内部および周上にある格子点の個数は 86 個である。

解説

(1) は基本的な一次不定方程式の問題である。特殊解をいかに素早く見つけるかがポイントとなる。(2) の前半は、2次関数の最小値問題に帰着させることで処理できる。後半の格子点の個数を数える部分は、不等式を立てて $x$ や $y$ ごとに和の記号（シグマ）を用いて数え上げることも可能だが、直角三角形であることを利用して長方形を構成し、図形の対称性を用いると計算量を大幅に減らすことができる。ピックの定理を用いることも可能だが、今回のように辺が座標軸に平行な直角三角形であれば、対称性を利用する方が直感的で記述も簡潔になる。