2026年 東京大学 理系数学 第2問

問題

1. 問題の構造

1.1 記号と計数への還元

$[n]:=\{1,2,\dots,n\}$，$L_n:=[3]\times[n]$ とおく。直線 $x=j$ 上の $n$ 点を第 $j$ 列，直線 $y=k$ 上の $3$ 点を第 $k$ 行（高さ $k$）とよぶ。
$L_n$ の $3$ 点部分集合は $\binom{3n}{3}$ 個あり，仮定よりそれらは等確率で選ばれる。三角形は同一直線上にない $3$ 点を頂点とする図形であるから，相異なる $3$ 点が三角形の $3$ 頂点となることは，$3$ 点が共線でないことと同値である。そこで
$$ T_n:=\#\{\text{共線でない 3 点集合}\},\qquad D_n:=\#\{\text{共線な 3 点集合}\} $$
とおくと $T_n+D_n=\binom{3n}{3}$ であり，
$$ p_n=\frac{T_n}{\binom{3n}{3}}=1-\frac{D_n}{\binom{3n}{3}}. $$
「三角形をなす」は不等式条件（面積 $\neq0$），「共線」は等式条件（面積 $=0$）である。等式で記述される側は一つの方程式の解として構造化できるため，以下では主として $D_n$ を決定する。

1.2 列型による分類

$3$ 点の $x$ 座標の重複の仕方は，すべて等しい（$3$ 型），ちょうど $2$ つが等しい（$2+1$ 型），すべて異なる（$1+1+1$ 型）のいずれかである。

$3$ 型の $3$ 点集合は各列に $\binom n3$ 個ずつ，計 $3\binom n3$ 個あり，すべて共線である。$2+1$ 型はすべて三角形をなす。したがって非自明な判定が必要なのは $1+1+1$ 型のみである。

1.3 共線条件の一次式化

$a+c=2b$ は $b-a=c-b$ と同値であり，$(a,b,c)$ がこの順に（公差 $0$ を許す）$3$ 項等差数列をなすこと，また等間隔 $3$ 点における第 $2$ 階差 $a-2b+c$ が $0$ であることを意味する。同じ一次式は面積・重心・双対などからも得られる（ 3.1 ）。

1.4 解集合の格子構造

$S_n$ は，平面 $a-2b+c=0$ と立方体 $[1,n]^3$ の共通部分に含まれる格子点の全体である。この平面上の格子点には二つの自然な座標がある。

端点座標による表示

射影 $(a,b,c)\mapsto(a,c)$ は $S_n$ 上で単射であり（$b=\frac{a+c}{2}$ で復元される），その像は
$$ E_n:=\{(a,c)\in[n]^2\mid a\equiv c\pmod 2\} $$
である。実際，$(a,c)\in E_n$ ならば $\frac{a+c}{2}$ は整数であり，$\min(a,c)\leqq\frac{a+c}{2}\leqq\max(a,c)$ より $\frac{a+c}{2}\in[n]$ となる。すなわち，中央点の範囲条件は外側 $2$ 点の範囲条件から自動的に従う。

中心・公差座標による表示

$(a,b,c)\in S_n$ に対し $d:=b-a=c-b\in\mathbb{Z}$ とおくと $a=b-d,\ c=b+d$ である。$\min(b-d,b+d)=b-\lvert d\rvert$，$\max(b-d,b+d)=b+\lvert d\rvert$ に注意すると，$(a,b,c)\mapsto(b,d)$ は $S_n$ から
$$ Q_n:=\{(b,d)\in\mathbb{Z}^2\mid 1+\lvert d\rvert\leqq b\leqq n-\lvert d\rvert\} $$
への全単射である。$Q_n$ は $(b,d)$ 平面の菱形内の格子点の全体である。線形写像 $(b,d)\mapsto(b-d,\ b+d)$ の行列式は $2$ であり，$\mathbb{Z}^2$ を指数 $2$ の部分格子 $\{(a,c)\in\mathbb{Z}^2\mid a\equiv c\pmod 2\}$ の上へ写す。
したがって $N_n=\#E_n=\#Q_n$ であり，$N_n$ は「正方形 $[1,n]^2$ 内の指数 $2$ の部分格子の点の個数」である。$n=5$ の $E_5$ を，各点に $b=\frac{a+c}{2}$ を記入して示す（$\cdot$ は $a\not\equiv c\pmod 2$）。

記入された $13$ 個の数は，奇数行に $3$ 個ずつ，偶数行に $2$ 個ずつ並ぶ（$3^2+2^2$）。対角線方向 $c-a=2d$ 一定の並びは傾き $d$ の直線に，反対角線方向 $a+c=2b$ 一定の並びは中央点 $\mathrm{B}=(2,b)$ に対応する。

解法の分岐

各解法は，同一の有限集合 $S_n$ をどの座標でどう分解して数えるかの違いとして整理される。

別解3（3.6）のみは， 補題2 の列型分類の代わりに行型分類から出発する別系統である。

1.5 設計の分析

幅 3 の役割

幅 $2$ の格子 $[2]\times[n]$ では，鳩の巣原理により $3$ 点のうち $2$ 点が同じ列にあるから，共線は鉛直な場合に限られる。幅 $3$ は非鉛直な共線が現れる最小の幅であり，しかも非自明な型は $1+1+1$ 型ただ一つで，中央列が外側 $2$ 列の中点に位置する。この二点により，幾何的な共線判定が $3$ 項等差数列の計数 $N_n$ に正確に一致する。
格子点 $\mathrm{P},\mathrm{R}$ を結ぶ開線分上の格子点の個数は $\gcd(\lvert\Delta x\rvert,\lvert\Delta y\rvert)-1$ である（ 補題6 ）。幅 $3$ では $\lvert\Delta x\rvert\in\{0,1,2\}$ であるから，退化の判定に現れる数論的情報は $\Delta y$ の偶奇のみとなる。幅 $k\geqq4$ では $\lvert\Delta x\rvert=3$ の組が現れ，$\Delta y$ を $3$ で割った余りが判定に入る。すなわち幅 $3$ は，退化の判定が偶奇だけで決まる最大の幅である。これに対応して，幅 $k$ の格子の共線 $3$ 点数は周期が $\operatorname{lcm}(1,\dots,k-1)$ の約数である $n$ の準多項式となり，$k=3$ では周期 $2$，$k=4$ では周期はちょうど $6$ である（ 5.1 ）。

小問の構成

奇数の $n=2m+1$ $(m\geqq0)$ に対しては
$$ D_{2m+1}=4m^3+2m^2+m+1,\qquad \binom{6m+3}{3}=(2m+1)(3m+1)(6m+1) $$
であり，両者は多項式として互いに素である。その結果
$$ p_{2m+1}=\frac{2m(16m^2+17m+5)}{(2m+1)(3m+1)(6m+1)} $$
となり，分子の $2$ 次式は判別式 $17^2-4\cdot16\cdot5=-31<0$ により実数の範囲で既約である。これに対し偶数の $n=2m$ では偶奇類の大きさが等しく（$m$ 個ずつ），$D_{2m}=2m(2m^2-2m+1)$ と $\binom{6m}{3}=2m(3m-1)(6m-1)$ が共通因子 $2m$ をもつため，$p_{2m}$ は $2$ 次式の比に簡約される。
以上から，(2) は閉じた式が簡潔になる偶数側に一般の $n$ を置き，(1) は偶奇類の大きさが不均衡（奇数 $3$ 個，偶数 $2$ 個）な奇数側を具体値で問う構成と読める。なお (2) の結論は $m=1$ でも成り立つ（$p_2=\frac{9}{10}$）から，条件 $m\geqq2$ は結論の成立には不要であり，$2m\geqq3$，すなわち $3$ 型の共線が実際に存在する範囲への限定と解される。

確率としての外皮

等確率の仮定は計数比への正規化を与えるにすぎない。$n\to\infty$ で $p_n\to\frac89$ となり，極限に残る $\frac19$ は $3$ 点が同一列に入る確率の極限 $3\cdot\left(\frac13\right)^3$ に等しい。非鉛直な共線の寄与は $O(n^{-1})$ である（ 2.3 ）。

2. 本解：列型分類と偶奇

2.1 方針

補集合 $D_n$ を数える。列型分類により $3$ 型（$3\binom n3$ 個）と $2+1$ 型（退化なし）を処理し，$1+1+1$ 型では「外側 $2$ 点の中点が中央列の格子点となる」ことを高さの偶奇の一致に言い換え，同じ偶奇の組 $(a,c)$ の個数として $N_n$ を求める。

2.2 解答

$3$ 点の選び方は $\binom{3n}{3}$ 通りで，これらは等確率である。相異なる $3$ 点が三角形の $3$ 頂点とならないのは $3$ 点が共線のときに限るから，共線な $3$ 点集合の個数 $D_n$ を求めればよい。$3$ 点の $x$ 座標の重複の仕方で分類する。
$3$ 点がすべて同じ列にあるとき，$3$ 点は鉛直線上にあって共線であり，その個数は $3\binom n3$ である。
ちょうど $2$ 点が同じ列にあるとき，その $2$ 点を通る直線は鉛直線であり，残る $1$ 点は別の列にあるからこの直線上にない。よって共線でない。
$3$ 点が相異なる列にあるとき，$3$ 点は $\mathrm{A}=(1,a),\ \mathrm{B}=(2,b),\ \mathrm{C}=(3,c)$ $(a,b,c\in[n])$ と書ける。直線 $\mathrm{AC}$ 上の点は $(1+2t,\ a+t(c-a))$ $(t\in\mathbb{R})$ と表され，$x=2$ となるのは $t=\frac12$ のときに限るから，
$$ \mathrm{A},\mathrm{B},\mathrm{C}\text{ が共線}\iff b=\frac{a+c}{2}. $$
$a,c$ は整数であるから，$\frac{a+c}{2}$ が整数であることは $a\equiv c\pmod 2$ と同値である。さらに $\min(a,c)\leqq\frac{a+c}{2}\leqq\max(a,c)$ であるから，このとき $\frac{a+c}{2}\in[n]$ は自動的に成り立つ。したがって $1+1+1$ 型の共線 $3$ 点集合は，$a\equiv c\pmod 2$ を満たす $(a,c)\in[n]^2$ と一対一に対応する（$b$ は $b=\frac{a+c}{2}$ により一意に定まる）。$[n]$ に含まれる奇数の個数を $o_n$，偶数の個数を $e_n$ とすると，その個数は
$$ N_n=o_n^2+e_n^2,\qquad o_n=\left\lceil\frac n2\right\rceil,\quad e_n=\left\lfloor\frac n2\right\rfloor $$
である。以上より
$$ p_n=1-\frac{3\binom n3+o_n^2+e_n^2}{\binom{3n}{3}}. $$

(1)

$n=5$ のとき $o_5=3,\ e_5=2$ より $N_5=9+4=13$ である。$3\binom53=30$，$\binom{15}{3}=455$ であるから
$$ p_5=1-\frac{30+13}{455}=\boxed{\frac{412}{455}}. $$

(2)

$n=2m$ のとき $o_{2m}=e_{2m}=m$ より $N_{2m}=2m^2$ である。また
$$ 3\binom{2m}{3}=\frac{2m(2m-1)(2m-2)}{2}=2m(2m-1)(m-1),\qquad \binom{6m}{3}=\frac{6m(6m-1)(6m-2)}{6}=2m(3m-1)(6m-1) $$
であるから
$$ D_{2m}=2m(2m-1)(m-1)+2m^2=2m(2m^2-2m+1). $$
よって
$$ \begin{aligned} p_{2m}&=1-\frac{2m^2-2m+1}{(3m-1)(6m-1)}=\frac{(18m^2-9m+1)-(2m^2-2m+1)}{(3m-1)(6m-1)}\\ &=\boxed{\frac{m(16m-7)}{(3m-1)(6m-1)}}. \end{aligned} $$

2.3 検証・検算

小さい n での照合

$3$ 点集合をすべて列挙して共線性を直接判定した値と， 命題4 ・ 命題5 による値は一致する。

$m=1,2,3$ を (2) の式に代入すると $\frac{9}{10}$，$\frac{50}{55}=\frac{10}{11}$，$\frac{123}{136}$ となり，表と一致する。また列型による分解 $\binom{3n}{3}=3\binom n3+6n\binom n2+n^3$（$n=5$ で $30+300+125=455$）は，型分類が標本空間を過不足なく分割していることの検算となる。

漸近挙動

$$ \frac{3\binom n3}{\binom{3n}{3}}=\frac{(n-1)(n-2)}{(3n-1)(3n-2)}=\frac19-\frac{2}{9n}+O(n^{-2}),\qquad \frac{N_n}{\binom{3n}{3}}=\frac{1}{9n}+O(n^{-2}) $$
より
$$ p_n=\frac89+\frac{1}{9n}+O(n^{-2})\qquad(n\to\infty). $$
実際 $p_{2m}-\frac89=\frac{9m-8}{9(3m-1)(6m-1)}>0$ である。極限が $1$ となる式が得られた場合は，鉛直な共線 $3\binom n3$ の脱落を疑うべきである。

答の既約性

$p_{2m}$ の分子と分母は $m$ の多項式として共通因子をもたない。ただし整数としては約分が生じうる。$\gcd(m,(3m-1)(6m-1))=1$，$\gcd(3m-1,6m-1)=1$ であり，
$$ (16m-7)-5(3m-1)=m-2,\quad (3m-1)-3(m-2)=5,\qquad 3(16m-7)-8(6m-1)=-13 $$
より $\gcd(16m-7,3m-1)\mid5$，$\gcd(16m-7,6m-1)\mid13$ である。したがって分子と分母の最大公約数は $5^{\varepsilon}\,13^{\eta}$ の形であり，$\varepsilon=1\iff m\equiv2\pmod5$，$\eta=1\iff m\equiv11\pmod{13}$（それ以外は $0$）である（例：$m=2$ で $\frac{50}{55}=\frac{10}{11}$，$m=11$ で $\frac{1859}{2080}=\frac{143}{160}$）。

計算機による全列挙

      from itertools import combinations
from fractions import Fraction
def p(n):
    P = [(x, y) for x in (1, 2, 3) for y in range(1, n + 1)]
    good = total = 0
    for (x1, y1), (x2, y2), (x3, y3) in combinations(P, 3):
        total += 1
        good += (x2 - x1) * (y3 - y1) != (y2 - y1) * (x3 - x1)
    return Fraction(good, total)
print(p(5))  # 412/455
print(all(p(2*m) == Fraction(m*(16*m - 7), (3*m - 1)*(6*m - 1)) for m in range(1, 16)))  # True
    

3. 別解と参考解

3.1 共線条件の別証

補題3 の一次式 $a-2b+c$ は以下のいずれからも得られる。いずれも同一の一次式に到達するため，計数の段階で新しい枝を生まない。以下 $\mathrm{A}=(1,a),\ \mathrm{B}=(2,b),\ \mathrm{C}=(3,c)$ とする。

面積・外積

$\overrightarrow{\mathrm{AB}}=(1,\ b-a)$，$\overrightarrow{\mathrm{AC}}=(2,\ c-a)$ より，三角形 $\mathrm{ABC}$ の符号付き面積の $2$ 倍は
$$ \det\begin{pmatrix}1&b-a\\2&c-a\end{pmatrix}=(c-a)-2(b-a)=a-2b+c $$
であり，共線はこれが $0$ であることと同値である。副産物として，退化しない三角形の面積は $\frac12$ の正の整数倍，特に $\frac12$ 以上である。

重心

$1+1+1$ 型の $3$ 点の重心 $\mathrm{G}$ の $x$ 座標は $\frac{1+2+3}{3}=2$ である。$3$ 点が共線ならば，$\mathrm{G}$ はその直線（鉛直でない）上の $x$ 座標 $2$ の点であるから $\mathrm{G}=\mathrm{B}$，すなわち $\mathrm{A}+\mathrm{C}=2\mathrm{B}$ となる。逆に $\mathrm{A}+\mathrm{C}=2\mathrm{B}$ ならば $\mathrm{B}$ は線分 $\mathrm{AC}$ の中点であり，$3$ 点は共線である。

第 2 階差

$f:\{1,2,3\}\to\mathbb{Z}$ を $f(1)=a,\ f(2)=b,\ f(3)=c$ で定める。$1+1+1$ 型の $3$ 点を通る直線は鉛直でないから，共線であることは $f$ が一次関数 $x\mapsto\alpha x+\beta$ の制限であることと同値であり，これは $\Delta f(1)=\Delta f(2)$，すなわち
$$ \Delta^2 f(1)=f(3)-2f(2)+f(1)=a-2b+c=0 $$
と同値である（$b-a=c-b=\alpha$ ならば $f(x)=a+\alpha(x-1)$）。

点と直線の双対

点 $(x,y)$ に直線 $\ell_{(x,y)}:\ Y=xX-y$ を対応させると，点 $(x,y)$ が直線 $y=\alpha x+\beta$ 上にあることと，点 $(\alpha,-\beta)$ が $\ell_{(x,y)}$ 上にあることは同値である。$1+1+1$ 型の $3$ 点を通る直線は鉛直でないから，共線であることは $3$ 直線 $Y=X-a,\ Y=2X-b,\ Y=3X-c$ が $1$ 点で交わることと同値である。第 $1$・第 $3$ の直線の交点 $\left(\frac{c-a}{2},\ \frac{c-3a}{2}\right)$ を第 $2$ の式に代入すると $a+c=2b$ を得る。

3.2 偶奇条件の別証：格子線分上の格子点

外側 $2$ 点 $\mathrm{A}=(1,a)$，$\mathrm{C}=(3,c)$ に対して，直線 $\mathrm{AC}$ 上の中央列の点は $x$ 座標が $1$ と $3$ の間にあるから，開線分 $\mathrm{AC}$ 上にある。 補題6 より，そのような格子点の個数は
$$ \gcd(2,\lvert c-a\rvert)-1=\begin{cases}1 & (a\equiv c\pmod 2)\\ 0 & (a\not\equiv c\pmod 2)\end{cases} $$
である。したがって $N_n=\sum_{(a,c)\in[n]^2}\bigl(\gcd(2,\lvert c-a\rvert)-1\bigr)=\#E_n$ であり，偶奇条件が格子幾何から直接得られる。

3.3 答の他の導出：三角形の直接計数

補集合を経由せず $T_n$ を直接数える。$2+1$ 型は，$2$ 点をとる列（$3$ 通り），その $2$ 点（$\binom n2$ 通り），他の列の $1$ 点（$2n$ 通り）の選び方で $6n\binom n2$ 個あり，すべて三角形をなす。$1+1+1$ 型は $n^3$ 個のうち $N_n$ 個が共線である。よって
$$ T_n=6n\binom n2+n^3-N_n. $$
$n=5$ では $T_5=300+125-13=412$ である。$n=2m$ では
$$ T_{2m}=12m\cdot m(2m-1)+8m^3-2m^2=32m^3-14m^2=2m^2(16m-7) $$
であり，$\binom{6m}{3}=2m(3m-1)(6m-1)$ で割って (2) の答を得る。恒等式 $\binom{3n}{3}=3\binom n3+6n\binom n2+n^3$ により，本解の結果と整合する。

3.4 別解1：公差（傾き）を固定する計数

着想・方針

$1+1+1$ 型の共線 $3$ 点は $(1,b-d),\ (2,b),\ (3,b+d)$ $(d\in\mathbb{Z})$ と書け，$d$ はその直線の傾きである。傾きを固定すると，許される配置はその直線の平行移動として数えられる。これは $Q_n$ を $d$ 一定の直線で切ることにあたる。

解答

$1+1+1$ 型の共線 $3$ 点集合 $\{(1,a),(2,b),(3,c)\}$ では $a+c=2b$ であるから，$d:=b-a=c-b\in\mathbb{Z}$ とおけば $3$ 点は $(1,b-d),\ (2,b),\ (3,b+d)$ と表される。逆にこの形の $3$ 点は共線であり，$3$ 点集合と $(b,d)$ は一対一に対応する。範囲条件 $b-d,\ b,\ b+d\in[n]$ は
$$ 1+\lvert d\rvert\leqq b\leqq n-\lvert d\rvert $$
と同値であるから，$d$ を固定したときの $b$ の個数は $\max(n-2\lvert d\rvert,\ 0)$ である。$d=0$（水平）と $d=\pm k$ $(k\geqq1)$ に分けて
$$ N_n=\sum_{d\in\mathbb{Z}}\max(n-2\lvert d\rvert,\ 0)=n+2\sum_{k=1}^{\lfloor (n-1)/2\rfloor}(n-2k). $$

(1)

$$ N_5=5+2\{(5-2)+(5-4)\}=13,\qquad p_5=1-\frac{30+13}{455}=\frac{412}{455}. $$

(2)

$\left\lfloor\frac{2m-1}{2}\right\rfloor=m-1$ であり，$j=m-k$ とおくと
$$ N_{2m}=2m+2\sum_{k=1}^{m-1}(2m-2k)=2m+4\sum_{j=1}^{m-1}j=2m+2m(m-1)=2m^2. $$
以下，本解と同様に $p_{2m}=\frac{m(16m-7)}{(3m-1)(6m-1)}$ を得る。

検証・検算

• $n=5$ の傾きごとの個数は $d=0,\pm1,\pm2$ に対して $5,3,3,1,1$ であり，1.4 の表の対角線方向の並びと一致する。
• 反転 $x\mapsto4-x$ は $L_n$ と共線性を保ち，$(a,b,c)\mapsto(c,b,a)$，すなわち $d\mapsto-d$ を引き起こす。これが係数 $2$ の根拠である。
• $d=0$ を $\pm k$ の和に含めると二重計数となる。和の上限 $\lvert d\rvert\leqq\left\lfloor\frac{n-1}{2}\right\rfloor$ は $n-2\lvert d\rvert\geqq1$ と同値である。
• $n=2m+1$ では $N_{2m+1}=(2m+1)+2m^2=\left\lceil\frac{n^2}{2}\right\rceil$ となり， 命題5 と一致する。

3.5 別解2：中央点を固定する点対称計数

着想・方針

共線であることは $\mathrm{B}$ が線分 $\mathrm{AC}$ の中点であること，すなわち $\mathrm{A}$ と $\mathrm{C}$ が $\mathrm{B}$ に関して点対称であることと同値である。中央点を固定し，それを中心とする点対称な外側 $2$ 点の組を数える。これは $Q_n$ を $b$ 一定の直線で切ることにあたる。

解答

中央点 $\mathrm{B}=(2,b)$ $(b\in[n])$ を固定する。$\mathrm{B}$ を通る $1+1+1$ 型の共線 $3$ 点集合は，$\mathrm{A}=(1,b-d),\ \mathrm{C}=(3,b+d)$ $(d\in\mathbb{Z})$ によって一対一に与えられる。範囲条件 $b\pm d\in[n]$ は $\lvert d\rvert\leqq\min(b-1,\ n-b)$ と同値であるから，その個数は $2\min(b-1,\ n-b)+1$ である（$d=0$ の水平な場合を含む）。よって
$$ N_n=\sum_{b=1}^{n}\bigl\{2\min(b-1,\ n-b)+1\bigr\}. $$

(1)

$b=1,\dots,5$ に対する個数は $1,3,5,3,1$ であるから $N_5=13$，$p_5=\frac{412}{455}$。

(2)

$n=2m$ のとき，$b-1\leqq 2m-b\iff b\leqq m$ であるから，$1\leqq b\leqq m$ では $\min=b-1$，$m+1\leqq b\leqq 2m$ では $\min=2m-b$ である。個数の列は $1,3,\dots,2m-1,\ 2m-1,\dots,3,1$ となり
$$ N_{2m}=2\sum_{b=1}^{m}(2b-1)=2m^2. $$
以下，本解と同様に $p_{2m}=\frac{m(16m-7)}{(3m-1)(6m-1)}$ を得る。

検証・検算

• 個数の列は $b\mapsto n+1-b$ で不変である。これは反転 $y\mapsto n+1-y$ の対称性の反映である。
• $n=5$ の個数 $1,3,5,3,1$ は 1.4 の表の反対角線方向の並び（同じ値 $b$ の個数）と一致する。
• 別解1と本解法は同一の有限集合 $Q_n$ を二方向に切った和であり，$\sum_d\#\{b\}=\sum_b\#\{d\}$ が両者の一致を保証する。

3.6 別解3：水平な行を基準とする局所 3×3 計数

着想・方針

分類軸を列から行へ替え，$3$ 点が使う行の本数（$1,2,3$）で分類する。$3$ 本の行を固定すると，問題は $3\times3$ の局所配置の計数に縮約される。三角形を直接数える。

解答

使う行が $1$ 本のとき，$3$ 点はその行の $3$ 点全体で水平に共線である。三角形は $0$ 個。
使う行がちょうど $2$ 本のとき，一方の行に $2$ 点，他方に $1$ 点がある。行の組は $\binom n2$ 通り，固定した $2$ 行に対し $2\cdot\binom32\cdot3=18$ 通りである。同じ行の $2$ 点を通る直線は水平であり，他方の行の点を通らないから，すべて三角形をなす。三角形は $18\binom n2$ 個。
使う行が $3$ 本のとき，高さを $r< s< t$ とし，各行から $1$ 点ずつ選ぶ。列の割り当ては $3^3=27$ 通りある。$3$ 点が同じ列にある $3$ 通りは鉛直に共線，ちょうど $2$ 点が同じ列にある場合は 補題2 (2) により三角形である。列がすべて異なる $6$ 通りでは，$3$ 点は $(1,h_1),(2,h_2),(3,h_3)$（$(h_1,h_2,h_3)$ は $(r,s,t)$ の並べ替え）と書け， 補題3 より共線 $\iff h_1+h_3=2h_2$ である。$h_2=r$ ならば $h_1+h_3>2r$，$h_2=t$ ならば $h_1+h_3<2t$ であるから，共線となるのは $h_2=s$ かつ $r+t=2s$ のとき，すなわち $(h_1,h_2,h_3)=(r,s,t),(t,s,r)$ の $2$ 通りに限る。したがって固定した $3$ 行における三角形の個数は
$$ \begin{cases}27-3=24 & (r,s,t\text{ が等差数列でない})\\ 27-3-2=22 & (r,s,t\text{ が等差数列})\end{cases} $$
である。$[n]$ の $3$ 元部分集合で等差数列をなすものの個数を $R_n$ とすると，公差 $e\geqq1$ を固定したとき初項は $1,\dots,n-2e$ の $n-2e$ 通りであるから
$$ R_n=\sum_{e=1}^{\lfloor (n-1)/2\rfloor}(n-2e),\qquad T_n=18\binom n2+24\left\{\binom n3-R_n\right\}+22R_n=18\binom n2+24\binom n3-2R_n. $$

(1)

$R_5=3+1=4$（$\{1,2,3\},\{2,3,4\},\{3,4,5\},\{1,3,5\}$）であるから
$$ T_5=180+240-8=412,\qquad p_5=\frac{412}{455}. $$

(2)

$R_{2m}=\sum_{e=1}^{m-1}(2m-2e)=m(m-1)$ であり，$18\binom{2m}{2}=18m(2m-1)$，$24\binom{2m}{3}=16m(2m-1)(m-1)$ であるから
$$ T_{2m}=18m(2m-1)+16m(2m-1)(m-1)-2m(m-1)=32m^3-14m^2=2m^2(16m-7). $$
$\binom{6m}{3}=2m(3m-1)(6m-1)$ で割って $p_{2m}=\frac{m(16m-7)}{(3m-1)(6m-1)}$ を得る。

検証・検算

• 行型による分解 $\binom{3n}{3}=n+18\binom n2+27\binom n3$（$n=5$ で $5+180+270=455$）が成り立つ。
• この方法で得られる退化数は $n+3\binom n3+2R_n$ であり， 命題4 の $D_n=3\binom n3+N_n$ との一致は $N_n=n+2R_n$ と同値である。これは別解1の $d=0$ の項 $n$ と $d=\pm e$ の項 $2R_n$ の分解そのものである。なお $R_n=\left\lfloor\frac{(n-1)^2}{4}\right\rfloor$ である。
• 列がすべて異なる $6$ 通りのうち共線は $2$ 通りであって $6$ 通りではない。また $R_n$ は相異なる $3$ 行を数えるから公差 $0$ を含まない。
• 分類軸が本解と独立であるため，結果の一致は強い検算となる。

3.7 参考解1：盤面を 2 行ずつ広げる漸化式

着想・方針

$N_n$ を一度に数えず，高さ $1,\dots,n-2$ の盤面に $2$ 行を加えたときの増分を数える。静的な計数を，盤面の大きさを状態とする漸化式に置き換える。

解答

$[0]=\varnothing$ とし，$S_0=\varnothing$，$N_0=0$ と定める。$n\geqq2$ に対し $S_{n-2}\subset S_n$ であり，$S_n\setminus S_{n-2}$ は $\max(a,b,c)\geqq n-1$ を満たす $(a,b,c)\in S_n$ の全体である。等差数列の最大項は両端のいずれかにあるから $\max(a,b,c)=\max(a,c)=:M\in\{n-1,\ n\}$ で分類する。
公差 $0$ のものは $(M,M,M)$ の $2$ 個である。公差が $0$ でないものは $(M-2k,\ M-k,\ M)$ または $(M,\ M-k,\ M-2k)$ $(k\geqq1)$ であり，範囲条件は $M-2k\geqq1$，すなわち $k\leqq\left\lfloor\frac{M-1}{2}\right\rfloor$ である。よって，整数 $j\geqq0$ に対する $\left\lfloor\frac j2\right\rfloor+\left\lfloor\frac{j+1}{2}\right\rfloor=j$ を $j=n-2$ に用いて
$$ N_n-N_{n-2}=2+2\left\lfloor\frac{n-2}{2}\right\rfloor+2\left\lfloor\frac{n-1}{2}\right\rfloor=2n-2\qquad(n\geqq2). $$

(1)

$N_1=1$（水平な $1$ 組）より $N_3=1+4=5$，$N_5=5+8=13$。よって $p_5=\frac{412}{455}$。

(2)

$$ N_{2m}=\sum_{j=1}^{m}(N_{2j}-N_{2j-2})=\sum_{j=1}^{m}(4j-2)=2m(m+1)-2m=2m^2. $$
以下，本解と同様に $p_{2m}=\frac{m(16m-7)}{(3m-1)(6m-1)}$ を得る。

検証・検算

• 直接の数え上げで $N_2=2$（水平 $2$ 組），$N_3=5$（水平 $3$ 組と $(1,2,3),(3,2,1)$）であり，漸化式と一致する。
• $n^2$ と $(n-2)^2$ は偶奇が等しいから $\left\lceil\frac{n^2}{2}\right\rceil-\left\lceil\frac{(n-2)^2}{2}\right\rceil=\frac{n^2-(n-2)^2}{2}=2n-2$ であり， 命題5 は漸化式を満たす。
• 増分を「新しい行を少なくとも $1$ 点使うもの」として数えると重複が生じやすい。最大項 $M$ による分類は重複を排除する。
  漸化式と初期値の管理を要するため，答案としては参考解に位置づける。

3.8 参考解2：生成関数による偶奇抽出

着想・方針

$N_n=\#E_n$ は「$a+c$ が偶数である $(a,c)\in[n]^2$ の個数」である。この合同条件を場合分けせず，多項式の $x=\pm1$ での値によって抽出する。

解答

$F_n(x):=x+x^2+\cdots+x^n$ とおくと $F_n(x)^2=\sum_{(a,c)\in[n]^2}x^{a+c}$ であるから，$N_n$ は $F_n(x)^2$ の偶数次の係数の総和である。多項式 $P(x)=\sum_k\alpha_kx^k$ に対し
$$ \frac{P(1)+P(-1)}{2}=\sum_k\alpha_k\cdot\frac{1+(-1)^k}{2}=\sum_{k\text{ は偶数}}\alpha_k $$
であるから
$$ N_n=\frac{F_n(1)^2+F_n(-1)^2}{2},\qquad F_n(1)=n,\quad F_n(-1)=\sum_{k=1}^{n}(-1)^k=\begin{cases}-1&(n\text{ は奇数})\\0&(n\text{ は偶数})\end{cases}. $$

(1)

$N_5=\frac{25+1}{2}=13$。よって $p_5=\frac{412}{455}$。

(2)

$N_{2m}=\frac{(2m)^2+0}{2}=2m^2$。以下，本解と同様に $p_{2m}=\frac{m(16m-7)}{(3m-1)(6m-1)}$ を得る。

検証・検算

• $F_n$ を奇数次・偶数次の部分に分けると $F_n(1)=o_n+e_n$，$F_n(-1)=e_n-o_n$ であり，$\frac{(o_n+e_n)^2+(e_n-o_n)^2}{2}=o_n^2+e_n^2$ となって本解と一致する。
• 一般に $N_n=\frac{n^2}{2}+\frac{1-(-1)^n}{4}$ であり， 命題5 を一つの式で与える。
• 合同条件 $a+c\equiv r\pmod q$ を満たす組の個数は，$1$ の $q$ 乗根 $\omega$ にわたる和 $\frac1q\sum_{\omega^q=1}\omega^{-r}F_n(\omega)^2$ で与えられる。本解法はその $q=2$ の場合である。

3.9 同じ系列に属する変形

以下は独立の解法とせず，既存の解法の言い換え・視覚化として位置づける。

• 条件付き確率・逐次選択：$P(1+1+1\text{ 型})=\frac{n^3}{\binom{3n}{3}}$，$P(\text{共線}\mid 1+1+1\text{ 型})=\frac{N_n}{n^3}$（$n=2m$ で $\frac{1}{4m}$）と分解する表現は，本解の計数を確率で正規化したものである。
• チェッカーボード：1.4 の表のように行番号を偶奇で塗り分ける見方は，本解の偶奇計数の視覚化である。
• $3$ 次元の平面切断：$S_n$ を平面 $a-2b+c=0$ と立方体 $[1,n]^3$ の共通部分とみる見方は，$b$ 一定で切れば別解2，$c-a$ 一定で切れば別解1に一致する（5.2 も参照）。
• 中心化：$Y=y-\frac{n+1}{2}$ とおくと反転対称 $Y\mapsto-Y$ が明示されるが，計数原理は別解1・別解2と同じである。
• 期待値・指示変数：共線の指示変数の期待値は退化確率そのものであり，計数を置き換えない。
• 複素数・三角比・行列の階数：いずれも 3.1 の一次式 $a-2b+c$ の別表記に帰着する。
• 境界の周期化（鏡像による折り返し，トーラスへの埋め込み）：周期化した空間での計数と元の有限区間での計数を結ぶ全単射と重複の補正を与えない限り，証明として完結しない。本稿では採用しない。
• 自由度による漸近評価：$1+1+1$ 型の確率 $\to\frac29$，その条件の下での共線確率 $\sim\frac{1}{2n}$ から非鉛直な寄与 $\sim\frac{1}{9n}$ を見積もる議論は，証明ではなく検算（2.3）として用いる。

3.10 解法の比較

本解・別解1・別解2は，線形変換 $(b,d)\mapsto(b-d,\ b+d)$ で結ばれた同一の格子点集合を異なる座標で数えている。本解は範囲条件が自動的に満たされる点で最短であり，別解1・別解2は偶奇を用いずに境界条件だけで数え切る。別解3は標本空間の分割そのものが異なるため，他の解法に対する独立な検算となる。参考解1は増分の分類に，参考解2は係数抽出の原理の説明に，それぞれ答案上の記述を要する。

4. 汎用的な探索手順

4.1 手順

本問の解析を抽象化すると，有限格子上の配置の確率・個数を求める問題に対して次の手順が得られる。

1. 確率を計数に直す。標本空間が等確率の有限集合であることを確認し，確率を個数の比として表す。
2. 等式で記述される側を数える。「三角形をなす」のような不等式条件は，補集合の等式条件（面積 $=0$）に置き換えると一つの方程式で記述できる。
3. 値域の小さい座標で重複型を分類する。自明に判定が決まる型（$3$ 型，$2+1$ 型）を先に除き，非自明な自由度を特定する。
4. 非自明な型の条件を一つの不変量に集約する。中点・面積・差分などの複数の表現が同一の一次式に帰着することを確認し，入口の多様性と計数原理の多様性を区別する。
5. 解集合の構造を同定する。一次方程式の整数解と箱型領域の共通部分は，格子（部分格子）と凸多角形の共通部分である。範囲条件が他の条件から自動的に従うか（平均は範囲内にある）を確認する。
6. 数え方を選ぶ。端点座標での合同類の直積，別座標（中心・公差）への変換と切断，パラメータの増分（漸化式），合同条件の代数的抽出（$1$ の冪根による和），分類軸そのものの変更（局所化）のいずれかを，範囲条件が最も単純になるものとして選ぶ。
7. 検算する。小さい場合の全列挙，型分解の恒等式（各型の和が全体に一致），対称性，主要項（漸近），独立な分類軸による別解の一致，答の既約性を確認する。

4.2 観察と選択の対応

4.3 同型の問題への適用

同じ手順は次のような問題にそのまま適用できる。

• $3$ 個のさいころの目 $a,b,c$ が $a+c=2b$ を満たす確率は，$N_6/6^3=18/216=\frac{1}{12}$ である。幾何的な外皮がないだけで，本問の $1+1+1$ 型と同一の計数である。
• 幅 $k$ の格子 $[k]\times[n]$ における共線 $3$ 点の計数では，手順 5 の格子構造が $\gcd(\lvert\Delta x\rvert,\lvert\Delta y\rvert)$ として現れ，手順 6 の合同条件が $\bmod\ \Delta x$ に一般化される（5.1）。
• 条件 $a+c\equiv r\pmod q$ を満たす組の個数は，3.8 の冪根による抽出で一括して求められる。

5. 発展事項

5.1 格子線分公式と一般の長方形格子

$G=[k]\times[n]$ に適用する。変位 $(u,v)=\mathrm{R}-\mathrm{P}$ を $u\geqq0$ かつ（$u=0$ ならば $v>0$）と正規化すると，その変位をもつ $2$ 点集合は $(k-u)(n-\lvert v\rvert)$ 個あるから，共線 $3$ 点数 $C_k(n)$ は
$$ C_k(n)=k\sum_{v=1}^{n-1}(n-v)(v-1)+\sum_{u=1}^{k-1}(k-u)\sum_{v=-(n-1)}^{n-1}(n-\lvert v\rvert)\bigl(\gcd(u,\lvert v\rvert)-1\bigr) $$
である。第 $1$ 項の内側の和は，$[n]$ の $2$ 元 $i< j$ と $i< h< j$ を満たす $h$ の組の個数であるから $\binom n3$ に等しい。
$k=3$ では $u=1$ の項は $\gcd(1,\cdot)-1=0$ により消え，$u=2$ の項は $v$ が偶数の項のみが残って $\sum_{\lvert v\rvert\leqq n-1,\ v\text{ は偶数}}(n-\lvert v\rvert)=N_n$ となる（別解1の和と同一）。したがって
$$ C_3(n)=3\binom n3+N_n=D_n $$
であり， 補題2 ・ 補題3 ・ 命題4 の内容は 命題7 の $k=3$ の場合に一括して含まれる。
一般の $k$ では，$u\geqq1$ を固定すると $v\mapsto\gcd(u,\lvert v\rvert)$ は周期 $u$ の関数であるから，内側の和は周期が $u$ の約数である $n$ の準多項式である。よって $C_k(n)$ は周期が $\operatorname{lcm}(1,\dots,k-1)$ の約数である $3$ 次の準多項式である。$k=4$ では周期はちょうど $6$ であり，
$$ C_4(n)=\frac23n^3-\frac13n^2+\frac43n+\varepsilon(n),\qquad \varepsilon(n)=0,\ \tfrac73,\ \tfrac43,\ 1,\ \tfrac43,\ \tfrac73\quad(n\equiv0,1,2,3,4,5\pmod 6) $$
となる（例：$C_4(1)=\binom43=4$，$C_4(2)=8$）。$k\geqq4$ では $u=3$ の項により $\Delta y$ の $3$ を法とする情報が現れ，$k=4$ では実際に周期が $6$ となる。これが 1.5 で述べた幅 $3$ の特殊性の正確な内容である。

5.2 Ehrhart 理論からみた解の個数

平面 $H:\ a-2b+c=0$ は平行移動 $(a,b,c)\mapsto(a-1,b-1,c-1)$ で不変である（$1-2+1=0$）。よって
$$ N_n=L(n-1),\qquad L(t):=\#\bigl(tP\cap\Lambda\bigr),\qquad P:=H\cap[0,1]^3,\quad \Lambda:=H\cap\mathbb{Z}^3. $$
1.4 の座標 $(b,d)$ により $\Lambda\cong\mathbb{Z}^2$ であり，$P$ は頂点 $(0,0),\ (1,0),\ \left(\frac12,\pm\frac12\right)$ の菱形 $\{\lvert d\rvert\leqq\min(b,1-b)\}$ に写る。$P$ は頂点が $\frac12\mathbb{Z}^2$ に属する有理多角形であるから，有理多面体に対する Ehrhart の定理により，$L(t)$ は $t$ の $2$ 次の準多項式で，周期は $2$ の約数，最高次係数は $P$ の（$\Lambda$ に関する）面積 $\frac12$ に等しい。実際
$$ L(t)=\frac{t^2}{2}+t+\frac34+\frac{(-1)^t}{4},\qquad N_n=\frac{n^2}{2}+\frac{1-(-1)^n}{4}=\left\lceil\frac{n^2}{2}\right\rceil. $$
答に現れる偶奇は，準多項式の周期として，頂点座標の分母 $2$（中点の $\frac12$）から生じている。
さらに Ehrhart–Macdonald の相互法則 $L(-t)=L^{\circ}(t)$ が成り立つ。ここで $L^{\circ}(t)$ は $tP$ の（$H$ 内での）内部の格子点数であり，$H$ は立方体の内部と交わるから $L^{\circ}(t)=\#\bigl(H\cap\{1,\dots,t-1\}^3\bigr)=N_{t-1}=L(t-2)$ である。したがって相互法則は，準多項式 $N(n):=\frac{n^2}{2}+\frac{1-(-1)^n}{4}$ が $N(-n)=N(n)$ を満たすことと同値であり，上の式で直接確かめられる。

5.3 3 項等差数列と加法的組合せ論

有限集合 $A\subset\mathbb{Z}$ に対し $\operatorname{ap}_3(A):=\#\{(a,b,c)\in A^3\mid a+c=2b\}$ とおくと，$N_n=\operatorname{ap}_3([n])$ である。$S_n$ を自明な解 $a=b=c$（$n$ 個）と，$3$ 項等差数列をなす $3$ 元部分集合（それぞれ $2$ 通りの向きで現れる）に分けると
$$ N_n=n+2R_n,\qquad R_n=\left\lfloor\frac{(n-1)^2}{4}\right\rfloor $$
となる（$R_n$ は 3.6 の $3$ 項等差数列をなす $3$ 元部分集合の個数）。
利用できる行の高さを $A\subset[n]$ に制限した点集合 $[3]\times A$ では，$1+1+1$ 型の共線 $3$ 点数は $\operatorname{ap}_3(A)\geqq\lvert A\rvert$ となり，等号は $A$ が非自明な $3$ 項等差数列を含まないときに限る。この「$3$ 項等差数列を含まない集合の最大サイズ」$r_3(N)$ を扱うのが加法的組合せ論の古典的主題である。

• Roth（1953）：$r_3(N)=O\left(\frac{N}{\log\log N}\right)$，特に $r_3(N)=o(N)$。
• Behrend（1946）：ある定数 $c>0$ に対し $r_3(N)\geqq N\exp\bigl(-c\sqrt{\log N}\bigr)$。
• Kelley–Meka（2023）：ある定数 $c>0$ に対し $r_3(N)\leqq N\exp\bigl(-c(\log N)^{1/12}\bigr)$。上界と下界が同じ型 $N\exp(-c(\log N)^{\beta})$ となり，以後は指数 $\beta$ の改良が課題となっている。
• Varnavides（1959）：$\lvert A\rvert\geqq\delta N$ ならば，十分大きい $N$ に対し $A$ は $c(\delta)N^2$ 個以上の $3$ 項等差数列を含む。
  本問の $N_n\sim\frac{n^2}{2}$ は，稠密度 $1$ の集合 $[n]$ における $3$ 項等差数列の総数であり，Varnavides の定理の $N^2$ のオーダーはこの総数に対する正の割合を意味する。

5.4 高校数学との境界

入試答案として完結するのは 4 章までの内容であり，5 章は本問の構造がどの一般理論の特殊例であるかを示すものである。

6. 最終整理

6.1 構造マップ

• 等確率の仮定により $p_n=1-D_n/\binom{3n}{3}$（1.1）
  • 列型分類（ 補題2 ）
    • $3$ 型：鉛直に共線，$3\binom n3$ 個
    • $2+1$ 型：退化なし
    • $1+1+1$ 型：$a+c=2b$（ 補題3 ）により $N_n=#S_n$
      • 端点座標 $(a,c)$ で偶奇類の直積：本解，3.2，参考解2
      • 中心・公差座標で $d$ を固定：別解1
      • 中心・公差座標で $b$ を固定：別解2
      • $n$ を動かして増分を数える：参考解1
  • 行型分類：$3$ 行ごとの局所 $3\times3$ 配置（$24$ または $22$）：別解3
• 合流点：$N_n=\left\lceil\frac{n^2}{2}\right\rceil$ より $p_5=\frac{412}{455}$，$p_{2m}=\frac{m(16m-7)}{(3m-1)(6m-1)}$

6.2 要点

• 確率問題の実体は有限配置の計数であり，等式条件で記述される退化側を数えると，構造は一つの方程式 $a-2b+c=0$ に集約される。
• 値域の小さい座標による重複型の分類は，自明な型を一括して除き，非自明な自由度を $1+1+1$ 型に特定する。
• 共線条件の表現（中点・等差・面積・重心・第 $2$ 階差・双対）は入口の違いにすぎない。解法の本質的な差異は，解集合 $S_n$ をどの座標でどう分解するか，あるいは標本空間をどの軸で分類するかにある。
• 中央点の範囲条件が外側 $2$ 点の範囲条件から自動的に従う（平均は範囲内にある）ことの確認が，本解を最短にする。
• 偶奇は格子線分の公式において $\lvert\Delta x\rvert=2$ から生じる。幅 $3$ は退化の判定が偶奇だけで決まる最大の幅であり，奇数の具体値と偶数の一般式という設問構成はこの構造に対応する。
• 検算は，小さい $n$ の全列挙，型分解の恒等式，対称性，漸近式 $p_n=\frac89+\frac{1}{9n}+O(n^{-2})$，分類軸の異なる別解3との一致によって多重に行える。