1. 高校数学の美しい物語
  2. n本の直線の交点の数

n本の直線の交点の数

更新日時 2021/03/07
問題

平面上に nn 本の直線を引くとき,交点の数の最大値 ana_n を求めよ。

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

目次
  • 漸化式を用いた解法

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

  • 一般の位置

漸化式を用いた解法

n本の直線の交点

様子をつかむために nn が小さい場合について実験してみます。

  • n=2n=2 のとき a2=1a_2=1
  • n=3n=3 のとき a3=3a_3=3
  • n=4n=4 のとき a4=6a_4=6

交点の数をできるだけ増やすには,

  • 「今までに引いた直線に平行にならないようにする」かつ
  • 「今までにある交点を通らないようにする」

必要がありそうです。

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

解答

交点をできるだけ増やそうとすると,kk 本目の直線を引くときに新たに k1k-1 個の交点が発生するので,

ak=ak1+k1a_k=a_{k-1}+k-1

よって,この式を k=2k=2 から k=nk=n まで足し合わせると,

an=a1+1+2+3++(n1)=12n(n1)a_n=a_1+1+2+3+\cdots +(n-1)=\dfrac{1}{2}n(n-1)

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

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

解答

2本の直線に対して交点は高々1つなので,交点は最大で nC2{}_n\mathrm{C}_2 本。

  • nn 本の直線のどの2本の直線も平行でない」かつ
  • nn 本の直線のどの3本も一点で交わらない」

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

一般の位置

上記のいずれの解答中にも述べたように,交点の数が最大となるためには2つの条件が満たされる必要がありました:

  • nn 本の直線のどの2本の直線も平行でない」かつ
  • nn 本の直線のどの3本も一点で交わらない」

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

平面上に適当に直線を nn 本引くと,ほぼ100%一般の位置にある直線群が得られます(適当に,とは正確には一様分布を用いて表現します)。

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

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

工学では,起こる確率が十分0に近いような事象はスルーすることが多いです。もちろんスルーできない場合もあります。

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

Tag:漸化式の解き方11パターンと応用例まとめ

Tag:数学Bの教科書に載っている公式の解説一覧

  1. 高校数学の美しい物語
  2. n本の直線の交点の数