数学A / 場合の数

円周上の8点を結ぶ弦が作る領域

最難関編領域の数え上げ組合せへの翻訳

問題

円周上に8個の点があり、これらの点を結ぶどの3本の弦も、円の内部の同じ1点では交わらないものとする。8個の点のうちのすべての2点を弦で結ぶとき、円の内部は何個の領域に分かれるか。

ヒントを見る

「弦を全部引いた完成図」をいきなり数えるのは無理がある。1本ずつ引くと、1本引くたびに領域はいくつ増えるか — その弦が途中で既存の弦と交わる回数と関係づけられないか。交点の総数は、円周上の点の選び方に言い換えられる。

解答・解説

方針

弦を1本ずつ引きながら、領域がいくつ増えるかを数える: 新しい弦が既に引いた弦と k 回交わるなら、弦は k+1 個の部分に分かれ、領域は k+1 増える。だから総領域数 = 1 + (弦の本数) + (内部交点の総数)。内部交点は円周上の4点の選び方と1対1。

解答

⓪ 発想 — どう考え始めるか。 完成図の領域を直接数えるのは、 $n$ が大きいと不可能だ。1本ずつ弦を足して、増分を数える方針に切り替える。

新しい弦が既存の弦と内部で $k$ 回交わると、弦は $k + 1$ 個の線分に分かれ、その各線分が通過中の領域を2つに割る。つまり領域は $k + 1$ 増える。すると最後の総数は、「最初の1(円の内部)+ 弦の本数 + 内部交点の総数」になる。

残るは交点の総数。どの3本も1点で交わらない仮定の下では、内部交点1つ ⟷ 円周上の4点の選び方1つ(4点を選ぶと、交わるのはたすきに結んだ1組だけ)という対応で数えられる。

重要弦を1本足すと領域は(既存の弦との内部交点の数)

+ 1

増える。内部交点は円周上の4点の選び方と1対1

① 弦の本数。 8点から2点を選んで

$_{8} C_{2} = 28 本$

② 内部交点の総数。 円周上の4点を選ぶと、その4点を結ぶ6本の弦のうち内部で交わるのは「たすき」の1組だけ。逆に、内部の交点はそのような4点をただ1組決める。よって

$_{8} C_{4} = 70 個$

4点の例: 弦6本・内部交点1個(4点の選び方1通り)で、領域は 1+6+1=8 個。たすきに結んだ1組(赤)だけが内部で交わる

③ 増分を足し上げる。 何も引かないとき領域は1個。弦を1本ずつ足すと、増える数の合計は(各弦につき1)+(交点1つにつき1)だから

$1 + 28 + 70 = 99 個$

まとめ: 「1本ずつ足して増分を数える」帰納の型と、「交点を4点の選び方に翻訳する」対応の型の合わせ技。点を $2, 3, 4, 5, 6$ 個で試すと領域は $2, 4, 8, 16, 31$ 。倍々に見えて $n = 6$ で崩れるのは、正体が $1 +_{n} C_{2} +_{n} C_{4}$ だからだ(モーザーの円分割として有名)。

発展 — 一歩先へ。 「どの3本も1点で交わらない」という仮定を外すと、多重交点1つごとに領域が減る。たとえば正六角形の対角線は中心で3本が重なり、領域は31より1つ少ない30になる。仮定の一文が答えを守っている。

答

$99$ 個

別解

オイラーの公式で検算する(得意な人向け)。 平面のつながり方には、頂点 $V$ ・辺 $E$ ・面 $F$ のあいだの普遍の関係がある。

定理オイラーの公式: つながった平面図形で

V - E + F = 2

(

F

は外側の無限に広い面も数える)

この図で数えてみる。頂点は、円周上の8点と内部交点70個で $V = 8 + 70 = 78$ 。辺は、円弧が8本(8点で切られる)、弦は1本あたり(交点数+1)本に分かれるから合計 $28 + 2 \times 70 = 168$ 本(交点1つが2本の弦をそれぞれ1回ずつ切る)。あわせて $E = 8 + 168 = 176$ 。

公式から

$F = 2 - V + E = 2 - 78 + 176 = 100$

外側の面を1つ除いて、円の内部は $99$ 個。本解の増分勘定と一致した。

増分で数える(本解)か、完成図の $V, E, F$ を勘定してオイラーに任せるか。前者は過程の、後者は構造の数え方だ。2本の道が同じ99で合流すると、答えはもう動かない。

ポイント

弦1本の追加で領域は(交点数) $+ 1$ 増える。
内部交点 ⟷ 円周上の4点の選び方( $_{8} C_{4} = 70$ )。
$1 +_{8} C_{2} +_{8} C_{4} = 1 + 28 + 70 = 99$ 。

よくある間違い

領域数を $2^{n - 1}$ と即断する。 $n = 5$ までは合うが $n = 6$ で31になり崩れる。指数ではなく組合せの式が正体。
「どの3本も1点で交わらない」の仮定を使う場所を言わない。交点⟷4点の1対1対応は、この仮定があって初めて成り立つ。
弦の分割数を交点の数と同じにする。 $k$ 個の交点は弦を $k + 1$ 本の線分に分ける。