数学B / 漸化式と数学的帰納法

n個の円で平面を分ける領域の数(漸化式)

実戦編漸化式数え上げ幾何領域単元横断

問題

平面上に、どの $2$ つも異なる $2$ 点で交わり、どの $3$ つも $1$ 点で交わらないように $n$ 個の円をかく。これらの円が平面を分ける領域の数 $a_{n}$ を求めよ。

ヒントを見る

$n$ 個目の円は既存 $n - 1$ 個と各 $2$ 点、計 $2 (n - 1)$ 点で交わる。この $2 (n - 1)$ 点が新しい円周を $2 (n - 1)$ 個の弧に分け、各弧が領域を $1$ つ増やす。漸化式 $a_{n} = a_{n - 1} + ?$ 。

解答・解説

方針

$n$ 個目の円を追加したとき増える領域数を数える。新しい円は既存の各円と $2$ 点で交わり、円周上の交点が円周を弧に分ける。弧の数だけ領域が増える。

解答

⓪ 発想 — どう考え始めるか。 領域の数を直接数えるのは難しい。「 $1$ 個増やすと領域がいくつ増えるか」を追うのが漸化式の発想だ。

$n$ 個目の円は、既存の $n - 1$ 個の円それぞれと $2$ 点で交わる。つまり円周上に $2 (n - 1)$ 個の交点ができる。

交点は円周を $2 (n - 1)$ 本の弧に分け、各弧が既存の領域を1つずつ2分割する。だから領域は $2 (n - 1)$ 個増える。この増分の漸化式を $a_{1} = 2$ から解く。

重要

n

個目の円は既存と

2 (n - 1)

点で交わり、円周が

2 (n - 1)

個の弧に分かれて領域を

2 (n - 1)

個増やす

① 漸化式を立てる。 $1$ 個目の円は平面を内・外の $2$ 領域に分けるので $a_{1} = 2$ 。 $n$ 個目( $n \geq 2$ )を足すと領域が $2 (n - 1)$ 増えるから $a_{n} = a_{n - 1} + 2 (n - 1) .$

3個の円(どの2つも2点で交わる)は平面を 8 領域に分ける。a₃=3²−3+2=8。

② 漸化式を解く。 $a_{n} = a_{1} + k = 2 \sum n 2 (k - 1) = 2 + 2 (1 + 2 + \dots + (n - 1)) = 2 + 2 \cdot \frac{( n - 1 ) n}{2} .$

③ 整理する。 $a_{n} = 2 + n (n - 1) = n^{2} - n + 2.$ (検算: $a_{1} = 2, a_{2} = 4, a_{3} = 8$ 。 $3$ 個の円で $8$ 領域。)

まとめ 新しい円が既存と $2 (n - 1)$ 点で交わり領域を $2 (n - 1)$ 増やす、という増分から漸化式 $a_{n} = a_{n - 1} + 2 (n - 1)$ 。解いて $a_{n} = n^{2} - n + 2$ 。漸化式と数え上げ・幾何の融合。

発展 — 一歩先へ。 同じ「増分を数える」発想で、一般の位置にある $n$ 本の直線は平面を $\frac{n ^{2} + n + 2}{2}$ 個に分ける( $k$ 本目が既存の $k - 1$ 本と交わり領域を $k$ 個増やす)。円は「閉じている」分だけ増分が $2$ 倍で、領域数も速く増える。図形が空間を何分割するかは、交わり方の数え上げに帰着する。

答

$n$ 個目の円は既存の $n - 1$ 個と $2 (n - 1)$ 点で交わり、円周が $2 (n - 1)$ 個の弧に分かれて領域を $2 (n - 1)$ 個増やす。 $a_{n} = a_{n - 1} + 2 (n - 1)$ 、 $a_{1} = 2$ を解いて $a_{n} = n^{2} - n + 2$ 。

別解

別解 — オイラーの多面体公式で数える(得意な人向けの高い視点)。 円の配置を「平面のグラフ(頂点と辺)」とみて、オイラーの公式 $V - E + F = 2$ で領域数 $F$ を出す。

頂点 $V$ : 円は2つずつ $2$ 点で交わるから $V = 2 (2 n) = n (n - 1)$ 。
辺 $E$ : 各円は他の $n - 1$ 個と交わって $2 (n - 1)$ 個の交点をもち、円周が $2 (n - 1)$ 本の弧(辺)に分かれる。全部で $E = 2 n (n - 1)$ 。

オイラーの公式から

$F = E - V + 2 = 2 n (n - 1) - n (n - 1) + 2 = n (n - 1) + 2 = n^{2} - n + 2.$

( $F$ は無限に広がる外側の領域も1つと数えている。)

増分を1つずつ足す漸化式(本解)に対し、こちらは頂点・辺・面の総数を一気に数える。同じ $n^{2} - n + 2$ に、まったく別の道から着く。

ポイント

$n$ 個目の円は既存と $2 (n - 1)$ 点で交わる。
交点が円周を $2 (n - 1)$ 弧に分け、領域を $2 (n - 1)$ 増やす。
$a_{n} = a_{n - 1} + 2 (n - 1)$ 、 $a_{1} = 2$ を解いて $n^{2} - n + 2$ 。

よくある間違い

$n$ 個目の円と既存の交点数を $n - 1$ 点とする(2点ずつなので $2 (n - 1)$ 点)。
増える領域数を交点数でなく弧の数で数える必要があることを見落とす(弧 $= 2 (n - 1)$ 本 $=$ 増える領域数)。
初期条件 $a_{1} = 2$ (1個の円は内外の2領域)を $a_{1} = 1$ とする。