折れ線平面問題

くの字型に折れた線n本で平面を分割できる領域の最大数を漸化式を用いて解いたらどうなるのでしょうか？

No.1 ベストアンサー 回答者： nag0720 回答日時： 2012/06/18 03:30

漸化式ではなく、一般形で解けます。

n本の直線で平面を分割できる領域の最大数は、(n^2+n+2)/2　だから、
2n本の直線では、((2n)^2+2n+2)/2=2n^2+n+1個に分割できます。

それらの直線でできる交点のうち、一番外側にある交点を選んで、その２本の直線を半直線にして「くの字型」にすれば、領域の数は２個減ります。
それをn回繰り返せば「くの字型」がn本になり、境域の数は、2n^2+n+1-2n=2n^2-n+1個になります。