トップ› 九州大学› 2002年› 文系第5問

九州大学 2002年文系第5問解説

方針・初手

(1), (2), (3) すべてにおいて、領域分割の基本である「新しい図形（直線や折れ線）を追加したときに、領域がいくつ増えるか」を考える。すでにある図形との交点の個数を数え、追加した図形がいくつの線分（または半直線）に分割されるかを調べることで、増加する領域の数を求める漸化式を立てることができる。

解法1

(1)

$n-1$ 本の直線で分割された平面に、$n$ 本目の直線を追加したときの領域の増加分を考える。 $n$ 本目の直線は、既存の $n-1$ 本の直線のそれぞれと交わるため、$n-1$ 個の交点を持つ。条件 (ii) より、任意の $3$ 直線は同一点で交わらないため、これらの交点はすべて異なる。 $n$ 本目の直線は、これら $n-1$ 個の交点によって、$n$ 個の線分または半直線に分割される。この分割された $n$ 個の線分または半直線のそれぞれが、既存の領域を $2$ つに分割するため、領域は新たに $n$ 個増加する。したがって、$n \geqq 2$ のとき、$L_n$ と $L_{n-1}$ の間の関係式は以下のように表される。

$$L_n = L_{n-1} + n$$

$n=1$ のとき、平面は $1$ 本の直線によって $2$ つの領域に分割されるので、$L_1 = 2$ である。 $n \geqq 2$ のとき、数列 $\{L_n\}$ の階差数列が $n$ であるから、

$$\begin{aligned} L_n &= L_1 + \sum_{k=2}^{n} k \\ &= 2 + \frac{1}{2} n(n+1) - 1 \\ &= \frac{n^2 + n + 2}{2} \end{aligned}$$

この式は $n=1$ のとき $\frac{1+1+2}{2} = 2$ となり、$n=1$ でも成立する。よって、$L_n = \frac{n^2 + n + 2}{2}$ である。

(2)

$1$ 本の $1$ 回折れ線は、平面を $2$ つに分割するので $H_1 = 2$ である。次に、$n-1$ 本の $1$ 回折れ線で分割された平面に、$n$ 本目の折れ線を追加したときの領域の増加分を考える。 $n$ 本目の折れ線は、既存の $n-1$ 本の折れ線と、それぞれ $4$ 点で交わる。条件 (ii) より、任意の $3$ 本の折れ線は同一点で交わらないため、これらの $4(n-1)$ 個の交点はすべて異なる。また、折れ線は $1$ 回折れ曲がっているため、自身の「頂点」を $1$ つ持つ。したがって、$n$ 本目の折れ線上には、他の折れ線との交点 $4(n-1)$ 個と、自身の頂点 $1$ 個の、合計 $4n-3$ 個の「分割点」が存在する。 $n$ 本目の折れ線は、これらの $4n-3$ 個の点によって、$(4n-3) + 1 = 4n - 2$ 個の線分または半直線に分割される。これら $4n-2$ 個の線分または半直線のそれぞれが、既存の領域を $2$ つに分割するため、領域は新たに $4n-2$ 個増加する。したがって、$H_n$ と $H_{n-1}$ の間の関係式は以下のようになる。

$$H_n = H_{n-1} + 4n - 2$$

これを用いて $H_3$ を求める。まず、$n=2$ のとき、

$$H_2 = H_1 + 4 \cdot 2 - 2 = 2 + 6 = 8$$

次に、$n=3$ のとき、

$$H_3 = H_2 + 4 \cdot 3 - 2 = 8 + 10 = 18$$

(3)

(2) で求めた漸化式 $H_n - H_{n-1} = 4n - 2$ を用いる。 $n \geqq 2$ のとき、数列 $\{H_n\}$ の階差数列が $4n-2$ であるから、

$$\begin{aligned} H_n &= H_1 + \sum_{k=2}^{n} (4k - 2) \\ &= 2 + 4 \sum_{k=2}^{n} k - \sum_{k=2}^{n} 2 \\ &= 2 + 4 \left( \frac{1}{2} n(n+1) - 1 \right) - 2(n-1) \\ &= 2 + 2n^2 + 2n - 4 - 2n + 2 \\ &= 2n^2 \end{aligned}$$

この式は $n=1$ のとき $2 \cdot 1^2 = 2$ となり、$n=1$ でも成立する。よって、$H_n = 2n^2$ である。

解説

平面の領域分割における典型問題である。直線を引くごとに「既存の図形との交点がいくつできるか」を数え、それによって「追加した図形がいくつの部分に分割されるか」を調べるのが定石である。追加した図形の分割された部分（線分や半直線）の数だけ、新たな領域が増加する。 (2) の $1$ 回折れ線の場合は、他の折れ線との交点に加えて、自身の「折れ曲がる頂点」も分割点としてカウントする必要があることに注意したい。