ベストアンサー

三角形の個数

2002/01/10 06:00

stomachmanの回答

stomachman
ベストアンサー率57% (1014/1775)

2002/01/31 02:43 回答No.15

またしても中間報告です。 [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)どの直線を１本取り除いても三角形の個数が減らない図形は存在するか？