2020 北海道大学理系数学 第2問

2020年 北海道大学理系数学 第2問の解説をしてみます。

サトゥー

エレガントな解法の類はやりません。あくまで、試験場で自分が解くとしたらどう考えるかな〜という観点で見ていますのでよろしくです

座標平面上の 2 点 $\left( \frac{1}{16}, 0 \right), \left( 0, \frac{1}{9} \right)$ を通る直線 $\ell$ を考える。

(1) $\ell$ 上にある格子点の座標をすべて求めよ。ただし、格子点とはその点の $x$ 座標と $y$ 座標がともに整数であるような点のことである。

(2) $\ell$ 上の格子点のうち、原点との距離が最小となる点を $\mathrm{A}$ とする。また $\ell$ 以外の格子点のうち、原点との距離が最小となる点を $\mathrm{B}$ とする。さらに、 $\mathrm{A}$ の $x$ 座標と $\mathrm{B}$ の $y$ 座標をそれぞれ $x$ 座標と $y$ 座標とする点を $\mathrm{C}$ とする。三角形 $\mathrm{ABC}$ の内部および周上にある格子点の個数を求めよ。

2020 北海道大学理系

解いてみた感想

標準的な整数問題、格子点の数え上げ問題。格子点自体も簡単な三角形についてなので、スピード感をもって確実に解き切りたい問題ではありますね。

(1) 1次の不定方程式を解く

直線 $\ell$ の方程式は $16x + 9y = 1$ とおけるので、この1次不定方程式の整数解を求めれば良いことがわかります。不定方程式の解き方は人によって様々ですが、ここでは例えば、

\begin{align*}
16(x-4) = -9 (y+7)
\end{align*}

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

\begin{align*}
x = -9k+4, y = 16k-7
\end{align*}

とできます。これが答え。

(2) 格子点の数え上げ

とりあえず原点との距離を $d(k)$ として、

\begin{align*}
(d(k))^2 & = (-9k+4)^2 + (16k-7)^2 \\
& = 337 k^2 – 296 l + 65 \\
& = 337 {\left( k + \frac{148}{337} \right)}^2 + 65 – \frac{148^2}{337}
\end{align*}

より、$k$ を連続変数とみなしてやれば、$d(k)$ は次のような下に凸、軸が $k = – \frac{148}{337}$ の放物線となり、この軸に近い $k$ ほど $d(k)$ が小さくなります。

そこで、改めて整数 $k$ を考えると、$d(k)$ が最小になる整数 $k$ は、 $-\frac{148}{337}$ に最も近い $k= 0$ であり、これが $\mathrm{A}$ に対応している。次に近い $k = -1$ が $\mathrm{B}$ に対応しています。

よって、

\begin{align*}
\mathrm{A} (4, -7), \mathrm{B} (-5, 9)
\end{align*}

これより $\mathrm{C} (4, 9)$ で、これらを図示すると次のようになります。

いまからこの三角形 $\mathrm{ABC}$ 内の格子点の個数を数えるのですが、計算を簡単にするために点 $\mathrm{D}(-5, -7)$ を導入します。

こうすることで、長方形 $\mathrm{ABDC}$ 内の格子点の個数を求めて対称性を利用することができます。具体的には、長方形内の格子点の個数が $10 \cdot 17 = 170$ 、線分 $\mathrm{AB}$ 上の格子点は $\mathrm{A}$ と $\mathrm{B}$ の 2 つだけ、よって求める格子点の個数は

\begin{align*}
\frac{170 – 2}{2} + 2 = 86
\end{align*}

となります。

📓 他の問題の解説

この記事を書いた人

サトゥー

東大学際情報学府M1。情報科学と教養の海に溺れています。面白いことをやるのがすきです。