2014/06/03

n本の直線の交点の数

分野: 場合の数  レベル: 基本公式

問題

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


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

漸化式を用いた解法

n本の直線の交点

様子をつかむために $n$ が小さい場合について実験してみます。
$n=2$ のとき $a_2=1$
$n=3$ のとき $a_3=3$
$n=4$ のとき $a_4=6$

交点の数をできるだけ増やすには,
「今までに引いた直線に平行にならないようにする」かつ
「今までにある交点を通らないようにする」
必要があることが分かります。

このことに注意すると,以下の解答が思いつきます。

解答

交点をできるだけ増やそうとすると,$k$ 本目の直線を引くときに新たに $k-1$ 個の交点が発生するので,
$a_k=a_{k-1}+k-1$
よって,この式を $k=2$ から $k=n$ まで足し合わせると,
$a_n=a_1+1+2+3+\cdots +(n-1)=\dfrac{1}{2}n(n-1)$

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

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

解答

2本の直線を選ぶと交点が1つ定まるので,交点は最大で${}_nC_2$ 本。
「 $n$ 本の直線のどの2本の直線も平行でない」かつ
「 $n$ 本の直線のどの3本も一点で交わらない」

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

一般の位置

上記のいずれの解答中にも述べたように,交点の数が最大となるためには2つの条件が満たされる必要がありました:
「 $n$ 本の直線のどの2本の直線も平行でない」かつ
「 $n$ 本の直線のどの3本も一点で交わらない」

このような $n$ 本の直線は「一般の位置にある」といいます。

平面上に適当に直線を $n$ 本引くと,ほぼ100%一般の位置にある直線群が得られます。(「適当に」とは正確には一様分布を用いて表現します)
この「一般の位置」という考え方は,数学と現実の問題を結びつけるときに大事な概念になります。

この概念は様々な場面で登場します。「ほとんど1に近い確率で」「測度0集合上を除いて」「almost everywhere」「generic」など様々な表現がありますが,全て意味していることは同じです。

  • $0$ 以上 $1$ 以下の適当な実数を2つ選ぶとそれらはほぼ間違いなく一致しない
  • 平面上に適当に3点うつと一般的には三角形ができる(同一直線上にはない)

工学では起こる確率が十分0に近いような事象はスルーすることが多いのです。もちろん一様分布が適用できない場合もあり,その場合は対称性がある場合もきちんと考える必要があります。

3回切ればケーキを7個に分割することができます(等分ではないので不公平ですが)

Tag: 漸化式の解き方と応用例まとめ
Tag: 数学Bの教科書に載っている公式の解説一覧

分野: 場合の数  レベル: 基本公式