n本の直線の交点の数

更新日時 2021/03/07

問題

平面上に $n$ 本の直線を引くとき交点の数の最大値 $a_n$ を求めよ。

易しい問題ですが，考え方が重要かつ有名な問題なので紹介します。

漸化式を用いた解法
コンビネーションを用いた解法
一般の位置

漸化式を用いた解法
様子をつかむために
nnn
 が小さい場合について実験してみます。
n=2n=2n=2
 のとき
a2=1a_2=1a2​=1
n=3n=3n=3
 のとき
a3=3a_3=3a3​=3
n=4n=4n=4
 のとき
a4=6a_4=6a4​=6
交点の数をできるだけ増やすには，
「今までに引いた直線に平行にならないようにする」かつ
「今までにある交点を通らないようにする」必要があることが分かります。
このことに注意すると，以下の解答が思いつきます。
解答
交点をできるだけ増やそうとすると，kkk
 本目の直線を引くときに新たに
k−1k-1k−1
 個の交点が発生するので，
ak=ak−1+k−1a_k=a_{k-1}+k-1ak​=ak−1​+k−1
よって，この式を
k=2k=2k=2
 から
k=nk=nk=n
 まで足し合わせると，
an=a1+1+2+3+⋯+(n−1)=12n(n−1)a_n=a_1+1+2+3+\cdots +(n-1)=\dfrac{1}{2}n(n-1)an​=a1​+1+2+3+⋯+(n−1)=21​n(n−1)

コンビネーションを用いた解法

賢い人は一瞬で以下の解答が思いつくでしょう。

解答

2本の直線を選ぶと交点が1つ定まるので，交点は最大で ${}_nC_2$ 本。

「 $n$ 本の直線のどの2本の直線も平行でない」かつ

「 $n$ 本の直線のどの3本も一点で交わらない」

ならば任意の2本の直線の組に対して別々の交点が定まるので，実際に交点の数 ${}_nC_2$ が達成される。

一般の位置上記のいずれの解答中にも述べたように，交点の数が最大となるためには2つの条件が満たされる必要がありました：
「nnn 本の直線のどの2本の直線も平行でない」かつ
「nnn 本の直線のどの3本も一点で交わらない」
このような
nnn
 本の直線は「一般の位置にある」といいます。
平面上に適当に直線を
nnn
 本引くと，ほぼ100％一般の位置にある直線群が得られます。（「適当に」とは正確には一様分布を用いて表現します）
この「一般の位置」という考え方は，数学と現実の問題を結びつけるときに大事な概念になります。
この概念は様々な場面で登場します。「ほとんど1に近い確率で」「測度0集合上を除いて」「almost everywhere」「generic」など様々な表現がありますが，全て意味していることは同じです。
例
000 以上 111 以下の適当な実数を2つ選ぶとそれらはほぼ間違いなく一致しない
平面上に適当に3点うつと一般的には三角形ができる（同一直線上にはない）
工学では起こる確率が十分0に近いような事象はスルーすることが多いのです。もちろん一様分布が適用できない場合もあり，その場合は対称性がある場合もきちんと考える必要があります。
3回切ればケーキを7個に分割することができます（等分ではないので不公平ですが）
Tag:漸化式の解き方11パターンと応用例まとめ
Tag:数学Bの教科書に載っている公式の解説一覧