トップ› 東京大学› 2020年› 文系第2問

東京大学 2020年文系第2問解説

方針・初手

16個の点は座標平面上の $4 \times 4$ の格子点である。この16点から5点を選ぶときの、点と直線の包含関係について考える。「直線が選んだ点を含まない」という状態を「直線が空である」と言い換えると見通しが良くなる。アプローチとしては、条件を満たす点の配置パターンを直接数え上げる方法（解法1）と、包含と排除の原理（包除原理）を用いて全体から条件を満たさない場合を引く方法（解法2）の2つが考えられる。

解法1

(1)

選んだ点を1個も含まない（空である）直線がちょうど2本となるパターンは、以下の3つの場合に分けられる。

(i)

$x=a$ のうち2本が空、$y=b$ はすべて空でない場合空になる $x$ の直線の選び方は ${}_4\mathrm{C}_{2} = 6$ 通り。残った2本の $x$ 直線と4本の $y$ 直線の交点8個の中から5個の点を選ぶ。このとき、4本の $y$ 直線はすべて空であってはならない。各 $y$ 直線上にはそれぞれ2個の点があるため、5個の点を4本の直線に分配すると、点の個数は必ず (2, 1, 1, 1) となる。 2個の点が選ばれる $y$ 直線の選び方は ${}_4\mathrm{C}_{1} = 4$ 通り。残りの3本の $y$ 直線からは2個中1個の点を選ぶので $2^3 = 8$ 通り。また、この選び方では2本の $x$ 直線には少なくとも2個の点が選ばれるため、新たに空の直線が生じることはない。したがって、この場合は $6 \times 4 \times 8 = 192$ 通り。

(ii)

$x=a$ はすべて空でなく、$y=b$ のうち2本が空である場合（i）と対称であるため、同じく $192$ 通り。

(iii)

$x=a$ のうち1本、$y=b$ のうち1本が空であり、他はすべて空でない場合空になる直線の選び方は ${}_4\mathrm{C}_{1} \times {}_4\mathrm{C}_{1} = 16$ 通り。残った3本の $x$ 直線と3本の $y$ 直線の交点9個の中から5個の点を選ぶ。総数は ${}_9\mathrm{C}_{5} = 126$ 通り。ここから、さらに空の直線ができてしまう場合を引く。・$x$ が新たに1本空になる（点を選ぶ対象が $2 \times 3 = 6$ 個になる）場合：${}_3\mathrm{C}_{1} \times {}_6\mathrm{C}_{5} = 18$ 通り。・$y$ が新たに1本空になる場合：同様に $18$ 通り。・$x, y$ が新たに1本ずつ空になる場合：残りの点が4個となるため5個選べず $0$ 通り。よって、条件を満たす点の選び方は $126 - 18 - 18 = 90$ 通り。したがって、この場合は $16 \times 90 = 1440$ 通り。

以上より、求める総数は

$$ 192 + 192 + 1440 = 1824 $$

となる。

(2)

8本の直線がいずれも点を含む（空の直線が0本である）条件を考える。 4本の $x$ 直線すべてに少なくとも1個の点が選ばれるため、5個の点の分配は必ず (2, 1, 1, 1) 個となる。 $y$ 直線についても同様である。 2個の点が選ばれる $x$ 直線および $y$ 直線を1本ずつ選ぶ方法は ${}_4\mathrm{C}_{1} \times {}_4\mathrm{C}_{1} = 16$ 通り。対称性から、これらが $x=1$ と $y=1$ であるとして点の配置を考える。点 $(1, 1)$ が選ばれているかどうかで場合分けをする。

（A）点 $(1, 1)$ が選ばれている場合直線 $x=1$ 上のもう1点は $y=2, 3, 4$ から選ぶ（3通り）。直線 $y=1$ 上のもう1点は $x=2, 3, 4$ から選ぶ（3通り）。これで3個の点が選ばれ、$x, y$ ともに3本の直線がすでに点を含んでいる。残り2点は、まだ点が含まれていない2本の $x$ 直線と2本の $y$ 直線の交点（$2 \times 2 = 4$ 個）に、互いに異なる行・列になるように配置する必要がある。この配置は対角の 2 通りである。よって、この場合は $3 \times 3 \times 2 = 18$ 通り。

（B）点 $(1, 1)$ が選ばれていない場合直線 $x=1$ 上の2点は $(1, 2), (1, 3), (1, 4)$ から2個選ぶ（${}_3\mathrm{C}_{2} = 3$ 通り）。直線 $y=1$ 上の2点は $(2, 1), (3, 1), (4, 1)$ から2個選ぶ（${}_3\mathrm{C}_{2} = 3$ 通り）。これで4個の点が選ばれた。残り1個の点は、まだ点が含まれていない1本の $x$ 直線と1本の $y$ 直線の唯一の交点に配置するしかなく、1通りに定まる。よって、この場合は $3 \times 3 \times 1 = 9$ 通り。

以上から、1組の直線に対して $(18 + 9) = 27$ 通りの配置がある。直線の選び方は16通りであったため、求める総数は

$$ 16 \times 27 = 432 $$

となる。

解法2

包含と排除の原理を利用する。 16個の点から5個選ぶすべての選び方を $S_0$ とすると、

$$ S_0 = {}_{16}\mathrm{C}_{5} = 4368 $$

「特定の $k$ 本の直線が空である」選び方の延べ数を $S_k$ とする。直線1本が空：

$$ S_1 = 2 \times {}_4\mathrm{C}_{1} \times {}_{12}\mathrm{C}_{5} = 8 \times 792 = 6336 $$

直線2本が空（$x$ から2本、$y$ から2本、$x, y$ から1本ずつの3パターン）：

$$ S_2 = 2 \times {}_4\mathrm{C}_{2} \times {}_8\mathrm{C}_{5} + {}_4\mathrm{C}_{1} \times {}_4\mathrm{C}_{1} \times {}_9\mathrm{C}_{5} = 12 \times 56 + 16 \times 126 = 672 + 2016 = 2688 $$

直線3本が空（$x$ から2本かつ $y$ から1本、またはその逆。片側3本は残りが4点になるため0通り）：

$$ S_3 = 2 \times {}_4\mathrm{C}_{2} \times {}_4\mathrm{C}_{1} \times {}_6\mathrm{C}_{5} = 48 \times 6 = 288 $$

直線4本以上が空となる選び方は、選べる点が4個以下になるためすべて0通りである。

ここで、ちょうど $k$ 本の直線が空になるような点の選び方の総数を $N_k$ とする。最大で空になる直線は3本であるため、$N_4 = N_5 = \dots = 0$ となる。 $S_k$ は、ちょうど $j$ 本（$j \ge k$）空になる事象を ${}_j\mathrm{C}_{k}$ 回重複して数えているため、以下の関係が成り立つ。

$$ S_3 = N_3 $$

$$ S_2 = N_2 + {}_3\mathrm{C}_{2} N_3 = N_2 + 3N_3 $$

(1) 求めるのはちょうど2本が空になる選び方であるから、$N_2$ を計算すればよい。

$$ N_2 = S_2 - 3S_3 = 2688 - 3 \times 288 = 2688 - 864 = 1824 $$

(2) 求めるのは空の直線が0本である選び方である。包除原理の基本式より

$$ N_0 = S_0 - S_1 + S_2 - S_3 $$

と表されるため、代入して計算する。

$$ N_0 = 4368 - 6336 + 2688 - 288 = 432 $$

解説

点と直線の包含関係を問う、場合の数の典型的な難問である。解法1のように条件を満たす配置のパターンを数え上げる方法は、場合分けの漏れや重複に注意して丁寧に整理する力が求められる。(1)において「$x$側で2本空になり、$y$側で空がない」という状況の存在を見落とさないようにしたい。解法2の包含と排除の原理は、図形的な配置の複雑さを機械的な組み合わせの計算に落とし込むことができるため、事象の定義さえ正しく行えれば非常に強力である。特に「ちょうど $k$ 個」を求める公式や導出の考え方は、難関大でたびたび威力を発揮する。