三角形の個数

平面にｎ本の直線をどの２本も平行でなく、また、
どの３本も１点で交わらないように引きます。
このとき、直線群は平面をいくつかの部分に分割します。
その分割された部分のうち、３角形になっている部分の個数を
問題にするのですが、その個数は直線群の配置によっては、異なったりします。
そこで、n本直線を引いたときできるそのような３角形の個数の最小値を
ｎの式で表してください。

何気なく作った問題ですが、いまだに解けていません。
（そういうもんかもしれないが…。）

No.11 回答者： stomachman 回答日時： 2002/01/13 15:50

自明の定理：

・任意のn本の直線が囲む領域をくっつけたものは、連結な多角形であって、n個以上の角を持つ。
・このくっつけたものが丁度n角形になるようなn本の直線の配置が存在する。
（「連結」とは、分離した、あるいは、頂点だけで接した複数の領域に分けられないこと）

・三角形の凸領域は、何本線を追加して分割しても、その断片は三角形と四角形以上の多角形凸領域を含む。
・四角形の凸領域は、何本線を追加して分割しても、その断片は四角形以上の多角形凸領域を含む。
・五角形の凸領域は、線を追加して分割しても、その断片は五角形以上の多角形凸領域を含む。
・六角形の凸領域は、線を追加して分割しても、その断片は五角形以上の多角形凸領域を含む。
・七角形の凸領域は、線を追加して分割しても、その断片は六角形以上の多角形凸領域を含む。
…
一般に、五角形以上の凸領域に、何本線を追加して分割しても、その断片は五角形以上の多角形凸領域を含む。つまり、一度作ってしまった五角形以上の領域は、あと何本線を加えても無くならない。

どうやら丁度(n-2)個の三角形が存在するためには
・直線が囲む領域をくっつけたものがn角形であること、
・五角形以上の多角形が存在しないこと、
これらが鍵らしいという気がします。そうすると、

最終予想から予想されそうなこと：
・n本の直線が囲む領域をくっつけた連結な多角形がn角形ならば、三角形の数は(n-2)以上である。
・n本の直線が囲む領域をくっつけた連結な多角形がnより多い角を持つならば、三角形の数は(n-2)より多い。
・n本の直線が囲む領域をくっつけた連結な多角形がn角形であって、かつ、その内部に五角形以上の多角形を含むならば、三角形の数は(n-2)より多い。
・三角形の数が(n-2)個ならば、n本の直線が囲む領域をくっつけた連結な多角形はn角形であって、かつ、その内部は四角形と三角形だけからなる。
・n本の直線が囲む領域をくっつけた連結な多角形がn角形であって、かつ、その内部が四角形と三角形だけからなるならば、三角形の数は(n-2)である。
・n本の直線があるとき、m本の直線を加えて、(n+m)本の直線が囲む領域をくっつけた連結な多角形が(n+m)角形になるようにできる。
・n本の直線が囲む領域をくっつけた連結な多角形がn角形ならば、直線を一本加えることによって、三角形がm>0個増え、しかも、これら(n+1)本の直線が囲む領域をくっつけた連結な多角形の角の数は(n+m)以下になる。

いや、どれも証明の手掛かりも分からないですけど。ん～なんとなくグラフの話っぽくなってきたような気が…

この回答へのお礼

ん～、ですね。
なんかすごい量の予想が提示されていて、確かめるのが大変です。
でも、がんばって考えてみます。

・このくっつけたものが丁度n角形になるようなn本の直線の配置が存在する。
（「連結」とは、分離した、あるいは、頂点だけで接した複数の領域に分けられ
ないこと）

このｎ角形というのは、凸とは限らないのですよね。つまり、どの有界領域も他の
ある有界領域と辺で接していて、かつ、すべての有界領域を合併してできる図形
は、ｎ角形であるような、ｎ本の直線の配置があるということですね。

「どうやら丁度(n-2)個の三角形が存在するためには
　・直線が囲む領域をくっつけたものがn角形であること、
　・五角形以上の多角形が存在しないこと、
　これらが鍵らしいという気がします。」
についてですが、これらは十分条件としては正しいかもしれませんが、
必要条件ではありません。反例が作れます。例えば、以前に丁度(n-2)個の三角形が
存在するn本の直線の配置の例を紹介しましたが、その配置から、半円のてっぺんに
近い交点を通る直線を一本選んで、ちょうど他の直線群がつくる交点をひとつ飛び
越えるように上のほうにずらします。すると、できる配置は、三角形の個数は変化
しませんが、有界領域全体の合併は(n-1)角形になり、5角形がひとつできます。
ただし、ｎ>=5とする。

細かく状況を追っていくやり方には無理があるような気がします。（飽く迄、気が
するというだけですが。）ガバッといっぺんに解決するような方法はないもので
しょうか？

お礼日時：2002/01/14 23:59

No.12 回答者： stomachman 回答日時： 2002/01/15 01:05

n=5で既に反例！あちゃ、f><);　No.11は１行目からハズしてしまいました。

後の予想も総崩れです。こりゃどうもいけませんね。

まとめてドカっと行きたいのはやまやま、そう行くためには問題の枠を広げて一般論を展開してしまうのが常道と思います。

じゃ今度は今度は、直線に1～nの番号を振って、マトリックスを作る。A[i,j]は直線i上の交点の内で、端から数えて何番目の交点が直線jとの交点であるか、という整数値を表す。（対角成分は無し。）
n本の直線から成る図形を一つ決めると対応するマトリックスAが決まりますが、どんなマトリックスにも対応する図形があるという訳ではない。そこで、直線３本からはじめて、直線を追加するたびに、対応する図形が存在するようにマトリックスの修正の仕方を制限する。そうやって、対応する図形が存在するマトリックスの集合を特徴付けておいて、その性質として三角形の個数をバシ！と割り出す。
なんて旨くはいかないんだろうなあ。直線を追加する規則を構成することが一番難しいみたいですから。n本の直線から成る図形で何通りのマトリックスが可能であるかを数え上げることすら手も出ません。

この回答へのお礼

早々のUPありがとうございます。

直線に1～nの番号を振って、マトリックスを作る。A[i,j]は直線i上の交点の内
で、端から数えて何番目の交点が直線jとの交点であるか、という整数値を表す。（対角成分は無し。）

という考えはまだ試したことがないので、なにか構造が発見できればおもしろい
かもしれませんね。ぼくも考えてみます。でも最近ちょっと忙しいからなあ～。
まあ、お互いゆっくりやりましょうか。

なんか怖いことを聞いたんですが、回答者の「燃えつき症候群」というやつです。
この問題、ひょっとしたらそうなる可能性があるかもしれないので、あと、１ヶ月
くらいをめどにしようかと考えています。それでよろしいでしょうか？
もうちょっと考えてくれる人が増えるといいのに…。でも、基本的に議論をするサ
イトではないようなので、数学問題専門のサイトに出した方が良かったかもしれま
せん。

お礼日時：2002/01/15 01:21

No.13 回答者： oodaiko 回答日時： 2002/01/15 13:30

＞もうちょっと考えてくれる人が増えるといいのに…

あ、実は私も考えてます。
私はある程度結果がまとまって、しかも証明がちゃんと出来るまでアップしない主義なので、こういう問題だとつい何も発言せずに終ってしまいますが。
他の質問でも、「この問題はこの定理が本質になっている（出題者はその定理を使うことを期待している）からこの定理を使えば出来るはずだ」と見抜けるものは多いのですが（学校のレポート課題はほとんどそうです）、さて自分でやってみるとなかなかうまくいかなかったりしてなんとかまとめようとしているうちに、質問者が他の回答者との途中までの議論で満足して締め切ってしまう。
あるいはなんとか仕上げても、ロジックエラーはないか、計算ミスはないか、タイプミスはないかと細かくチェックしているうちに他の人の回答が出て時間切れ、というパターンは多いです。悪しき完全主義ですかね。

とりあえず私が考えているのはstomachmanさんの回答No.8のように、直線を交差する直線を端から順に並べた順序対であらわすことで、ブロックデザインの問題に帰着できるのではないかな、ということですがこの分野の知識がないものでそれ以上進めないでいます。この問題は（グラフなり行列なりの問題に）うまく定式化出来さえすれば既存の定理で決着がつきそうに思います。難しいのはやはり条件をうまく定式化する部分だと思います。

この回答へのお礼

他にも考えている人がいるということがわかり、頼もしくなってきました。
みなさんが納得がいく回答が出せるまで、辛抱強く待つつもりなので、
ゆっくりとお考えくださいませ。
テンポの速さのみが要求される昨今、完全主義が悪くとられがちですね。
これからは、いいモノをつくるということが要求される世の中になればいいと
思っています。

お礼日時：2002/01/15 20:44

No.14 回答者： nyonta 回答日時： 2002/01/21 02:20

すいません。

回答でもなんでもないんですが、
とりあえず、「僕も考えてます。」と言いたくて・・
現在、学校の方が忙しくて、ちょっと考える時間が無いんですが、
こういう規則性を探す問題は大好きなので、もう少し時間を頂きたいです。

現在の方針としては、
直線をn本引いたときに、四角形以上（四角形、五角形、六角形・・・）が
{(n^2)-n+2}/2　個以上作れない。
の証明を試みています。（三角形がn-2個未満であることはない。と同値）

ただ、この証明もこのままでは出来なかったので（僕は）、
問題を、「リーマン幾何学っぽいモノ」での話に発展させて、
その出来た法則の一例として、上記の証明したい内容も成り立つ。
という方向で頑張ってます。

僕も、最初はグラフや行列や帰納法、的な話に帰着しようとも試みたんですが、やはりみなさんの言うように、この問題の条件を数値化(定式化)するのが困難で、図形と平面の性質の問題としてそのまま解く事にしました。

では、本当に回答でもアドバイスでも何でもありませんでしたが、
僕ももう少ししたら真剣に研究(?)したいので、どうか締め切らず待っていて下さい。
今回はお邪魔して申し訳御座いませんでした。

この回答へのお礼

いえいえ、ぜんぜんお邪魔ではないです。心強いかぎりです。
でも、この問題ってわかってみたら、案外簡単だったりして(^^)。
ぼくも数学やってる人間である以上、他の人が解いちゃうと悔しいんですけど、
こうやってみんなで知恵を出し合うというも大好きなんです。
ぼくの方も２月一杯まで忙しいので、気長に待つことにします。

お礼日時：2002/01/21 03:37

No.15 回答者： stomachman 回答日時： 2002/01/31 02:43

またしても中間報告です。

[1] 図形の表現
実数の直交座標<u,v>を持つ平面上で、k本の直線が組み合わされている配置を考える。直線はv=Au+Bで表され、A,B∈Rとする。Aは直線ごとに異なっている。直線の向きAが小さい順になるように直線に0～N-1まで番号を付けることにする。j番の直線の向きAをA(j)と書く。
j番の直線上の交点はxが小さい順に、どの直線と交差するかを表す列：X(j)=<x(j,1),x(j,2),.......,x(j,N-1)>で表されるものとする。x(j,m)∈{0,1,...,N-1}-{j}である。以下、紛らわしくない時にはXを「図形」と呼ぶ。

(? 問題1-1) 図形Xは、座標系を回転させたときにどんな図形Yに移るか?

[2] 飛び越え変換
この図形Xに新しい直線Nを追加する。εを正の微少量（無限小）として、Nの向きをA=-1/εとする。当然、∀j;A<A(j)である。原点からうんと離れた所(たとえばB=1/(ε^2))にこの新しい直線Nを置いてみると、直線N上の交点の順番は
X(N,0) =<0,1,....,N-1>
そして
X(j,0) = <x(j,1),x(j,2),.......,x(j,N-1),N>
である。
　（新しい直線Nはv軸と平行で、X(N,0)はNとの交点のv座標が小さい順になるように並べる、と言っても良い。こっちの方がわかりやすいか。でもまあともかく…）

(Lemma2-1)直線NをBが小さくなる方向へ平行移動させて行くと、一つの交点にぶつかる。この交点は直線a,bの交点だとする。(a,b∈{0,...,N-1}, a>b)。これを飛び越えると、X(N), X(a), X(b)だけが変化する。
まず、X(N)上でa,bは隣り合っているのでなくてはならない。つまり|a-b|=1 である。
つまり0≦b, a=b+1≦N-1であって、
・X(a,0) = <x(a,1),x(a,2),.......,x(a,N-1)=b,N>→X(a,1) = <x(a,1),x(a,2),.......,N,x(a,N-1)=b>
・X(b,0) = <x(b,1),x(b,2),.......,x(b,N-1)=a,N>→X(b,1) = <x(b,1),x(b,2),.......,N,x(b,N-1)=a>
・X(N,0) = <0,1,......,b,a,.....,N-1>→X(N,1) = <0,1,......,a,b,.....,N-1>
・他のX(j,1)についてはX(j,1)=X(j,0)
となる。（最初のN本の直線の配置によって、a=1～N-1のどれもがあり得る。）

　さらに直線Nを移動させて次々と交点を飛び越えていく。

(Lemma2-2)n回目に交点<a,b>(a>b)を飛び越えると、
・X(a,n-1) = <......,b,N,......>→X(a,n) = <.....,N,b,....>
・X(b,n-1) = <......,a,N,......>→X(b,n) = <.....,N,a,......>
・X(N,n-1) = <......,b,a,......>→X(N,n) = <.....,a,b,.....>　　(a>b)
・他のX(j,n)についてはX(j,n)=X(j,n-1)
という変換が生じる。（最初のN本の直線の配置によって、a=1～N-1, b=0～N-2のどれもがあり得る。）

[3] 飛び越え変換の列から図形を再構成する
　既存のN本の直線の交点はN(N-1)/2個ある。従って、直線Nを平行移動させて行くにつれて、X(N,n)上で隣り合っている要素a,b(a>b)の間で上記の変換がN(N-1)/2回行われ、しかもどの変換も、交換する2要素の組み合わせ{a,b}は異なっている。そして、N(N-1)/2回の変換の後では、
X(N,N(N-1)/2)=<N-1,.....,1,0>
X(j,N(N-1)/2) = <N,x(j,1),x(j,2),.......,x(j,N-1)>
になっていなくてはならない。この過程で、(m≠n∧X(N,m)=X(N,n))となってはならない。

(Lemma3-1)この変換の列を適用する過程で、X(j,n) (j≠N)から要素Nを除いたものは不変である。
(Lemma3-2)同じ図形Xについて、複数の変換の列が存在する。
(Lemma3-3)どの変換の列も、X(N,0)に対して、X(N,0)を要素が大きい順になるように並べ替えるsortを行う。
(Lemma3-4)n=0,1,....について、X(N,n-1)=<.....,b,a,...> (a>b)であるような隣り合う要素の対を任意に選んで、それらを入れ替える変換を繰り返すと、
・a,bを選ぶのに、どのような選び方をしても必ず丁度N(N-1)/2回の変換でsortが完了し、
・(m≠n∧X(N,m)=X(N,n))となることはなく、
・任意の２要素を指定したとき、それらの入れ替えを行う変換は、変換の列の中に丁度１度だけ現れる。
従って、N本の直線で構成される図形Xにおいて生じ得る変換の列は、全てこの中に含まれている。
(Lemma3-5)変換の列が与えられたとき、Xを再構成するのは容易である。初めに
X(j,0) = <?,?,.....,?,N> (j∈{0,....,N-1})
X(N,0) = <0,1,......, N-1>
としておき、変換をひとつづつやっていく。n回目の変換で入れ替える要素がa,bであるとき、
X(a,n-1) = <?,....,?,?,N,.......>→X(a,n) = <?,....,?,N,b,.......>
X(b,n-1) = <?,....,?,?,N,.......>→X(b,n) = <?,....,?,N,a,.......>
と書き換えていく。(Nの位置は一つ左にずれる。）これを続ければ
X(j,N(N-1)/2) = <N,x(j,1),x(j,2),.......,x(j,N-1)>
が得られる。
(Lemma3-6)あらゆる可能な変換の列に対して図形の再構成を行えば、N本の直線で構成される図形Xを網羅することができる。
(? 問題3-1)変換の列に対して図形の再構成を行って図形Xを得たとき、これに対応するN本の直線の配置は常に存在するか？

[4]三角形
　三角形とは、相異なる３つの要素を持つ集合{r,s,t}⊂{0,1,....,N}であって、
X(r,n)の中で隣り合っている要素s,t (X(r,n)=<....,s,t,.......>またはX(r,n)=<....,t,s,.......>)について
・X(s,n)の中でrとtは隣り合っている。(X(s,n)=<....,r,t,.......>またはX(s,n)=<....,t,r,.......>）
・X(t,n)の中でsとrは隣り合っている。(X(s,n)=<....,r,s,.......>またはX(s,n)=<....,s,r,.......>）
が成り立つもののことである。

(Lemma4-1)既存のN本の直線が作る図形Xにおける相異なる三角形の個数がM個であるとする。(B→∞)に新しい直線Nを加えることによって、（Nに最も近い交点<a,b>に注目すると、新しい三角形{a,b,N}が構成されるから）三角形の個数が少なくとも１個増える。
(Lemma4-2)N本の直線が作る図形において、適当に座標を回転変換して直線に番号を付け直し、X(N) =<0,1,....,N-1>とできるなら、この直線を取り除くと三角形が１個以上減る。
(Lemma4-3)この過程を繰り返して、直線の本数が3になるまで行えた場合、元の図形にはn-2個以上の三角形がある。
(Lemma4-4)この過程が不可能な図形が存在する。例えば☆型である。
(? 問題4-1)☆型の場合、適切な一つの直線を平行移動して交点を飛び越えさせることで、三角形の個数を増やさず、なおかつ、上記の過程が可能である図形に変換することができる。このような変換は常に可能か？
(Lemma4-5)ある直線を取り除いても三角形の個数が減らない図形が存在する。
(? 問題4-2)どの直線を１本取り除いても三角形の個数が減らない図形は存在するか？

この回答へのお礼

久しぶりにご報告ありがとうございます。いま、このページを開けたところ
なので、まだ読んでませんが、コピーしてじっくり読みたいと思います。
ぱっとみたところ、数々のLemmaがあって、確認するのがたいへんそうですが、
がんばって読んでみます。

お礼日時：2002/02/01 04:10

No.16 回答者： stomachman 回答日時： 2002/01/31 04:30

すいませ～ん。

No.15の訂正。

> j番の直線上の交点はxが小さい順に、
訂正：j番の直線上の交点はu座標が小さい順に、

またLemma4-2,4-3を以下のように訂正。

(Lemma4-2)N本の直線が作る図形において、適当に座標を回転変換して直線に番号を付け直し、X(N-1) =<0,1,....,N-2>とできるなら、この直線(N-1)を取り除くと三角形が１個以上減る。
(Lemma4-3)この過程を繰り返して、直線の本数が3になるまで行えた場合、元の図形にはN-2個以上の三角形がある。

No.17 回答者： stomachman 回答日時： 2002/02/02 03:21

中間報告、続きです。

　まだ問題の核心には全然迫れていません。単に幾何を離れて離散数学の領域に問題を移して、探ってみているに過ぎないところです。
　前回(No.15)の話の[1]～[3]では、N本の直線からなる配置の「座標の回転を除いて位相同型」な同値類に一意的に対応する表現である「図形」を定義しました。そして図形に対して、もう一本の直線を「プローブ」として用い、プローブを平行移動させて行くことで飛び越え変換を定義して、飛び越え変換の列から図形Xを再構成できること、ならびに、<0,1,.....,N-1>の隣り合う要素を入れ替える操作をN(N-1)/2回行って<N-1,....,1,0>に並べ替えるsortの手順の集合が、可能な「飛び越え変換の列」の集合と一致し、従って図形と対応している、ということを述べました。これでなんとか、紙に変な図形を描き散らすことなく検討できるようになったかな、という所。
　なお、[4]は三角形の個数について雑多な事を並べてみたものに過ぎません。
　どのLemmaも完璧に証明できているか、と訊かれたらごめんなさいなんですけど…

　三角形とsortの手順（飛び越え変換の列）との関係をもう少し密接に表現することを試みます。

[5] 飛び越え変換の列と、三角形
　まず[3]において導入した「飛び越え変換の列」を記号化しておきましょう。
{0,1,....,N-1}から２個の元を選ぶ組み合わせの集合を、
Cmb={c| c⊂{0,1,....,N-1} ∧ |c|=2}
とする。Cmbの濃度はN(N-1)/2で、Cmbの元はいずれも２個の元からなる集合である。
ここで1:1対応 J : {1,....,N(N-1)/2}→Cmb
を考えると、Jは２個の元から成る集合cの列（列の要素はいずれもCmbの元である）を定める。これを
J[n] (n∈{1,....,N(N-1)/2})
と書いて「変換列」と呼ぶ。
Jが「飛び越え変換列」であるとは、Jが変換列であって、さらに以下のようなN-対の列X(N,0), X(N,1).....が存在して、
・X(N,0) = <0,1,.....,N-1>
・∀n∈{1,....,N(N-1)/2}について、J[n] = {a,b} (a>b)に対して、X(N,n-1)中でb,aがこの順で隣接している箇所が存在し、つまりX(N,n-1) = <......,b,a,......> である。さらに、X(N,n)はこのa,bを入れ替えたもの X(N,n) = <.....,a,b,.....> である。
を満たすことである。

(Lemma5-1)飛び越え変換列Jにおいて、
・{p,q,r}⊂{1,....,N(N-1)/2}、p<q<r
・J[p]∩J[q] ≠φ　（φは空集合）
・J[r]=(J[p]∪J[q])-(J[p]∩J[q])　（p≠qよりJ[p]≠J[q]なので、右辺は２個の元を持つ集合になる。）
・∀s(p<s<q→J[s]∩J[p]=φ)
・∀s(q<s<r→J[s]∩J[r]=φ)
を満たす集合{p,q,r}が存在するとき、そのときに限り、Jから再構成される図形には三角形J[p]∪J[q] （=J[p]∪J[q]∪J[r]）が存在する。この集合{p,q,r}をJにおける「三角index」と呼ぶ。

　さて、二つの飛び越え変換列K,Jを考え、Kから再構成される図形と、Jから再構成される図形とが同一であるとき、これらは「同値」であると言うことにして、
K～J
と書くことにします。（～は明らかに同値関係です。）ある飛び越え変換列Jが与えられたとき、これと同値の飛び越え変換列Kは以下のようにして得られます。

(Lemma5-2)飛び越え変換列Jについて、要素J[n-1]とJ[n]を入れ替えた変換列をKとする。変換列KがJと同値の飛び越え変換列であるための必要十分条件は
J[n-1]∩J[n]=φ
である。

　特定の飛び越え変換列Jを与えたとき、「(Lemma5-2)の入れ替えが不能である」という事を順序として表現すれば、Jの要素間に半順序関係が自然に決まります。この半順序を崩さない限り、随意に並べ替えても同値という訳です。従って、

(Lemma5-3)Jの任意のひとつの三角index {p,q,r}について、Jと同値の飛び越え変換列Kを構成して、その三角indexがKの引き続く３つの要素の添字{n-2,n-1,n}に対応するようにできる。すなわち
{J[p],J[q],J[r]}={K[n-2],K[n-1],K[n]}
を満たすようにKを構成できる。
（しかし、Jと同値のある一つの飛び越え変換列K上で、Jの全ての三角indexが同時にそれぞれ、引き続く３つの要素の添字になるように並べ替えることは一般にはできない。）

　任意の飛び越え変換列において、相異なる三角indexが(N-2)個以上存在することを示せば、元の問題が解決したことになります。つまり、図形と縁を切って、飛び越え変換列の性質だけの問題に落とせると思うんです。
　一方、単なる変換列であれば、ひとつも三角indexがないように構成することが実際可能です。だから、三角indexの数は飛び越え変換列であるということと分かちがたく関連しています。ある変換列Jが飛び越え変換列であるかどうかを、X(N)のsortに依らずに、J自体の特徴で表現する必要条件が欲しいところです。
　また、飛び越え変換列全体を～で同値類に分けて代表元を選ぶ。そうすると、代表元と図形が１：１に対応する。そこで代表元について三角indexが(N-2)個以上存在することを示せば良かろう、というのがもう一つのアイデアなんですが、代表元の選び方をどのように定めれば便利なのかまだ見当が付きません。

(Lamma5-4) Jが飛び越え変換列であるとき、
X(N,0) = <0,1,.....,N-1> すなわち X(N,0)[k] = k (k=0,1,....,N-1)
とし、
J[n] = {a,b}に対して、互換
・X(N,n)[b] = X(N,n-1)[a]
・X(N,n)[a] = X(N,n-1)[b]
・X(N,n)[k] = X(N,n-1)[k] (k∈{0,...,N-1}-J[n])
を対応させると、
X(N,N(N-1)/2) = <N-1,.....,0> すなわちX(N,N(N-1)/2)[k] = N-1-k (k=0,1,....,N-1)
である。（つまりX(N,0)がsortされる。）
　これはあんまり使い途はなさそうです。

No.18 回答者： stomachman 回答日時： 2002/02/04 02:08

証明のあらすじが出来たと思うのですが、如何でしょうか。

ROMしている方もいらっしゃると思うので、例を用いながら説明します。

●直線の配置の離散表現の例
N=8の場合、
飛び越え変換列：
10, 43, 20, 53, 63, 73, 65, 40, 75, 21, 41, 42, 76, 70, 60, 71, 72, 50, 61, 30, 51, 31, 74, 62, 52, 32, 64, 54
は3角形6個、4角形13個、6角形1個を持つ図形X：
X(0)=3567421
X(1)=3567420
X(2)=3567410
X(3)=2107654
X(4)=5672103
X(5)=4210763
X(6)=4210753
X(7)=4210653
を定義し、また飛び越え変換によるプローブX(8)のsortは
01234567
10234567
12034567
21034567
21043567
21403567
24103567
42103567
42105367
42105637
42106537
42106573
42106753
42107653
42170653
42176053
42176503
42176530
42716530
42761530
42765130
42765310
47265310
47625310
47652310
47653210
74653210
76453210
76543210
＜fig-1＞
のように行われます。＜fig-1＞の、同じ数字の所を線で繋いでいったものが、図形Xに対応する直線の配置と位相同型の形になります。

●ナベゾコ
　飛び越え変換の定義から、行を追うに従って、0は右だけに、N-1は左だけに動きます。しかし1～N-2は必ず１度は両方へ動くことが容易に示せるでしょう。例えば3を見ると
３
　３
　：(0個以上の"３")
　３
３
＜fig-2＞
という風に、1～N-1には必ず少なくとも１箇所、動きの向きを変える箇所がある。このパターンを「ナベゾコ」と呼ぶことにします。(fig-2と左右鏡像でも、ナベゾコと呼びます。）すると、ナベゾコは少なくともN-2個存在します。
（なお、
３
　３
３
＜fig-3a＞
というパターンは決して現れない。なぜならこれは
３ａ
ａ３
３ａ
＜fig-3b＞
となるaが存在することを意味し、飛び越え変換の定義に矛盾します。）

●三角形とナベゾコ
　全ての三角形は、その一辺がナベゾコです。すなわち＜fig-1＞で見られる三角形{0,1,2}では
01
10
12
21
＜fig-4＞
となっていて、1のナベゾコに0と2が絡んで三角形を作っています。また三角形{5,6,7}は
56
65
65
67
76
＜fig-5＞
となっています。これは飛び越え変換列における三角indexの定義から自明に導かれます。

●三角形にならないナベゾコ
　どのナベゾコも三角形になるとは限りません。たとえば、
37
73
53
53
53
53
03
30
＜fig-6＞
の部分では、3がナベゾコですが、四角形{0,3,5,7}の一辺になっています。
　ナベゾコAが{A,b,c}という三角形の一辺にならないためには、割り込んでくる線Dが少なくとも一つ必要です。すなわち（fig-6とは左右逆になりますが）
ｂＡ
ＡｂＤ
ＡＤｂ
ＡＤ
ＡＤ
ＡＤｃ
ＡｃＤ
Ａｃ
ｃＡ
＜fig-7＞
のようになっていなくてはならない。この場合なら、Aは{A,b,c,D}という四角形の一辺になっている。そして割り込んだDもまたナベゾコになっている点に注目します。Dがこの部分でナベゾコにならないためには、
ｂＡ
ＡｂＤ
ＡＤｂ
ＡＤ
ＡＤ
ＤＡ
＜fig-8＞
のようにAと交差するしかなく、するとこれは{A,b,D}という三角形になってしまいます。

●三角形の個数≧N-2
　一方、（飛び越え変換列の定義から、）この割り込んだDは、Aとどこかで交差していなくてはならない。すなわち、Dは＜fig-7＞のパターンより上側か下側ではAより左にある筈です。ゆえに、＜fig-7＞に見られるDのナベゾコは、Dの唯一のナベゾコではあり得ず、Dは２個以上のナベゾコを持っていることが分かります。
　つまり、あるナベゾコが三角形の一辺にならないためには、少なくともあと１個余分にナベゾコが必要になります。ゆえに
(ナベゾコの数)-(三角形の一辺にならないナベゾコの数) ≧ N-2
従って、
(三角形の数)=(三角形の一辺になるナベゾコの数) ≧ N-2

この回答への補足

一つだけ疑問があります。最後の式
(ナベゾコの数)-(三角形の一辺にならないナベゾコの数) ≧ N-2
は、なぜ成り立つのでしょうか?

以下では、三角形の１辺になっているナベソコを三角ナベゾコ、そうでない
ナベゾコを非三角ナベゾコと呼ぶことにします。

「 非三角ナベゾコがひとつあったとき、その内側にナベゾコがあると、
そのナベゾコをもつ直線は、もうひとつナベゾコをもつ。」というのは、
わかりましたが、そのもうひとつが非三角ナベゾコでないという保証がないため
上の不等式は成り立たないように思うのですが、どうでしょうか？

あと、ナベゾコに関しておもしろいLemmaを発見しました。

Lemma(by sokamone)
ナベゾコの内側にナベゾコがあり、またその内側にナベゾコがあり、というように
ナベゾコの列があるとき、もっとも内側にあるナベゾコは三角ナベゾコである。

証明はいたって簡単。最も内側のナベゾコの内側に現れる数字は２種類以下である。
もし一種類だとそれは、二つの直線が二回交わることを意味する。終了。

これで非三角ナベゾコがひとつ存在すれば、必ず、三角ナベゾコがひとつ存在すること
が言えます。でも、一般に、複数の非三角ナベゾコに対して、一つの三角ナベゾコが
対応するため、これでは三角ナベゾコが少なくともN-2個存在することは言えません。
ああ、残念。

あと、stomachmanさんの理論は、こう考えるのがすっきりしていいと思います。
つまり、はじめに、N本の直線が配置されていて、それをちょうどスキャナでスキャン
するときのように、仮想的な直線ｓを頂点をひとつひとつ飛び越えるように動かしていく
(飛び越え変換)そうやって得られるN個の交点の配列を記録していき、その記録から
N本の直線の配置でできる三角形の個数に関する条件を分析する。
やっていることはまさにこういうことで、だから、N+1本目の直線を動かすのではなく
スキャナを動かしていると考えたほうがややこしくなく感じます。
幾何学ではこれはちょうどMorse関数を考えるということに対応します。
まあ、でもそれは趣味の問題なので、どうでもいいことですが（＾＾）。

補足日時：2002/02/04 12:30

No.19 ベストアンサー 回答者： stomachman 回答日時： 2002/02/05 05:42

No.18のコメントに対するResです。

> (ナベゾコの数)-(三角形の一辺にならないナベゾコの数) ≧ N-2
> は、なぜ成り立つのでしょうか?
> そのもうひとつが非三角ナベゾコでないという保証がないため
> 上の不等式は成り立たないように思うのですが、どうでしょうか？

　はい、飛ばしすぎでした。
　「そのもうひとつが非三角ナベゾコでない」ことは勿論あって、それはまた別のナベゾコ（「そのもうひとつ」を非三角たらしめているナベゾコと同じ直線上にある）の存在を要求します。存在できる場所（交点との関係）の制約から、この連鎖がループに陥ることはなく、必ず三角ナベゾコで止まる。もの凄く「アタリマエ」の感じがしているのですが、いざ説明しようとしたら道具立てが大変だと気が付きましたっす。ヒマを見て言語化していく積もりですが、そのうちモエツキるkamone。

> Lemma(by sokamone)
　仰る通りです。このとき、「そのもうひとつ」がどっさり必要になります。どっさりがまた互いに入れ子になろうとすると「そのまたもうひとつ」がまたどっさり必要で（初めの入れ子を作ってる奴らは「そのまたもうひとつ」にはなり得ない）、しかもその「またどっさり」が存在できる場所はどんどん狭くなっていく。結局三角ナベゾコの数を削ることはできない。（『分かり切ってる』のに、説明になんない。あ～もどかしいったら）

> スキャナでスキャン
　これもまさしく仰るとおりです。「N+1本目の直線を動かす」というのは、Nに関する帰納法に持ち込むというアプローチに使えるように「直線を加えていく」という操作を表現する方法も手に入れたかったためでした。しかしNo.17で「飛び越え変換列の集合＝隣接要素の互換によるsort手順の集合」が分かったので、「N+1本目の直線」は重要ではなくなりました。だからretrospectiveに整理してみると「プローブ(No.17)」（仰るとおりスキャナ）と考えるのが一番すっきりしています。Morse関数と言うんですか。
　帰納法の方向では、ある飛び越え変換列（これも専門用語があるんでしょうね）を同値でない飛び越え変換列に（図形を経由せずに）移す方法は容易に記述できたものの、一つの直線を「一番外側」にまで移す過程で三角形の数が増えたり減ったりして、「必ず増えない」を証明するのは難しそうでした。

この回答への補足

あれから6年たつのか～。お久しぶりです。質問者本人です。
あらゆる知識がデジタル化され、インターネットで検索できる
すごい時代になってきましたね。
この問題に関して検索してみたところ以下のサイトに証明が載っていました：
http://www.mathlinks.ro/viewtopic.php?t=6246
どうも数学の研究者の論文が元ネタのようです：
http://citeseerx.ist.psu.edu/viewdoc/summary?doi …
のPDFファイルをダウンロードして読んでもらえば同じ論理で証明されています。

本質的には直線で区切られた有界区画多角形の内角の問題みたいです。
★「４辺以上もつ多角形は、両端の内角の和が１８０度未満になる辺を高々２個もつ。」
という事実を証明して、線分の片側がその両端の内角の和が１８０度未満なら赤を塗り、もう片側を青に塗り、赤い線分の数に関して不等式を立てこの問題を証明しています。

つまり、線分の数をDとし、有界区画の数をF、三角形区画の数をmとすると、４辺以上もつ有界区画の数は、(F-m)なので、上の★の事実から、次の不等式が成り立つ：
D≦3m+2(F-m)=m+2F
一方、簡単な組み合わせの議論で、D=n(n-2)、F=(n-1)(n-2)/2であることがわかるので、m≧n-2
が得られる。

なんとあっさりしているのでしょう・・・。

つぎは三角領域の最大値の問題を考えてみることにします。もっと言うと三角領域の個数をnの式で表すことに挑戦してみます。いろいろなサイトを見ましたが、いまだに答えがないみたいです。

ご協力頂いたみなさまに感謝致します。

補足日時：2008/12/08 00:54

この回答へのお礼

>存在できる場所（交点との関係）の制約から、
>この連鎖がループに陥ることはなく、必ず三角ナベゾコで止まる。
>もの凄く「アタリマエ」の感じがしているのですが、
>いざ説明しようとしたら道具立てが大変だと気が付きましたっす。

たしかにその部分がたいへんですね。三角ナベゾコと非三角ナベゾコの間の
関係をもっと探ってみないといけないと思っています。
あと、Ｎ個の数字のＮ(Ｎ-1)/２個の配列が、飛び越え変換列となる条件を
もっと見つけないといけないと思っています。それは、No.15の問題3-1ですね。

個人的にはこの飛び越え変換列の考え方はとても扱いやすくて、気に入りました。
大いに利用させてもらいます。
stomachmanさんの負担がだいぶ大きくなってきていると思うので、
僕もできる限り、わかったことをレスしたいと思います。

お礼日時：2002/02/05 16:21