東京大学 2020年度文系数学第2問解答・解説

問題

座標平面上に8本の直線

x = a (a = 1, 2, 3, 4), y = b (b = 1, 2, 3, 4)

がある。以下，16個の点

(a, b) (a = 1, 2, 3, 4, b = 1, 2, 3, 4)

から異なる5個の点を選ぶことを考える。

(1) 次の条件を満たす5個の点の選び方は何通りあるか。
上の8本の直線のうち，選んだ点を1個も含まないものがちょうど2本ある。

(2) 次の条件を満たす5個の点の選び方は何通りあるか。
上の8本の直線は，いずれも選んだ点を少なくとも1個含む。

出典：東京大学 2020年度前期日程第2次学力試験文系第2問

方針

解法1（空行・空列の本数で場合分けする方法）

選んだ点を含まない行数を $r$ 、列数を $c$ とする。(1)は $r + c = 2$ の3場合に分け、残った格子の全行・全列を使うように数える。(2)は行・列の点数分布がともに $2, 1, 1, 1$ になることを使う。

解法2（包除原理で使用行・使用列を数える方法）

$p \times q$ 格子から5点を選び、全 $p$ 行・全 $q$ 列を使う個数を包除原理で求める。(1)は使用行数と使用列数が $(2, 4), (3, 3), (4, 2)$ の場合を足し、(2)は8本の行・列が空になる事象に直接包除原理を適用する。

解答

解法1（空行・空列の本数で場合分けする方法）

4本の横線を「行」、4本の縦線を「列」と呼ぶ。

(1)

空の行数を $r$ 、空の列数を $c$ とすると

r + c = 2.

$r = 2, c = 0$ のとき、使う2行の選び方は $_{4} C_{2} = 6$ 通りである。残る $2 \times 4$ 格子で全4列を使って5点を選ぶには、1列に2点、他の3列に1点ずつ置く。2点を置く列は4通り、他の3列では上下を選べるので

6 \cdot 4 \cdot 2^{3} = 192

通りである。対称性から $r = 0, c = 2$ も192通りである。

$r = 1, c = 1$ のとき、空の1行と1列の選び方は $4 \cdot 4 = 16$ 通りである。残る $3 \times 3$ 格子から5点を選び、3行3列をすべて使う。全体は $_{9} C_{5}$ 通りで、さらに空になる1行を指定した選び方は $_{6} C_{5}$ 通り、空になる1列についても同様である。2本以上がさらに空なら残る点は高々4個なので、5点を選べない。よって

_{9} C_{5} - 3_{6} C_{5} - 3_{6} C_{5} = 126 - 18 - 18 = 90.

したがってこの場合は $16 \cdot 90 = 1440$ 通りである。合計は

192 + 1440 + 192 = 1824.

(2)

5点で4行をすべて使うから、行ごとの点数分布は $2, 1, 1, 1$ である。列についても同じである。2点を含む行を $R$ 、2点を含む列を $C$ とすると、その選び方は

4 \cdot 4 = 16

通りである。

交点 $R \cap C$ を選ぶ場合、 $R$ 上のもう1点の列が3通り、 $C$ 上のもう1点の行が3通りである。残る2行と2列を1対1に対応させる方法が2通りなので

3 \cdot 3 \cdot 2 = 18

通りである。

交点 $R \cap C$ を選ばない場合、 $R$ 上で使う2列の選び方と $C$ 上で使う2行の選び方がそれぞれ $_{3} C_{2}$ 通りである。最後の点の位置は一意に決まるから

_{3} C_{2}_{3} C_{2} = 9

通りである。よって

16 (18 + 9) = 432.

以上より、答えは

(1) 1824 通り, (2) 432 通り .

解法2（包除原理で使用行・使用列を数える方法）

(1)

空の直線が2本なら、使用する行数と列数の組は

(2, 4), (3, 3), (4, 2)

のいずれかである。

$2 \times 4$ 格子では5点を選べば2行は自動的に使われる。全4列を使わない選び方を除くと

N_{2, 4} =_{8} C_{5} - 4_{6} C_{5} = 56 - 24 = 32.

$3 \times 3$ 格子では、1行または1列を空にする選び方を除けばよい。2本以上をさらに空にすると残る点が4個以下になるので、補正項はない。よって

N_{3, 3} =_{9} C_{5} - 6_{6} C_{5} = 126 - 36 = 90.

使用する行と列の選び方も掛けると

_{4} C_{2} N_{2, 4} +_{4} C_{3}_{4} C_{3} N_{3, 3} +_{4} C_{2} N_{4, 2} = 6 \cdot 32 + 16 \cdot 90 + 6 \cdot 32 = 1824.

(2)

16点から5点を選ぶ全選択は $_{16} C_{5}$ 通りである。8本の行・列のいずれかが空になる事象に包除原理を用いる。

1本を空にすると残り12点なので、1次の項は

8_{12} C_{5} .

2本を空にする場合、同方向の2本なら残り8点で、その組は $2_{4} C_{2}$ 組、行と列を1本ずつなら残り9点で16組ある。3本では、同方向2本と他方向1本の場合だけ5点を選べ、残り6点、その組は

2_{4} C_{2} \cdot 4

組である。4本以上を空にすると残る交点は高々4個なので寄与しない。

したがって求める個数は

_{16} C_{5} - 8_{12} C_{5} + {2_{4} C_{2}_{8} C_{5} + 16_{9} C_{5}} - 2_{4} C_{2} \cdot 4_{6} C_{5} = 4368 - 6336 + (672 + 2016) - 288 = 432.

東京大学 2020年度文系数学 第2問

問題

方針

解法1（空行・空列の本数で場合分けする方法）

解法2（包除原理で使用行・使用列を数える方法）

解答

解法1（空行・空列の本数で場合分けする方法）

(1)

(2)

解法2（包除原理で使用行・使用列を数える方法）

(1)

(2)

東京大学 2020年度
文系数学第2問