トップ› 九州大学› 2024年› 理系第4問

九州大学 2024年理系第4問解説

方針・初手

与えられた領域内の格子点を $S_n = \{ (x,y) \mid x, y は整数, 1 \le x \le n, 1 \le y \le n \}$ とおく。直線が $S_n$ 内の点を複数通るとき、その直線上の隣接する格子点の間の $x$ 座標の差を $p$、$y$ 座標の差を $q$ とすると、$(p, q)$ は互いに素な整数の組となる（直線の傾きは $q/p$ であり、$p=0$ のときは $y$ 軸に平行）。方向を区別するため、$p \ge 0$ として一般性を失わない。$p=0$ のときは $q=1$ とする。

ある直線が $S_n$ 内の点を 3 個以上通るためには、その直線上の最も離れた 2 点の $x$ 座標の差は少なくとも $2p$、$y$ 座標の差は少なくとも $2|q|$ となる。 $S_n$ の $x$ 座標および $y$ 座標の最大の差はそれぞれ $n-1$ であるため、3 点以上を通るための必要条件は

$$ 2p \le n-1 \quad \text{かつ} \quad 2|q| \le n-1 $$

となる。各 $n$ において、この不等式を満たす互いに素な整数の組 $(p, q)$ を絞り込み、それぞれに対応する直線の本数を数え上げる。

解法1

(1) $n=3$ のとき、必要条件は $2p \le 2$ かつ $2|q| \le 2$、すなわち $0 \le p \le 1$ かつ $|q| \le 1$ である。これを満たす互いに素な組 $(p, q)$ は、$(1,0), (0,1), (1,1), (1,-1)$ の 4 方向である。

それぞれの方向について、3 点を通る直線の本数を数える。

$(p,q) = (1,0)$（$x$ 軸に平行）のとき $y=1, 2, 3$ の 3 本。
$(p,q) = (0,1)$（$y$ 軸に平行）のとき $x=1, 2, 3$ の 3 本。
$(p,q) = (1,1)$（傾き $1$）のとき両端の座標の差が $x, y$ ともに $2 \times 1 = 2$ となるので、両端の点は $(1,1)$ と $(3,3)$ のみ。この 2 点を通る直線 $y=x$ 上には $(2,2)$ も存在し、3 点を通る。よって 1 本。
$(p,q) = (1,-1)$（傾き $-1$）のとき同様に、両端が $(1,3)$ と $(3,1)$ となる直線 $y=-x+4$ の 1 本。

以上より、$L(3) = 3 + 3 + 1 + 1 = 8$ となる。

(2) $n=4$ のとき、必要条件は $2p \le 3$ かつ $2|q| \le 3$、すなわち $0 \le p \le \frac{3}{2}$ かつ $|q| \le \frac{3}{2}$ である。 $p, q$ は整数であるから、$0 \le p \le 1$ かつ $|q| \le 1$ となり、方向 $(p, q)$ は $n=3$ のときと同じく $(1,0), (0,1), (1,1), (1,-1)$ に限られる。

$(p,q) = (1,0)$ のとき $y=1, 2, 3, 4$ の 4 本。
$(p,q) = (0,1)$ のとき $x=1, 2, 3, 4$ の 4 本。
$(p,q) = (1,1)$ のとき直線の方程式を $y=x+k$ （$k$ は整数）とおく。この直線上の点が $S_4$ に含まれる条件は $1 \le x \le 4$ かつ $1 \le x+k \le 4$ である。これを満たす整数 $x$ が 3 個以上存在する $k$ を探す。 $k=0$ のとき $x=1, 2, 3, 4$ の 4 点を通る。 $k=1$ のとき $x=1, 2, 3$ の 3 点を通る。 $k=-1$ のとき $x=2, 3, 4$ の 3 点を通る。よって、該当する直線は 3 本である。
$(p,q) = (1,-1)$ のとき対称性より、$(1,1)$ のときと同様に 3 本存在する。

以上より、$L(4) = 4 + 4 + 3 + 3 = 14$ となる。

(3) $n=5$ のとき、必要条件は $2p \le 4$ かつ $2|q| \le 4$、すなわち $0 \le p \le 2$ かつ $|q| \le 2$ である。これを満たす互いに素な組 $(p, q)$ は以下の 8 方向である。

$$ (1,0), (0,1), (1,1), (1,-1), (2,1), (2,-1), (1,2), (1,-2) $$

それぞれの方向について数え上げる。

$(1,0)$ 方向、$ (0,1)$ 方向 $y=1, 2, 3, 4, 5$ の 5 本、および $x=1, 2, 3, 4, 5$ の 5 本。計 10 本。
$(1,1)$ 方向、$ (1,-1)$ 方向 $(1,1)$ について、直線 $y=x+k$ 上の点が $S_5$ に含まれる条件は $1 \le x \le 5$ かつ $1 \le x+k \le 5$ である。これを満たす整数 $x$ が 3 個以上存在するのは、$-2 \le k \le 2$ のときであり、合計 5 本存在する。対称性から $(1,-1)$ 方向も 5 本。計 10 本。
$(2,1)$ 方向直線を媒介変数 $t$ を用いて $x = x_0 + 2t, y = y_0 + t$ （$t$ は整数）と表す。この直線が $S_5$ 内の格子点を 3 点以上通るとき、連続する 3 点の $x$ 座標は $x_0, x_0+2, x_0+4$ となる。これらがすべて $1$ 以上 $5$ 以下に収まる必要があり、$1 \le x_0 < x_0+2 < x_0+4 \le 5$ を満たす整数 $x_0$ は $x_0=1$ のみである。（このとき $x$ 座標は $1, 3, 5$）対応する $y$ 座標は $y_0, y_0+1, y_0+2$ となり、$1 \le y_0 < y_0+1 < y_0+2 \le 5$ を満たす整数 $y_0$ は $y_0 = 1, 2, 3$ の 3 通りである。よって、該当する直線は 3 本。
$(2,-1)$ 方向、$ (1,2)$ 方向、$ (1,-2)$ 方向対称性により、これらの方向の直線もそれぞれ 3 本ずつ存在する。計 $3 \times 3 = 9$ 本。

以上より、$L(5) = 10 + 10 + 3 + 9 = 32$ となる。

解説

格子点を通る直線の本数を数え上げる典型的な問題である。やみくもに直線を引いて数えるのではなく、「3 点以上を通るための条件」を数式（隣接する格子点の座標の差）に落とし込むことで、見落としなく確実にカウントできる。

直線上の隣接格子点の座標の差を互いに素な整数 $(p, q)$ とおいたとき、一直線上に $k$ 個の格子点が並ぶためには、領域の $x$ 方向の幅が $(k-1)p$ 以上、$y$ 方向の幅が $(k-1)|q|$ 以上必要であるという事実が本問の核心である。これにより、傾きの候補を論理的に絞り込むことができる。