数学A / 場合の数

格子点が作る三角形の個数

最難関編数え上げ共線点

問題

座標平面上の25個の格子点 $(x, y)$ ( $x, y$ は $0$ 以上 $4$ 以下の整数)から異なる3点を選ぶ。選んだ3点が三角形の頂点になる選び方は何通りあるか。

ヒントを見る

引くべき「一直線の3点」を、点の側からでなく直線の側から整理できるか。横・縦・45°のほかに、3つの格子点が乗る直線はもうないか — 傾きが整数や1/2になる場合をもう一度探してみると。

解答・解説

3点の選び方の総数から、一直線上に並ぶ3点の選び方を引く。共線な3点は「3点以上を含む直線」ごとに数える: 横・縦・傾き±1に加えて、見落としやすい傾き±2、±1/2 の直線がある。

⓪ 発想 — どう考え始めるか。 三角形を直接数えるのは無理筋で、全体から退化(3点が一直線)を引くのが定石だ。

勝負は共線な3点の数え上げにある。これは「3点以上を含む直線」を全部リストアップし、直線ごとに(その上の点数から3点を選ぶ)組合せを足せばよい。

横・縦・傾き $\pm 1$ まではすぐ見える。だがこの格子には、傾き $\pm 2$ と $\pm \frac{1}{2}$ の直線にも3点が並ぶ。ここを見落とすと答えがずれる。

重要三角形の個数 =(3点の選び方)−(共線な3点の選び方)。共線は「直線ごとに

_{m} C_{3}

」で漏れなく数える

① 全体。 25点から3点:

$_{25} C_{3} = \frac{25 \cdot 24 \cdot 23}{6} = 2300 通り$

② 共線な3点を直線ごとに数える。

横の直線5本・縦の直線5本(各5点): $2 \times 5 \times_{5} C_{3} = 2 \times 5 \times 10 = 100$
傾き $\pm 1$ : 各向きに5点の直線1本、4点の直線2本、3点の直線2本で $_{5} C_{3} + 2 \cdot_{4} C_{3} + 2 \cdot_{3} C_{3} = 10 + 8 + 2 = 20$ 。両向きで $40$
傾き $\pm 2$ と $\pm \frac{1}{2}$ : たとえば傾き2は $(0, 0), (1, 2), (2, 4)$ のように3点がちょうど乗る直線が3本。4方向で $4 \times 3 \times_{3} C_{3} = 12$

見落としやすい共線: 傾き2の直線(赤: (0,0),(1,2),(2,4))と傾き1/2の直線(青: (0,0),(2,1),(4,2))。それぞれ向きごとに3本ずつある

これ以外の傾き(たとえば3や $\frac{1}{3}$ 、 $\frac{2}{3}$ )では、3点目が $0$ 〜 $4$ の範囲からはみ出すので3点は並ばない。合計

$100 + 40 + 12 = 152 通り$

③ 引き算で仕上げる。

$2300 - 152 = 2148 通り$

まとめ: 「引くべきものを直線の側から整理する」のが急所。等間隔の格子では、傾き $\pm 2, \pm \frac{1}{2}$ のような隠れた共線が必ず候補になる。ベクトルの歩幅 $(1, 2)$ や $(2, 1)$ で3歩が枠に収まるか、と点検すると漏れがない。

発展 — 一歩先へ。 2つの格子点のあいだ(両端を除く)にある格子点の個数は、座標の差の最大公約数を $g$ として $g - 1$ 個になる。この事実(別解で活躍する)は、格子の幾何のあちこちで顔を出す基本部品だ。

答

$2148$ 通り

中点勘定 — 2点を選んで「間の点」を数える(得意な人向け)。 直線をリストアップする代わりに、共線な3点を「両端の2点+間の1点」と見る。

共線な3点のうち両端の2点を $P, Q$ とすると、残り1点は線分 $P Q$ の内部の格子点だ。座標の差を $(d x, d y)$ 、 $g = g cd (∣ d x ∣, ∣ d y ∣)$ とすると、内部の格子点はちょうど $g - 1$ 個(線分を $g$ 等分する点)。

よって共線な3点の総数は、すべての2点ペア(300組)にわたる $g - 1$ の和になる。実際に足し上げると

$ペア \sum (g - 1) = 152$

で、本解の直線別の集計と一致する。

この勘定は、直線のリストアップ(見落としの恐怖)を、 $g cd$ という機械的な計算に置き換えている。傾き $\pm 2, \pm \frac{1}{2}$ の「隠れた共線」も、 $g = 2$ のペアとして自動的に拾われる。見落としの心配がない数え方を設計する、という発想の見本だ。