- 742 名前：１３２人目の素数さん mailto:sage [2016/03/19(土) 17:23:55.22 ID:kp1sHwcy.net]
- >>701の問題について線の数と交点の数が円の部分の数になる事をベースに問題を解いた。そしてこの事をベースにして解けるのは、
別の問題、n本の直線があり、そのどれも平行でなく、３本が同じ１点で交わることもない。いくつの部分に分けられるか。・・・①
から証明できる。
①の証明
実際、n本目の直線を追加すると1つの直線とn-1本の交点が増えるため、n個の分割が行われる。
よってn本の直線がある場合、Ln=1+(1+2+…+n)となる。
まず、数学的帰納法を使用するために、n個の点がある時に円の内部にいくつ分割が出来るかを考えなければいけない。
①より円内の分割の数はn本の直線とm個の交点の数で決まる事がわかる。よってn個の点がある時の交点の数 + 直線の数 + 1を考える。
交点の数はn個の点の内４点を選ぶと１つ交点が出来る事より、n(n-1)(n-2)(n-3)/4*3*2となり、
直線の数は一つ点が増えるごとに、n-1本直線が増えることからn(n-1)/2となる。
よって円内の分割の数はn(n-1)(n-2)(n-3)/4*3*2 + n(n-1)/2 + 1となる。
この式が正しい事を数学的帰納法により証明する。
n個の点からn+1個目の点を増やしたとき、どれだけ分割が増えるかを考えると、
交点の場合は、直線の左側にある点の数と右側にある点の数の組合わせの数で交点が決まる事が分かる。よって
nΣk=1(k-1)(n-k)となる。（一本目とn本目の時は片側にしか点が無いため0になるよって交点が存在しない）
直線の場合は、n本増えるので、合計すると
nΣk=1(k-1)(n-k) + nとなる。
n=1の時、1となり正しい
n=2の時、2となり正しい
n(n-1)(n-2)(n-3)/4*3*2 + n(n-1)/2 + 1 + nΣk=1(k-1)(n-k) + n = (n+1)n(n-1)(n-2)/4*3*2 + (n+1)n/2 + 1
以上により証明された。
|
 |
