OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
解決
済み

三角形の個数

  • 暇なときにでも
  • 質問No.195687
  • 閲覧数755
  • ありがとう数11
  • 気になる数0
  • 回答数19
  • コメント数0

お礼率 76% (38/50)

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

何気なく作った問題ですが、いまだに解けていません。
(そういうもんかもしれないが…。)
通報する
  • 回答数19
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.19
レベル14

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

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

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

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

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

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

お礼率 76% (38/50)

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

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

つまり、線分の数をDとし、有界区画の数をF、三角形区画の数をmとすると、4辺以上もつ有界区画の数は、(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:46
お礼コメント
sokamone

お礼率 76% (38/50)

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

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

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

その他の回答 (全18件)

  • 回答No.6
レベル14

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

既にある多角形の外部にひとつも新しい三角形を作らないように直線cを加えることができたとします。 この直線cは、既にある多角形の内部を通過しているが、そのうち三角形ではない少なくとも一つの多角形から三角形を切り取ってしまう。 これが証明したい定理の残りの部分ですね。 部分的に検討してみました。 まず、既にある多角形というのは全て凸多角形、つまり内角が180度以下である。これは自明です。だから ...続きを読む
既にある多角形の外部にひとつも新しい三角形を作らないように直線cを加えることができたとします。
この直線cは、既にある多角形の内部を通過しているが、そのうち三角形ではない少なくとも一つの多角形から三角形を切り取ってしまう。

これが証明したい定理の残りの部分ですね。
部分的に検討してみました。

まず、既にある多角形というのは全て凸多角形、つまり内角が180度以下である。これは自明です。だから直線cは高々2点でしか多角形の辺と交わらない。

*cが通過している多角形が全部三角形である、という場合。まずこれらの三角形を構成していない直線を全部取り除いて考える。そのどれかの三角形の辺のうち、cが通過していないやつを構成している直線(少なくとも2本ある)とcとの交点が外部に三角形を作ってしまう。これを妨害するような直線(ただし問題にしているどの三角形の内部も通過してはいけない)を加えても、やっぱりその加えた直線が外部にcを一辺とする三角形を作るか、或いはcが通過しているような多角形を作ってしまって、「cが通過している多角形が全部三角形」という条件を満たさなくなる。ということが言えそうに思います。

*cが通過している多角形のうち三角形でないものがあるとします。
cが通過している多角形のうち、三角形は無視して、四角形以上の多角形だけを取り出してみます。この多角形を構成する辺のうち、隣り合っていない2つの辺d,eをcが通過するのなら、三角形は作らない。そうすると、cが通過していない残りの辺が少なくとも2つあります。そして、(d,e),(a,b), (a,c),(b,c)という5つの交点は全てこの多角形の外部にある。直線a上で、交点(a,b),(a,c),(a,d),(a,e)、という順番に並んでいるとすると、直線b上では交点(a,b),(b,d),(b,e),(b,c)という順番でなくてはならない。四角形の場合ならこれで直線に名前が一意的についたと思います。
さてもし直線d上で、(d,e)(d,b)(d,c)(d,a)という順番に交点が並んでいるとすると、直線e上では(e,d)(e,b)(e,c)(e,a)の順になっている。従って、(c,e)(c,b)(b,e)という三角形が出来ている。
これが既存の三角形の一部を切り取った物であるためには、(b,e)(a,e)を2頂点とする三角形が必要ですが、(b,a)はこっち側では交差してくれない。だからこれはない。
また、既存の多角形の外部に三角形ができちゃうのは、最初から禁止でした。
ゆえに、注目している多角形の内部を通過しない直線fがもう一本必要です。(多角形の内部を分割する線があってはいけないのは自明)
もし、fが(b,f)(b,e)(a,e)(a,f)を頂点とする多角形を作っていて、cがこの多角形の隣合わない辺を通過しているんだとすると、直線dを取り除いてもこの議論に帰着する。(dの代わりにa,b,e,fを辺とする多角形を考えれば、(f,c)(f,b)(b,c)の三角形が問題になる。)
するってえと、fの引きようがない。

なんかそんな感じで、うまくまとめられないかと思っていますが、難しいなあ。
補足コメント
sokamone

お礼率 76% (38/50)

なんだか複雑で、ちゃんと論理を追えているかどうか自信がないのですが、
2つ疑問点があります。一つ目は、
「…。そして、(d,e),(a,b), (a,c),(b,c)という5つの交点は全てこの多角形の
外部にある。直線a上で、交点(a,b),(a,c),(a,d),(a,e)、という順番に並んでい
るとすると、直線b上では交点(a,b),(b,d),(b,e),(b,c)という順番でなくてはならない。」
の部分ですけど、5つの交点というのは明らかに書き間違えですよね。それは置い
といて、最後の直線b上の4つの交点の順番は、(b,c),(a,b),(b,d),(b,e)という
のは駄目なのでしょうか?そういう場合もあると思うのですが。
二つ目は、その少し下の、
「…。従って、(c,e)(c,b)(b,e)という三角形が出来ている。」
に関してですが、なぜ、3角形になるのでしょうか?それは、線分(e,b)-(e,c),
線分(b,e)-(b,c),及び,線分(c,b)-(c,e)上に他の交点がないということを示さな
いといけないと思うんですが、それは、明らかなのでしょうか?
投稿日時 - 2002-01-12 01:53:23

  • 回答No.7
レベル14

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

どうもいい加減な話を書くと、あちこちボロが出ますね。申し訳ない。飽くまでひとつの方針と、考察の一例をご参考までにupしてみただけです。 (1) No.6の三角形だけ通る場合について。 ご指摘の通りですね。3つの直線が1点で交わらない限り2つ以上の三角形だけを通ることは起こらない。ですから、三角形1個を通過する場合だけ検討すれば十分ということですね。流石です。 (2) No.6で言っているa, ...続きを読む
どうもいい加減な話を書くと、あちこちボロが出ますね。申し訳ない。飽くまでひとつの方針と、考察の一例をご参考までにupしてみただけです。

(1) No.6の三角形だけ通る場合について。
ご指摘の通りですね。3つの直線が1点で交わらない限り2つ以上の三角形だけを通ることは起こらない。ですから、三角形1個を通過する場合だけ検討すれば十分ということですね。流石です。

(2) No.6で言っているa,bは多角形を作っている直線のうちで、多角形の辺上でcと交差していないもののことです。ここでは具体的には四角形をイメージして話をしています。5角形以上の時、議論がそのまま使えるかどうかは要検討事項です。
(3) ご指摘の通り、いささか混乱してます。
> 最後の直線b上の4つの交点の順番は、(b,c),(a,b),(b,d),(b,e)という
>のは駄目なのでしょうか?そういう場合もあると思うのですが。
直線a上で(a,b),(a,c),(a,d),(a,e)の順である場合、
 直線b上で(b,c),(a,b),(b,d),(b,e)
 直線b上で(a,b),(b,d),(b,e),(b,c)
の二通りが確かにあります。で、その後の議論は直線b上で(b,c),(a,b),(b,d),(b,e)となる場合について言っている。(場合分けして処理するつもりが、途中で忘れちゃったらしいです。すいません。)
(4) 方針としては、串刺しにされている多角形が、隣合う多角形に「cは三角形でない多角形から三角形を切り取らない」という条件を押しつけて行く。そうするとどうしても最後にはこの条件を満たせなくなる、というストーリーです。
 このとき、新しい直線f,g,h,....をどんどん加えてcが新しい三角形を構成するのを妨害しても良い。ただし制限を課す。「cを除き、既存の(n-1)本及び加えたf,g,h,..が構成する三角形の個数は、cを加えても増えないようにする。(ですからf,g,h,....は、cが通過しないところに幾つ多角形や三角形を作ろうと、かまわない)」 そういう加え方がないことを証明しようというわけです。
 この考え方は、要するに、「どんな既存の2本以上の直線の配置においても、新たに1本直線を加えるとかならず三角形が増える」という、強い定理を証明しようということです。

 元々の目的では「(n-1)本の直線が(n-2)個以上の三角形を作っている場合、新たに1本直線を加えても、三角形の個数は(n-2)以上である。」を示せば良いのですが、それよりも強い定理であることはお分かりでしょう。

 一方、無限遠点を考える代わりに、球面幾何でやってみたらどうか、とも思っています。全ての領域が閉じた多角形になるので扱いやすいかもしれないと思ったんです。この場合、直線=大円であり、地球の表側と裏側に同じ図形が対になって発生します。いや、この方向ではまだ何も進展していませんが。

 面白い問題ですね。通常、質問の意図が分からないとき以外は「回答に自信なし」だったらupしないのですが、余り面白いので自信なしを連発しています。お邪魔なら言ってね。
お礼コメント
sokamone

お礼率 76% (38/50)

いえいえ全然邪魔ではないです。実は私、大学院で変換群論を研究している学生
なのですが、ひまつぶしに考えた問題があなたの仰るように結構おもしろく、
かつ、私にとっては難解だったため、ここに投稿した次第です。過去ログをみた
ところ、stomachmanさんは物理学方面に造詣が深いみたいで、大変心強く感じて
います。まるで、共同研究をやっているみたいでとても楽しいです。この場所で
是非ともこの問題を解決させたいものです。

球面を考えるという発想は、友人と話しているときに出てきましたが、あまり、
利点はなかったように記憶してます。
投稿日時 - 2002-01-12 14:59:52
  • 回答No.8
レベル14

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

ぬわんと、専門家じゃないですかあ。だったら、別件ながら是非下記URLの問題をエレガントに解決するのにお力をお貸し願えませんでしょうか。 さて、これまでの方針であった補助定理「どんな配置であれ、そこに直線を追加すると、かならず三角形が増える」には反例が見つかってしまいました。(当初の予想:「三角形は(n-2)個以上」の反例ではありませんが) 直線a,b,d,e,f,gから構成される図形に直線cを加え ...続きを読む
ぬわんと、専門家じゃないですかあ。だったら、別件ながら是非下記URLの問題をエレガントに解決するのにお力をお貸し願えませんでしょうか。

さて、これまでの方針であった補助定理「どんな配置であれ、そこに直線を追加すると、かならず三角形が増える」には反例が見つかってしまいました。(当初の予想:「三角形は(n-2)個以上」の反例ではありませんが)
直線a,b,d,e,f,gから構成される図形に直線cを加えます。
直線pと交差する直線を端から順に並べた順序対をXpと書くことにして
Xa = <b,c,d,e,f,g>
Xb = <a,d,e,g,f,c>
Xc = <a,d,e,f,g,b>
Xd = <g,b,c,a,f,e>
Xe = <g,b,c,a,f,d>
Xf = <b,g,c,a,e,d>
Xg = <d,e,b,f,c,a>
となるように配置しますと、直線cを引っこ抜いても三角形の個数は変化せず、6個のままです。cを除く6本の直線は四角形以上の多角形を全部で4個構成しています。
cは2個の三角形abd, afg、1個の四角形adbe、1個の五角形aebgfを通過し、さらに既存の多角形の外部に四角形cgfbを生成します。

という訳で、方針を大転換しなくちゃなりません。どうしたものでしょう?
お礼コメント
sokamone

お礼率 76% (38/50)

なるほど、確かにその例は反例になってますね。
直線cを追加したとき、三角形が増えないような例があるとしたら、
直線cがすでにあった半直線と三角形を作らないように交わるようなもの
だろうなと思っていました。ちょうどこの例がそうですね。
なかなか証明できないから、反例があるんじゃないかと思ってたところでした。

さあ、どうしたものでしょう。昔考えたことに、直線を少しずつ残りの直線群の
つくる交点を飛び越える形でずらしていくことで三角形の個数を操作できないか
というのがあります。でも、いろんなバリエーションがあって、とても手に負え
ませんでした。しんどかったことだけ記憶してます。でも、stomachmanさんなら
できるかも知れませんね。ぼくももうちょっとがんばって考えてみます。
投稿日時 - 2002-01-13 01:22:32
  • 回答No.5
レベル14

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

…と思ってUPした直後に、アレ?となりました。No.4は間違いです。 「最後に引く直線cに最も近い、既存の交点(a,b)を選ぶと(a,b)(a,c)(b,c)の三角形の中を通る直線はない。」 という補題は、既に存在しているどれかの三角形Tを構成する3つの交点のうちの一つが、最後に引く直線cに最も近い交点であって、しかもcが三角形Tの内部を通る場合、新しい三角形を作ると同時に、もとの三角形を破壊して ...続きを読む
…と思ってUPした直後に、アレ?となりました。No.4は間違いです。

「最後に引く直線cに最も近い、既存の交点(a,b)を選ぶと(a,b)(a,c)(b,c)の三角形の中を通る直線はない。」
という補題は、既に存在しているどれかの三角形Tを構成する3つの交点のうちの一つが、最後に引く直線cに最も近い交点であって、しかもcが三角形Tの内部を通る場合、新しい三角形を作ると同時に、もとの三角形を破壊してしまいますから、これだけじゃ「三角形が増える」という保証になってはいませんでした。失敗です。

 「直線cに最も近い既存の交点(a,b)」というのはなかなか良いアイデアのようですけど、これだと「既存の三角形から切り取った三角形(三角形の個数は増えない)」と「既存の多角形の外部にできた新しい三角形、あるいは既存の多角形から切り取った三角形(個数が増える)」との区別ができないように思います。
 新しく加えた直線が、既にある多角形を通過する場合を考えますと、既存の多角形の内部を分割することは、
イ)三角形を三角形と四角形に分けるか、
ロ)四角形以上の多角形を四角形以上の多角形2個に分けるか、
ハ)四角形以上の多角形を三角形と四角形以上の多角形に分けるか、
であって、どれも三角形の数を減らすことはありません。そして直線を1本加えると(ハ)が生じるか、もしくは既存の多角形の外部に新しい三角形を作るか、その少なくともどちらかが起こると言えれば良いのです。んで、「どの直線を選んでも、残りの直線が構成する多角形の外部に新しい三角形を作ってはいない」という例も、これまた簡単に構成できる。(例えば☆型を2つ重ねておいて、一方を、図形の中心を動かさずに少し回転させたもの。)ですから(ハ)の場合も真面目に取り扱わなくてはならない。
 なるほど、この問題の厄介さがだんだん分かってきました。

 全然別のアプローチとして、「どの直線も「無限遠点」で交わっている」と解釈しますと、直線の配置によらず、平面は一定の個数の領域に分割されます。n=3なら7つ、n=4なら11、n=5なら16に分割される。その各領域を構成する辺の数の合計と無限遠点を含む頂点の数の合計の関係から、三角形の個数が出ないものかと思案中です。これだと無限遠点を含む「二角形」という厄介者が出来てしまうんですが、なんとかならんかな…
補足コメント
sokamone

お礼率 76% (38/50)

no.5とno.6を読みました。
no.6の内容はまだちゃんと追えていませんので、もう少し待ってください。
「直線群に新たに直線cを付け加えたとき、直線cはすでにあった多角形部分のみ
を通り、半直線部分とは交わらないと仮定する。そのとき、直線cは少なくとも
一つの(4角以上の)多角形を三角形とその他の部分に分ける。」
を示せば良いということですね。問題がすこし絞り込めたと思います。
no.6を参考にして、これから、がんばって考えたいと思います。

no.6の内容について、ちょっとだけ…。
直線cが連続して2つの三角形を通ることがないということは、すぐに言えます
よ。だって、そうだとすると、その二つの三角形は一つの辺で接していることに
なって、その辺の少なくとも一方の端点はすでに3本の直線の交点ということに
なるから(3角形の内角の和は180度)。とくに、直線cは3角形のみを2つ以上に
わたって通ることはない。
あと、no.6で用いている直線a,bの説明が書いてないと思うんですが、直線cが
通っていない辺を与えている2つの直線のこととしていいんでしょうか?
この返事を書いていていまふと思ったんですが、直線cが通ってゆく辺の端点での
その辺に接する2つの多角形の内角について議論すれば、なにか得られるんじゃ
ないかと。
まあ、とりあえず、no.6の内容をちゃんと理解するのが先ですね。
投稿日時 - 2002-01-12 01:12:48
  • 回答No.4
レベル14

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

この問題って、三角形の最大個数に関してはどこかで見た憶えがあります。 どうもsokamoneさんはほぼ証明を完成していらっしゃるようですね。 「最後に引く直線cに最も近い、既存の交点(a,b)を選ぶと(a,b)(a,c)(b,c)の三角形の中を通る直線はない。」 なるほど、この補題は簡単明解、秀逸ですね。直線を追加するごとに三角形が少なくとも1個増えることが保証されました。従って、「外側」云々は必要 ...続きを読む
この問題って、三角形の最大個数に関してはどこかで見た憶えがあります。
どうもsokamoneさんはほぼ証明を完成していらっしゃるようですね。
「最後に引く直線cに最も近い、既存の交点(a,b)を選ぶと(a,b)(a,c)(b,c)の三角形の中を通る直線はない。」
なるほど、この補題は簡単明解、秀逸ですね。直線を追加するごとに三角形が少なくとも1個増えることが保証されました。従って、「外側」云々は必要ない。脱帽です。

さて、だったら、[B]の議論は不要でしょう。
(1)直線が3本のとき、三角形は1個である。
(2) n≧4について、直線が(n-1)本あって、三角形がm個できているとき、もう一本直線を加えると三角形の個数はm+1以上である。
が証明できたわけですから、数学的帰納法によって
下限の定理:「n本の直線をひくと、三角形はn-2個以上できる」
が証明できています。

あとは、具体的にn-2個の三角形しか作らないようにn本の直線をひくアルゴリズムを構成してみせれば完成ですね。
補足コメント
sokamone

お礼率 76% (38/50)

直線を一本付け加えるごとに三角形の個数が少なくとも、一つ増えるという
ことは、まだ証明できていないのではないでしょうか。
先に証明した事柄は、「(n-1)本の直線が引かれているところに、新たにn番目の
直線を"どの多角形とも交わらないように"付け加えると、少なくとも三角形が一つ
増える。」ということです。n番目の直線のこのほかの付け加え方については、
三角形の個数が増えるかどうかはまだ言えていません。No.4の(2)はまだ言えて
ないと思うのですが。僕がわからないのは、まさにこの部分なのです。以前に考
えたときもここで詰まったと思います。でも、ここまで、すぐに回答してくれる
人がいるなんて、正直言ってびっくりしました。前のノートを探す必要がなくな
っちゃいました。

n本の直線を三角形がちょうど(n-2)個できるように配置するには、例えば、次の
ようにすればいいと思います。半円周をちょうどn等分する分点をとります。そし
て、隣り合う分点を通るように直線を引くと、n本の直線の配置ができて、三角形
はちょうど(n-2)個できます。

関係ありませんが、「教えて!goo」を利用し始めたのは昨日からで、とても
いいサイトだなあと感激してます。
投稿日時 - 2002-01-10 23:32:05
  • 回答No.1
レベル14

ベストアンサー率 50% (1122/2211)

限られた大きさの平面を問題にしているのではなく、無限に大きい平面を想定して いるのですよね。線も直線であって、線分ではない、と。 で、平行なものはなく、一点で三本が交わらないのであれば、できる三角形の数は 直線の配置によって変わることはなく nC3 になるんじゃないでしょうか?
限られた大きさの平面を問題にしているのではなく、無限に大きい平面を想定して
いるのですよね。線も直線であって、線分ではない、と。

で、平行なものはなく、一点で三本が交わらないのであれば、できる三角形の数は
直線の配置によって変わることはなく nC3 になるんじゃないでしょうか?
  • 回答No.2
レベル14

ベストアンサー率 37% (1123/2963)

回答ではないんですが。 例えば△ABCがあって辺AB、AC上に点P,QをPQとBCが平行にならないようにとります。直線PQとBCの交点をDとします。便宜的にDはBからみてCと反対側にあるとします。(どっちでも同じことです。) このとき、直線AB,AC,BC,PQは条件を満たしますよね。(n=4です) で、「分割された部分のうち、3角形になっている部分の個数」ですから、この場合△APQ,△PBDの ...続きを読む
回答ではないんですが。

例えば△ABCがあって辺AB、AC上に点P,QをPQとBCが平行にならないようにとります。直線PQとBCの交点をDとします。便宜的にDはBからみてCと反対側にあるとします。(どっちでも同じことです。)
このとき、直線AB,AC,BC,PQは条件を満たしますよね。(n=4です)
で、「分割された部分のうち、3角形になっている部分の個数」ですから、この場合△APQ,△PBDの2つということになると思うのですが。

△ABC・△QDCもOKとするなら、a-kumaさんの言う通り 4C3=4 ですが。
私の考え間違ってますでしょうか?
  • 回答No.3
レベル14

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

ご質問の意味は、直線で切り分けた最小の断片が三角形である、そういう三角形の個数のことを仰っているんだとおもいます。そうするとNo.1の回答とは話が違ってきます。 証明できないけど、  n<3のとき0  n≧3のときn-2 ではないかな? 三角形の個数がn-2となる作図法(システマティックに、どんなnについてもn-2個になるような作図法)を構成的に示すのは容易だと思います。さればn-2未満 ...続きを読む
ご質問の意味は、直線で切り分けた最小の断片が三角形である、そういう三角形の個数のことを仰っているんだとおもいます。そうするとNo.1の回答とは話が違ってきます。

証明できないけど、
 n<3のとき0
 n≧3のときn-2
ではないかな?

三角形の個数がn-2となる作図法(システマティックに、どんなnについてもn-2個になるような作図法)を構成的に示すのは容易だと思います。さればn-2未満にできないことを示すのがポイント。

[A](n-1)本の直線が描いてあるところに、n本目の直線を加える。ただし、既に存在している多角形の領域を通過しないようにn本目を加える場合を考えます。
(n-1)本の直線それぞれの上に、(n-2)個の交点が存在しています。そのうち、最も「外側」にある交点2個に注目します。直線aに関して最も「外側」にある交点のひとつ(a,b)は、別の直線bとの交点です。そして、(a,b)が直線bに関しても最も「外側」にある交点であるとする。
そうすると、n本目の直線cを、直線aと、(a,b)が直線aに関して最も「外側」にある交点でなくなるようにひいたときにできる交点(a,c)と、直線bとの交点(b,c)との間に、他の直線との交点はない。(もしあれば、(a,b)は直線a,直線bに関する最も「外側」にある交点ではない。)従ってここに1つ三角形(a,b)(a,c)(b,c)が出来ます。
言い換えれば、(n-1)本のどの直線についても「最も「外側」にある交点が、他の直線の最も「外側」にある交点ではない」、という配置が存在しない(これが示せたらいいんですが…)限り、n本目の直線を描くと新しく三角形ができる。

[B] さてn≧3について、n本の直線が描いてある場合、その中の1本cを選んで、他の(n-1)本の直線が構成するどの多角形をもcが通過しない、そういうふうにcを選ぶことが常に可能である(と言えそうな気がします…。)
すると、[A]の議論によって、cを取り除くことで三角形の個数が少なくとも1個減ります。
この手順を繰り返すと、残りの直線が2本になったとき、三角形は必ず丁度0個でなくてはならない。従って、元の、n本の直線が描いてある状態では三角形が少なくとも(n-2)個あった、ということが分かります。

[A][B]に残っている「…」の部分は、「(n-1)本のどの直線についても、最も「外側」にある交点が、他の直線の最も「外側」にある交点ではない、という配置が存在しない」という補助定理が証明できたら仕上がるように思うんですが、如何でしょう?
補足コメント
sokamone

お礼率 76% (38/50)

みなさん早々の回答ありがとうございます。
質問の意味は、n本の直線で区切られた部分の三角形の個数ということですから、
つまり、分割されていない三角形の個数を数えるということです。
高校の組合わせの標準問題でよくお目にかけるような問題ではありません。

stomachmanさんのいうように、僕も予想は(n-2)個だと思うんですが、
細かい点で完全に証明できないのがこの問題の難しいところだと思います。
この問題を考えたのは、かなり以前になる為、そのときのノートをいま
探しているところです。ぼくもstomachmanさんのような方法で考えた記憶が
あります。詳しいことはノートが見つかってから、書く予定ですが、
とりあえず、ここでは、stomachmanさんの論理に対する自分の理解を確認させて
頂くことにします。

まず、どのようなn≧3に対しても、三角形の個数がn-2個になる直線の配置が
作れる。問題は、それより三角形の個数を少なくするような配置がないことを
証明することである。

[A] (n-1)本直線が引いてあるところに、n本目の直線をどの多角形も通らない
ように引くと、三角形が少なくとも1個増える。

これに関しては簡単な証明があります。n本目の直線にもっとも近い交点がひとつ
とれるので、とります。その点を通る二本の直線は、そのn本目の直線と三角形を
作っている(簡単に証明できる)。stomachmanさんの議論ででてきた「外側」云々
という議論は必要なくなる。

[B] 「n本の直線が描いてある場合、その中の1本cを選んで、他の(n-1)本の直線
が構成するどの多角形をもcが通過しない、そういうふうにcを選ぶことが常に可能
である(と言えそうな気がします…。)」についてですが、これには反例があります。
5本の直線を星型に配置した時、どの直線をとってもそれは、他の4本の直線の
つくるある多角形を通ります。しかも、どの直線も[A]で追加した直線のようには
なっていません。
しかし、その後の文章の内容は、結果的に正しいのではないかと考えています。
つまり、適当に一本直線を抜いた時には、三角形の個数が減るということは十分
考えられます。この適当に一本選ばなくてはいけない直線の存在を保証したいが
ために最後の段落で述べている補助定理を考えたのだと思うのですが、そこの所が
いまいちはっきりわかりません。

以上。また書きます。
投稿日時 - 2002-01-10 16:06:50
  • 回答No.9
レベル14

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

No.8の反例に関する補足です。 直線eは本質的役割を果たしていません。UPした直後に、こいつは除いても構わないことに気が付きました。するってえと、何のことはない、a,b,d,f,gは☆型をちと歪めて描いたものに過ぎないのです。 ☆のトゲに順番に1,2,3,4,5と番号を振ります。直線cは1のトゲの2に近い側の辺を横切って、トゲ内部の五角形に突入し、トゲ3の三角形へ入り込み、トゲ4に近い側の辺を横切っ ...続きを読む
No.8の反例に関する補足です。
直線eは本質的役割を果たしていません。UPした直後に、こいつは除いても構わないことに気が付きました。するってえと、何のことはない、a,b,d,f,gは☆型をちと歪めて描いたものに過ぎないのです。
☆のトゲに順番に1,2,3,4,5と番号を振ります。直線cは1のトゲの2に近い側の辺を横切って、トゲ内部の五角形に突入し、トゲ3の三角形へ入り込み、トゲ4に近い側の辺を横切って外部に脱出後、トゲ1の頂点とトゲ4の頂点を結ぶ直線と交差するのです。(トゲ1を大きくして、しかもトゲ5の側に寄せて描き、トゲ4は小さくすると簡単に作図できます。)

交点のリストを行列の形に書いたり☆のトゲの変形を見ていて思うのですが、どうやら「直線」に拘らないで、交点の存在と順番を保存するような空間の位相だけ明確にしておけば宜しいようで、そうなるとグラフ理論か代数か、何かそのへんに帰着されそうな気がしてきましたぞ。
補足コメント
sokamone

お礼率 76% (38/50)

実は、以前にやったときも最終的に、直線を少しずらして配置を変えて
いくということを対応するグラフをつくってやってたんです。
対応するグラフというのは、区切られた領域ひとつに頂点をひとつ対応させて、
線分あるいは半直線で接しているふたつの領域に対応するふたつの頂点を辺で
結ぶというものです。
これまで、この方法を言わなかったのは、自分がこれで考えてみて精魂尽きた
というのと、余計なことを言わない方が新しい発想で考えてくれるのではと
思っていたからです。でも、やってみる価値は十分あると思います。
投稿日時 - 2002-01-13 01:35:56
  • 回答No.10
レベル14

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

 stomachmanも実は最初っから、平面分割の双対グラフを睨んでウンウンうなっていたんですよ。直線を組み合わせることで作られるこういう双対グラフを特徴付ける性質はなんかないのかな。四角形がくっついて出来てる平面グラフだ。ノードの数は直線の数で自動的に決まる。一番外側のノードは無限遠に開いている部分だから、これを無視して、edgeを3つ持つノードが三角形だ。直線を追加するってのは、グラフをどう変形させる ...続きを読む
 stomachmanも実は最初っから、平面分割の双対グラフを睨んでウンウンうなっていたんですよ。直線を組み合わせることで作られるこういう双対グラフを特徴付ける性質はなんかないのかな。四角形がくっついて出来てる平面グラフだ。ノードの数は直線の数で自動的に決まる。一番外側のノードは無限遠に開いている部分だから、これを無視して、edgeを3つ持つノードが三角形だ。直線を追加するってのは、グラフをどう変形させる演算なんだろうか。何か旨い保存則を見つけたらいとも簡単に解ける、ってな訳にはいかんのかな。なんてね。(だから「無限遠点追加して」なんて口走ったりしてます。)
 また、直線ごとに交点の順序を並べた行列、こいつも何か特徴のある空間を作りそうな気配がしてまして、どういう空間なんだろ。その空間上で代数を考えたらなんか出て来んのかな。三角形の個数や、直線を追加するということをぴったり表現する演算って何だろう。とにかく図面をいっぱい描かなくても済むやり方はないのだろうか。
 いや、直線追加方式も駄目と決まった訳じゃない。「(n-1)本の直線が(n-3)個の三角形を作っている場合に限るなら、直線を一本追加すると必ず三角形が増える」ことは証明できるんじゃないだろうか。そうすると(n-m)本がk個((n-1)≧k>(n-m-2))の三角形を作っている場合にだって、m本追加すると必ず(n-2)個以上になるはず。
 って、いろんな締切いっぱい抱えた状態で嵌ってしまってます。危ないですから長い目でみてやって下さい。(何のこっちゃ??)
18件中 1~10件目を表示
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ