じぶん更新日記

1997年5月6日開設
Copyright(C)長谷川芳典



01月のインデックスへ戻る
最新版へ戻る

 茂みの中?の時計台。数ヶ月前、時計台南西側にあった植栽が剪定され、その隙間から時計台が覗けるようになった。まるで茂みの中に時計台が出現しているように見える。


2015年01月14日(水)

【思ったこと】
150114(水)オックスフォード白熱教室(3)漸化式を使わないで解く円の最大分割問題

 昨日の続き。

 オックスフォード白熱教室から完全に脱線してしまったが、このあたりで、
円周上にn個の点をとり,円周上のすべての点どうしを直線(弦)で結ぶ。これによって分割される領域の数は、最大でいくつになるか?
という元の問題の解き方について、備忘録を兼ねて記しておくことにしたい。

 この解法は何通りかあるが、一番シンプルと思われるのは、上記の題意を満たす状態においては、分割された領域数は、

円の内部に存在する「直線の数」と「交点の数」の和プラス1

に等しいと考える解法である。

 ではなぜ、そのようになるのか。それは、まずn個の点を題意を満たすように配置し(そのように配置「できる保証」については、昨日の日記で証明したばかり)、それぞれを結ぶ直線(弦)を引く作業を始めるとする。出発点から終点に向かって線を引いていく過程では、
  1. すでに引かれている他の線と交わるたびに1つずつ
  2. そして終点にたどり着いた時点でもう1つ
領域が増えていくことが分かる。よって、1直線を引くたびに増える領域の数というのは、新たにできる交点の数(上記1.)、及び、その引いた直線の数(上記2.)の和に等しい。

 しかるに、領域の数が最大という条件のもとでは、円の内部の交点はすべて2本の線の交点であるからして、上記1.でカウントされる数は、線をすべて引き終えた時に円の内部に存在する交点の数と等しくなる。また、上記2.は、すべての直線の数と等しくなる。

 しかるに、
  • 円の内部にできる交点の総数は、n個の点から4つの点を選ぶ組合わせの数【任意の4点を選ぶと、その選び方1つに対応した1個の交点が必ずできる。なぜなら、4つの点は円周上にあるため、そのうちの3点が直線上に並ぶことはあり得ないし、円周の外にできることもない。】。よってn4。
  • 円の内部で結ばれる直線(弦)の総数は、n個の点から2つの点を選ぶ組合わせの数。よってn2。
であるからして、求める領域の数Rは、

R=n4+n2+1
=n(n−1)(n−2)(n−3)/4・3・2・1+n(n−1)/2・1+1
=(n4−6n3+23n2−18n+24)/24

となることが分かる。




 ところで、この連載の第1回のところで、

●元の問題はなぜ円でなければならないのか? 楕円ではダメなのか?

という素朴なギモンを述べた。これは、昨日の「できる保証」証明と、本日の上記の証明において、何が前提として使われているのか、その前提が円以外の単純閉曲線でも成り立つのかどうかを調べればよい。

 でもって、何が前提とされていたのかをざっと眺めると、単純閉曲線上にn個の点を配置した際、
  1. 隣り合う2点を結ぶ直線は必ず、その閉曲線の内部に引かれる。←外部に引かれてしまったのでは、領域を増やすことはできない。
  2. 隣り合う2点を結ぶ直線は、それらの点以外のところでは閉曲線とは交差しない。←交差するともっとたくさんの領域ができてしまう。
  3. 任意の4点によって作られる交点は必ずその閉曲線の内部に存在する。
などが暗黙の前提になっているように思われる。上記の3つの前提だけが必要条件というのであれば、楕円でも成り立つのではないかと思う。直観的に考えても、n個の点によって最大分割された円を縦方向や横方向に引き延ばしたり圧縮したとしても、直線がゆがむことはないし、領域の数や交点の数が増えたり減ったりすることはないから、楕円でも成り立つのではなかろうか【図2や図3参照】。
 また、外周に虫食いや突起のあるような閉曲線であっても、その一部が円(または楕円)から構成されており、配置されるn個の点がその弧の上にあり、かつ、n個の点によって形作られる多角形の外周が閉曲線からはみ出さないのであれば、点が配置されている以外の曲線部の形状は領域数の多少に影響を及ぼさないゆえ、円の場合と同じ数の領域に分割できるはずである【図4参照。もちろん、突起や凹みの部分に点を配置すれば、最大分割数はもっと増やせるであろうが。】

 次回に続く。