- ベストアンサー
三角形の個数
stomachmanの回答
- stomachman
- ベストアンサー率57% (1014/1775)
証明のあらすじが出来たと思うのですが、如何でしょうか。 ROMしている方もいらっしゃると思うので、例を用いながら説明します。 ●直線の配置の離散表現の例 N=8の場合、 飛び越え変換列： 1 0, 4 3, 2 0, 5 3, 6 3, 7 3, 6 5, 4 0, 7 5, 2 1, 4 1, 4 2, 7 6, 7 0, 6 0, 7 1, 7 2, 5 0, 6 1, 3 0, 5 1, 3 1, 7 4, 6 2, 5 2, 3 2, 6 4, 5 4 は3 角形 6個、4 角形 13個、6 角形 1個を持つ図形X： X(0)=3 5 6 7 4 2 1 X(1)=3 5 6 7 4 2 0 X(2)=3 5 6 7 4 1 0 X(3)=2 1 0 7 6 5 4 X(4)=5 6 7 2 1 0 3 X(5)=4 2 1 0 7 6 3 X(6)=4 2 1 0 7 5 3 X(7)=4 2 1 0 6 5 3 を定義し、また飛び越え変換によるプローブX(8)のsortは 0 1 2 3 4 5 6 7 1 0 2 3 4 5 6 7 1 2 0 3 4 5 6 7 2 1 0 3 4 5 6 7 2 1 0 4 3 5 6 7 2 1 4 0 3 5 6 7 2 4 1 0 3 5 6 7 4 2 1 0 3 5 6 7 4 2 1 0 5 3 6 7 4 2 1 0 5 6 3 7 4 2 1 0 6 5 3 7 4 2 1 0 6 5 7 3 4 2 1 0 6 7 5 3 4 2 1 0 7 6 5 3 4 2 1 7 0 6 5 3 4 2 1 7 6 0 5 3 4 2 1 7 6 5 0 3 4 2 1 7 6 5 3 0 4 2 7 1 6 5 3 0 4 2 7 6 1 5 3 0 4 2 7 6 5 1 3 0 4 2 7 6 5 3 1 0 4 7 2 6 5 3 1 0 4 7 6 2 5 3 1 0 4 7 6 5 2 3 1 0 4 7 6 5 3 2 1 0 7 4 6 5 3 2 1 0 7 6 4 5 3 2 1 0 7 6 5 4 3 2 1 0 ＜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}では 0 1 1 0 1 2 2 1 ＜fig-4＞ となっていて、1のナベゾコに0と2が絡んで三角形を作っています。また三角形{5,6,7}は 5 6 6 5 6 5 6 7 7 6 ＜fig-5＞ となっています。これは飛び越え変換列における三角indexの定義から自明に導かれます。 ●三角形にならないナベゾコ どのナベゾコも三角形になるとは限りません。たとえば、 3 7 7 3 5 3 5 3 5 3 5 3 0 3 3 0 ＜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
関連するQ&A
- 平面上に直線をどの2本も平行でなく、どの3本も1点で交わらないように引
平面上に直線をどの2本も平行でなく、どの3本も1点で交わらないように引いていくとき、交点の個数がｎ本でｎＣ２個となるのはなぜですか。 解答には2本の直線によって１つの交点が交わるから、と書いてあるんですが、なぜ組合せの式が出てくるのかわかりません。 たとえば2本だと２Ｃ２＝１個、3本は３Ｃ２＝3個…となっています。実際に書いてみて、そうなっていました。でもなぜその式で出るのか全く分かりません。 詳しく教えてください。
- ベストアンサー
- 数学・算数
- 緊急！数学の問題です。
平面上にｎ本の直線がある。これらの直線は、どの２直線も平行ではなく、どの３直線も１点では交わらないものとする。この時の交点の個数をｎを使って表しなさい。 答えはｎ（ｎ-1）÷2になるそうなんですが、その理由を教えてください。
- ベストアンサー
- 数学・算数
- 漸化式を利用した問題です。
一つの平面上のn本の直線がどの二本も平行でなくどの三本も同一点で交わらないとき、これらの直線がこの平面をan個の領域に分けるとする。（n は自然数） 数列{an}を求めよ。 アホでもわかるように漸化式の立て方までの解説をお願いします。
- ベストアンサー
- 数学・算数
- 高校数学、漸化式の応用
(問題）平面上にどの３本も１点で交わらないｎ本の直線がある。ｎ本の直線の中に、m本（２≦ｍ＜ｎ）平行なものがあるとき、平面がｎ本の直線によって分けられる領域の個数を求めよ。 （解答） 図のように、ｍ本の直線ｌ１、ｌ２ｌ３、、、ｌｍで平面はｍ＋１個に分けられる。Am=m+1 m≦ｋ＜ｎを満たす自然数kについて、ｋ本の直線ｌ１、ｌ２、ｌ３、、、ｌｍ、、、、ｌｋで平面がAk個の領域に分けられる時、さらに、直線ｌｋ＋１を引くと、k本の直線と交わるから領域は（ｋ＋１）個増える。 よって、Ak＋１＝Ak＋（ｋ＋１）とあるのですが、なぜ、ｋはm≦ｋ＜ｎという範囲なのでしょうか？ｋ＜ｎというのがよくわかりません。
- ベストアンサー
- 数学・算数
- 数Aの問題です
【問題】 平面上にｎ本の直線をひいたときに、直線によって分けられる部分のうち、 面積の有限な部分の個数をｆ（ｘ） 面積の無限な部分の個数をｇ（ｘ） とする ただし、どの２本の直線も平行ではなく、どの３本の直線も１店で交わることはないものとする ｆ（ｎ＋１）、ｇ（ｎ＋１）をそれぞれｎ、ｆ（ｎ）、ｇ（ｎ）を用いて表し、それを用いてｆ（６）、ｇ（６）の値をそれぞれ求めよ 私はこれを、ｎ＝４までを図示してｆ（ｘ）、ｇ（ｘ）の数をそれぞれ数え、 「よって、ｆ（ｎ＋１）＝ｆ（ｎ）＋ｎ－１、ｇ（ｎ＋１）＝ｇ（ｎ）＋２と推測できる」 としてｆ（ｎ＋１）、ｇ（ｎ＋１）を求め、ｎ＝４までは具体的に図で個数を数えたので ｆ（６）＝ｆ（５）＋４＝｛ｆ（４）＋３｝＋４＝６＋４＝１０ （ｇ（６）も同様） として求めました。 答えは合っていますが、記述式の問題だと「推測できる」としてはっきり根拠がないので満点はもらえないでしょう。 もしこの解答の補足をするならどのようにすべきでしょうか？ よろしくお願いします；
- ベストアンサー
- 数学・算数
- 平面による空間の分割の問題です（質問し直します）
大学への数学「マスター・オブ場合の数」の中の研究問題です。 空間をどの２つの交わりも直線で、どの３つの交わりは1点で、どの４つをとっても共有点が 無いようなｎ個の平面を分割するときの、領域の数の問題ですが、 まず、平面をｎ本の直線で、どの２本も１点で交わるが、どの３本も１点では交わらないように 分割するときの、領域の個数は（ｎ^2＋ｎ＋２）/２－(1)です。 また、空間において、ｋ－１枚の平面で作られた領域がｆ（ｋ－１）個に分割されていたとして、 これにｋ枚目の平面を題意のようにおいた時、ｋ枚目の平面上の、他の平面との交線で分け られた１つ１つの領域は、それまですでにあった空間領域の１つを２つに分ける‘面’であるの で、ｋ枚目の平面によって、空間領域は、（（ｋ－１）^2＋（ｋ－１）＋２）/２個増える。 よって、１＋∑［ｎ、Ｋ＝１］（（ｋ－１）^2＋（ｋ－１）＋２）/２＝（ｎ^3＋５ｎ＋６）とあります。 ようするに、ｋ枚目の平面を入れると、ｆ（ｋ－１）個の領域が増えるとなっていますが、 分からないのは、ｆ（ｋ－１）＝（（ｋ－１）^2＋（ｋ－１）＋２）/２－(2)ということなので、 平面の領域の個数（ｎ^2＋ｎ＋２）/２にｎ＝ｋ－１を代入すると、(2)になりますが、 例えば、添付画像の３（＝ｋ－１と考えて）本の領域には７個の領域がありますが、 ４（＝ｋと考えて）本目の直線を引くと、７個の領域が増えると言った内容の説明があります。 空間の領域の個数を求める問題であるのに、なぜ、平面での増えた領域の数が空間の領域 の数が対応するのかが理解出来ません。 Tacosan様、先ほどは失礼いたしました、改めて質問させて頂きます。 何卒宜しくお願い致します。
- ベストアンサー
- 数学・算数
補足
一つだけ疑問があります。最後の式 (ナベゾコの数)-(三角形の一辺にならないナベゾコの数) ≧ N-2 は、なぜ成り立つのでしょうか? 以下では、三角形の１辺になっているナベソコを三角ナベゾコ、そうでない ナベゾコを非三角ナベゾコと呼ぶことにします。 「 非三角ナベゾコがひとつあったとき、その内側にナベゾコがあると、 そのナベゾコをもつ直線は、もうひとつナベゾコをもつ。」というのは、 わかりましたが、そのもうひとつが非三角ナベゾコでないという保証がないため 上の不等式は成り立たないように思うのですが、どうでしょうか？ あと、ナベゾコに関しておもしろいLemmaを発見しました。 Lemma(by sokamone) ナベゾコの内側にナベゾコがあり、またその内側にナベゾコがあり、というように ナベゾコの列があるとき、もっとも内側にあるナベゾコは三角ナベゾコである。 証明はいたって簡単。最も内側のナベゾコの内側に現れる数字は２種類以下である。 もし一種類だとそれは、二つの直線が二回交わることを意味する。終了。 これで非三角ナベゾコがひとつ存在すれば、必ず、三角ナベゾコがひとつ存在すること が言えます。でも、一般に、複数の非三角ナベゾコに対して、一つの三角ナベゾコが 対応するため、これでは三角ナベゾコが少なくともN-2個存在することは言えません。 ああ、残念。 あと、stomachmanさんの理論は、こう考えるのがすっきりしていいと思います。 つまり、はじめに、N本の直線が配置されていて、それをちょうどスキャナでスキャン するときのように、仮想的な直線ｓを頂点をひとつひとつ飛び越えるように動かしていく (飛び越え変換)そうやって得られるN個の交点の配列を記録していき、その記録から N本の直線の配置でできる三角形の個数に関する条件を分析する。 やっていることはまさにこういうことで、だから、N+1本目の直線を動かすのではなく スキャナを動かしていると考えたほうがややこしくなく感じます。 幾何学ではこれはちょうどMorse関数を考えるということに対応します。 まあ、でもそれは趣味の問題なので、どうでもいいことですが（＾＾）。