三角形の最大数                          戻る

 平成17年9月6日付けで当HP掲示板「出会いの泉」に、HN「two−well」さんという方の
書き込みがあった。

 直線を n 本使ってできる最大の三角形の数を知りたいのだが...?
3本だと三角形は1個、4本だと2個、5本だと5個あることは分かったが、6本では何
個あるのか是非知りたい。また、個数を求める数式はあるのだろうか?


 当初、私自身この問題の難しさをあまり理解していなかった。

 高校の「数学A」における順列組合せの有名問題:

 「平面上において異なる n 本の直線が一般の位置にあるものとする。これらの直
 線で三角形は何個できるか?


と同じように考えていた。

    左図において、5本の直線から3本の直線を選ぶ
   と、その選び方1通りに対して三角形が1個対応す
   るので、求める三角形の個数は、

         53 = 10 (個)

   となる。

    上記で求めた10個の三角形の中には、互いに交
   わるものも数えられている。

    two−well さんの問題文中の「三角形の数」とは、
   互いに交わらないものを数えるらしい。

 上記の直線の配置の場合、右図のように互いに
交わらない三角形の個数は、3 となる。

 ところが、two−well さんが指摘しているように
直線の本数が5本の場合、三角形は最大で 5個
できるらしい。

 すなわち、三角形が5個存在するような直線の
上手い配置があるというのだ。

 右図は三角形の最大個数を与えないので、あ
る意味で「拙い」配置ということになる。

 果たして三角形の最大個数を与える直線の配
置をどうやってみつけるのだろうか?
   

 この問題は、実はとてつもなく難しいものらしいことが段々と分かってきた。この問題に対
して、当HPがいつもお世話になっているHN「らすかる」さんやHN「未菜実」さんたちがいろ
いろ考えてくれている。(← 現在進行形!)

 掲示板は時間の経過とともに消え去る運命なので、らすかるさんや未菜実さんの取り組
みを当HP上に記録として残すことにした。もちろん、私自身の理解を深めるという目的も
あるのだが...。

 三角形の個数に着目して数列 1、2、5、・・・ を構成すると、上記問題は、この数列の一
般項ないしは漸化式を求める問題に帰着される。

 数列と言えば、いつもお世話になるHPサイト:オンライン整数列大辞典 がある。

 らすかるさんからの報告によると、上記問題のことが、

      「Maximum triangles formed from n lines

という名前で、整数列番号 A006066 にまとめられているそうだ。

 それによると、

直線の本数
三角形の最大個数 11 15 21

となるが、この数列の一般項ないしは漸化式についての情報は残念ながら得られない。
多分、このことはまだ未解決の問題なのだろう。

 オンライン整数列大辞典 の整数列番号 A006066 に紹介されているHP

                   Kobon Triangle

には、直線の本数 n = 3 〜 9 の場合について、三角形の最大個数を与える直線の配置
図が掲載されている。

 さらにそこでは、この問題が、「Kobon Fujimura」(多分、藤村幸三郎氏)により提唱さ
れ、「Saburo Tamura」(多分、田村三郎氏)が、三角形の最大個数の上限は、

          n(n−2)/3

であることを示したことなどが述べられている。

 未菜実さんからの情報によると、藤村幸三郎氏は日本のパズルの草分け的存在という。
ブルーバックス「パズル入門」(173〜174頁)に、この問題のことが述べられているそうだ。

 たまたま私の手もとに、藤村幸三郎 著(小林茂太郎との共著)の「数学パズルの世界」
(講談社ブルーバックス)があったが、残念ながら、この問題に対する記述はなかった。

 Kobon Triangle に掲載されている直線の配置図を注意深く眺めると、前の図に直線
を1本追加して次の図を構成していることが分かる。ただ、配置図を見る限りにおいて、こ
の点に注意して配置図を書いているようには思われない。

 この点に最初に気づかれたのは、らすかるさんである。らすかるさんによれば、次のよう
に直線を順次追加していくことによって、次の「上手い」直線の配置図が得られるのだとい
う。

  
   (上記ボタンをクリックすると、このページのトップに行ってしまうので、クリックはなしネ!)

     (平成18年8月16日付け追記) 上図を、Flash で作ってみた。楽しめるかな?

        Flash版「三角形の最大個数」   HTML版「三角形の最大個数

       ※いま、Flashを集中的に学んでいるので、その作品公開です...(^^;)

 セキュリティ保護のため、コンピュータにアクセスできるアクティブ コンテンツが表示されないように、
Internet Explorer で制限していると、HTML版、Flash版ともに見られません。ブロックされている
コンテンツを許可してください。(すみません、自己の責任でお願いします。)


 しかしながら、前の図に直線を1本上手く配置して次の図が得られるのは、n=8 までで
ある。 n=9 の場合は、n=8 の図から得ることはできないようだ。

 その原因は、らすかるさんによれば、 n=8 の場合の特異性にあるという。三角形の最
大個数を与える配置を考えた場合、どうも、n=8 の場合は3直線が1点で交わらないよう
な配置図は存在しないようなのだ。

 したがって、n=9 の場合の配置図を考える場合、一度、8本目に描いた直線の配置を
変更し、9本目を描かなければならない。

 n=9 の場合についていろいろ直線の配置を工夫してみたが、あちらを立てればこちら
が立たずで結構難しかった。

 大いに拙いのですが、n=9 の場合の配置図は下記の通りである。
(これを作るにあたり、らすかるさんの http://www10.plala.or.jp/rascalhp/image/7-11.gif
を参考にさせていただいた。)

    

    上図では、青が8本目で、赤が9本目である。青の配置を若干修正している。

   (平成17年9月28日付けで、らすかるさんは上図が、120°回転対称形であること
    に着目され、下記のような数式を用いて描いてみたと報告された。

    9本の直線の方程式は、次で与えられる。(ただし、t≒82.8068)

     (y−3)((y+6)2−3x2)=0   、  tx2=(y−10)2
     t(x−y)2=(y+x+20)2   、  t(x+y)2=(y−x+20)2

    このとき、直線の交点は全て、原点中心で半径10の円 x2+y2=102 の内部に
    おさまり、次のような、きれいな図を得ることができる。

        http://www10.plala.or.jp/rascalhp/image/9-21-2.gif

   (コメント: 図が美しすぎます...! 感動的です。) )


 n=10 の場合の配置図として、次のものが候補としてあがっている。

         http://www10.plala.or.jp/rascalhp/image/10-25.gif (らすかるさん作)

 また、らすかるさんは、配置を工夫されて

         http://www10.plala.or.jp/rascalhp/image/10-25-2.gif

と見やすく改良された。

 三角形の数を数えるとちょうど25個ある。この数が本当に最大なのか、まだ確定してい
ないとのことである。

 n=11 の場合の配置図として、次のものが候補としてあがっている。

         http://www10.plala.or.jp/rascalhp/image/11-32.gif (らすかるさん作)

 三角形の数を数えるとちょうど32個ある。上限は33個であるが、この数が本当に最大
なのか、まだ確定していないとのことである。(→新情報

 n=10 までのらすかるさんの調査結果をまとめると

直線の本数 10
三角形の最大個数 11 15 21 25?
最大個数の上限 11 16 21 26

となっている。この表では、直線の本数が4以外の偶数の場合に『1減』になりそうな雰囲
気である。

 このことから、直線の本数が4本のとき以外は、求める三角形の最大個数は、

          
                             (注: [ ] は、ガウスの記号

かな??と、らすかるさんは予想されている。

(コメント) もし、これが正しい公式だったら、すごいことになりそうですね!

 ここで、田村三郎さんが示されたという三角形の最大個数の上限

          n(n−2)/3

がどのように算出されるのか、大いに興味・関心があるところである。

 これに対して、らすかるさんが明解に説明してくれた。(平成17年9月22日付け)

○ 3直線以上が1点で交わることがない場合

   直線の本数を、n とする。(左図は、n=4 の場合)

   左図のように、2つの三角形が辺を共有することがない
  ので、原則として、3つの線分で三角形1個が定まる。

   1本の直線上に他の直線との交点は最大で n−1 個
  あるので、両端を除いて最大 n−2 個の線分がある。
   よって、交点間の線分の総数は最大で、n(n−2) 個
  ある。(左図では、8個)

   したがって、三角形の最大個数は、 n(n−2)/3 が上
  限となる。( n=4 の場合は、上限は 2 )

(コメント) 上図からも分かるように、交点間の線分がすべて三角形の辺になるとは限ら
      ないので、出来る三角形の個数も n(n−2)/3 以下の整数になるわけである。

       らすかるさんは、三角形の辺にならない線分のことを、「無駄な線分」と命名さ
      れている。

       一般には、このような無駄な線分が発生するが、n = 3、5、9 のように無駄
      な線分がない場合もある。

○ 3直線以上が1点で交わることがある場合

   直線の本数を、n とする。(左図は、n=5 の場合)

   上図に n 本目の直線を追加するとき、赤点線のよう
  な場合は、上記で調べた通りである。ここでは、n 本目
  の直線が既存の交点を通る場合(赤実線)を考える。
  
   このとき、少なくとも3個の線分(左図では例えば@A
  B)が消失し、多くとも2個の線分(左図で例えばFGが
  平行な場合のCD)が増加する。
   よって、交点間の線分の総数は、n(n−2) 個より減る
  ことはあっても増えることはない。
   したがって、三角形の最大個数は、 n(n−2)/3 が上
  限となる。

(コメント) two-well さん同様、私も上記の説明に大いに納得し感動しました...。


 さて、らすかるさんは、三角形の個数がきっちり n(n−2)/3 となる場合について考察さ
れた。(平成17年9月28日付け)

 n=3、5、9 のとき、三角形の辺とならない「無駄な線分」は1本もなく、n(n−2)/3 個の
三角形が出来るが、いろいろパターンを見ていると、

  ・ 全体が五芒星と六芒星の絡み合った形で構成(n=3 のときを除く。)
  ・ 回転対称形
  ・ n が奇数

の場合に、n(n−2)/3 個の三角形が出来るように思われる。

 用語があるのかどうかわからないが、基本的に星型の延長のような形(無駄がなければ、
ある直線の両端の交点は三角形の1頂点でなければならず、またその交点は、交わる相手の直線に
とっても端の交点でなければならない。全ての直線は“端の頂点”より先に交点はないので、「正n角
形の頂点を (n−1)/2個ごとに取って出来る形」しかあり得ないと思う。)
を、頂点の順番を変えな
いように変形して作った形でないと、必ず無駄が出来ると思うので、nが偶数の場合は、
n(n−2)/3 にはなり得ないと思う。

  # 実際にやってみたところ、「正n角形の頂点を (n−1)/2個より小さい値ごとに取って
   出来る形」では、線分が少なくなってダメであった。

 また、五芒星と六芒星のみで構成されると仮定すると、回転対称形の中心は「五芒星」
「六芒星」「三角形」のいずれかになるはずだから、n(n−2) が 3 で割り切れる場合、

  ・ n の素因数が3と5だけの場合は、n(n−2)/3 個の三角形が作れる
    (素因数に3または5がある奇数なら作れるかもしれない?)
  ・ それ以外の場合は、n(n−2)/3 個にはならない

という予想が立てられる。

 すると、「n=15なら最大になるのでは?」と思われるが、実際に手作業でこれを作って
みたところ、成功することができた!(Word のオートシェイプを使用)

         http://www10.plala.or.jp/rascalhp/image/15-65.gif

         http://www10.plala.or.jp/rascalhp/image/15-65-2.gif(改良版)


 上図では、15本の直線で、15×13÷3=65個の三角形が出来ている。(多分合って
いると思うが、ご確認下さい!)。数えやすいように、回転対称を基準に色分けをした。
赤、紫、ピンク、橙、水色、黄色が各10個、緑が5個である。

  # 予想が当たっていれば、次に出来るのはn=27である。誰か作ってみませんか?


 らすかるさんは、『三角形が n(n−2)/3個になる条件』(平成17年9月30日付け)に関
して、わかっていることをまとめられた。

          http://www10.plala.or.jp/rascalhp/nlines.htm

 n=6、8 のときに、 最大個数が n(n−2)/3個にならない理由もこれで分かると思う。

(コメント) とても分かりやすいです。

 らすかるさんのその後の調査で、n=11 の場合は、三角形の最大個数は32個に確定
したとのことである。(平成17年10月5日付け)

 n(n−2)/3個の三角形が作れるのは、nが5または3の奇倍数に限られることが分かっ
たからだという。

 図がないと説明が大変なので、こちら(↓)を参照。

          http://www10.plala.or.jp/rascalhp/nlines2.htm

 これにより、n=11の場合は最大32個と確定した。


 らすかるさんのその後の調査(平成17年10月8日付け)で、次のことも判明したそうで
ある。

  ・ n=10 の場合、三角形の個数は最大25個で、26個は出来ない
  ・ n=8 の場合、3直線の交点がないと最大数にならない
  ・ 3直線の交点は、nが偶数の時有利に働き、奇数の時不利に働く

 これらについては、こちら(↓)を参照。

          http://www10.plala.or.jp/rascalhp/nlines3.htm

 これで最大値がわかっているものと確率的試行で予想されていたものは、全て解決した
そうである。

 これまでのらすかるさんの調査結果をまとめると、次の表になる。

直線の本数 10 11 12 13 14 15
三角形の最大個数 11 15 21 25 32 65
最大個数の上限 11 16 21 26 32 39 47 54 65

  (注) 田村三郎氏の公式によれば、n=11のときの三角形の最大個数の上限は、
     11×9÷3=33個のはずであるが、11が3の倍数でないので、33個の三角
     形は出来ないということが、らすかるさんの研究により示されている。他も同様。


 さて、らすかるさんは、この問題に対してプログラムを組み解の探究に邁進されている。
プログラムに対して浅学の身で、その探究方法を詳細に述べることは困難だが、次のよ
うな手順で、直線の最適な配置図を探されているらしい。

 あり得る全てのパターンを調べることは困難なので、乱数で発生させた直線の配置図
について、三角形の個数を調べるという方法をとることにする。

三角形の発生方法

 (1) 整数 N を適宜定める。
 (2) 乱数により、整数 y1、y2 ( 0 ≦ y1、y2 ≦ N−1)を定める。
 (3) 2点( 0 , y1 )、( 1 , y2 )を結ぶ直線を考える。

 この操作により次々と直線を生み出し三角形を発生させるわけだが、Nの値を適切な
値にする(ここらへんが難しいらしい!)と一定の確率で最大解が出現するようになるそ
うだ。

 次は、このプログラムにより得られた解である。

直線の本数(3)のとき、 N=2 としてよい。
                       
直線の本数(4)のとき、 N=2 としてよい。
                       
直線の本数(5)のとき、 N=4 としてよい。
                       
直線の本数(6)のとき、 N=4 としてよい。
                   
直線の本数(7)のとき、 N=6 としてよい。
                   

直線の本数(8)のとき、 N=7 としてよい。
           


直線の本数(9)のとき、 N=15 としてよい。

 (らすかるさんのその後の調査で、N=8 としても最大解が見つかったそうです。ただし、
 1997677867番目(だいたい20億くらい!)という気が遠くなるような数字です。らす
 かるさんによれば、何と45時間かかったそうです。本当にらすかるさんには頭が下がり
 ます。計算には乱数を用いているので、プログラムを改良すると、もしかしたらもっと早く
 出現する可能性もあるそうです。)
      

 図が少し込み入っているが、次の直線

   (0,7)−(1,0)、(0,9)−(1,6)、(0,8)−(1,8)、(0,0)−(1,)、
   (0,9)−(1,10)、(0,3)−(1,6)、(0,7)−(1,13)、(0,13)−(1,9)、
   (0,13)−(1,12)  (赤字の部分、当初は7でしたが、図の関係で変更)

から、21個の三角形が得られている。

 三角形の個数を数えることは、直線の本数が少ないときは全然苦にならなかったが、段
々本数が増えるに従って、大変になってきた。コンピュータに描かせているとはいえ、厳し
いところに三角形が出来たりで目視でカウントするのは辛いものがある。

 これに対して、らすかるさんは「三角形の判定」をコンピュータにやらせ、三角形の個数を
数えるという手法をとられたようだ。

三角形の計数方法  同一直線がないことを確認して、下記により計数を行う。

 (1) 全直線の交点の x 座標を求める。ただし、誤差が出ないように分数で計算する。
 (2) 各直線毎に交点の x 座標を小さい順にソートする。これにより、ある直線に対して
    交わる直線の順番が分かる。
 (3) 3直線のうちどの2直線の交点も互いに隣り合っているとき、この3直線により1つ
    の三角形が定まる。
 (4) 3直線以上が1点で交わる場合や直線同士が平行な場合に注意して、上記(1)〜
    (3)により三角形の個数を調べることができる。

例  直線の本数(5)のときの計数方法を確認してみよう。コンピュータ出力の結果を視覚
  的にまとめた図が左図であるが、出力の都度、図を描いていては時間がかかるので、
  出力パターンから三角形の個数を数えようと思う。

  平面上のペアとなる2点( 0 ,y1 )、( 1 ,y2
 について、出力パターンが、例えば、

 (y1,y2)=(3,2)、(3,0)、(2,3)、(2,2)、(0,3)

 になったとする。5本の直線を、a、b、c、d、e とし、

  a=(3,2)、b=(3,0)、c=(2,3)、d=(2,2)、
  e=(0,3) と略記することにする。

  実際的には、 a : y=−x+3 、b : y=−3x+3、

  c : y=x+2 、d : y=2 、e : y=3x である。


 2直線 L、M の交点の x 座標を、(L,M)と表すことにする。(コンピュータに(L,M)の計
算をさせることは、それほど難しくはないだろう。)

   (a,b)=0、(a,c)=1/2、(a,d)=1、(a,e)=3/4

   (b,a)=0、(b,c)=1/4、(b,d)=1/3、(b,e)=1/2

   (c,a)=1/2、(c,b)=1/4、(c,d)=0、(c,e)=1

   (d,a)=1、(d,b)=1/3、(d,c)=0、(d,e)=2/3

   (e,a)=3/4、(e,b)=1/2、(e,c)=1、(e,d)=2/3

 このとき、各直線毎に交点の x 座標を小さい順にソートすると、次のようになる。(ソートさ
せることもコンピュータにおいては難しくない作業だろう。)

   (a,b)=0、(a,c)=1/2、(a,e)=3/4、(a,d)=1

   (b,a)=0、(b,c)=1/4、(b,d)=1/3、(b,e)=1/2

   (c,d)=0、(c,b)=1/4、(c,a)=1/2、(c,e)=1

   (d,c)=0、(d,b)=1/3、(d,e)=2/3、(d,a)=1

   (e,b)=1/2、(e,d)=2/3、(e,a)=3/4、(e,c)=1

 このことから、各直線同士は次の順番で交わっていることが分かる。

       直線 a → b 、c 、e 、d

       直線 b → a 、c 、d 、e

       直線 c → d 、b 、a 、e

       直線 d → c 、b 、e 、a

       直線 e → b 、d 、a 、c

 隣り合う交点同士に着目して、3直線のうちどの2直線の交点も互いに隣り合っているか
どうかを調べる。

 例えば、 直線 a →  、 、e 、d   直線 b →  、 、d 、e
       直線 c → d 、 、 、e   直線 d → c 、b 、e 、a
       直線 e → b 、d 、a 、c

より、3直線 a、b、c で三角形が1個定まることが分かる。

 コンピュータを用いた実際の詳しい計数方法は、らすかるさんに聞くしかないが、このよう
な手順で求めると複雑な図から解放されて、単に交点同士が隣り合っているかどうかの判
断に帰着されるわけで、もっといろいろな場合を求めてみようという気になるから不思議だ。

 らすかるさんは、特定のNに対する全数調査も試みられた。

 それによると、

   (n,N)=(3,2)、(4,2)、(5,4)、(6,4)、(7,6)、(8,7)、(9,8)

が三角形の最大個数を与える最小のパターンとのことである。

 因みに、

全パターン数 1134 2074 2089380 112767879 6885330452
最大解パターン数 16 19 14
三角形の最大個数 11 15 21

となるそうである。


 当HPがいつもお世話になっているHN「FN」さんから、「Saburo Tamura」(多分、田村
三郎氏)が示された三角形の最大個数の上限の個数

          n(n−2)/3

が、多少改良された旨のご教示をいただいた。(平成22年9月23日付け)

 n≡0、2 (mod 6) のときは、1だけ減じることができる

とのこと。(→ 参考論文

 上記の論文には、参考文献として、このページ「三角形の最大数」があげられているとの
ことです。(FNさん同様、私も驚きました!)

 Kobon Triangle について、次のページに簡単なまとめがあります。

    http://mathworld.wolfram.com/KobonTriangle.html

 ここに次のような記述があります。

   Honma illustrates an 11-line, 32-triangle configuration, where 33 triangles is the
  theoretical maximum possible.

また、次の記述もあります。

   T. Suzuki (pers. comm., Oct. 2, 2005) found the above configuration for n=15, which
  is maximal since it satisfies the upper bound of N(15)=65.

 2005年10月2日というのは、ちょうど「三角形の最大数」が書かれているころで、どちら
が早いか微妙ですが、9月中に書かれているようにも思います。オンライン整数列大辞典
では、n=15のときが、「T.Suzuki」になっています。いずれにしろ、Kobon Problem に関
して、2005年9、10月ごろは世界の最先端を走っていたかもしれません。

 上記のFNさんのコメントに対する、らすかるさんからの返信です。
                                     (平成22年9月23日付け)

 その「T.Suzuki」は、私です。N(15)=65を発見したので、ここのサイトで書いた後、
mathworldに投稿しました。確かに当時は世界最先端だったかも知れませんが、他に力を
入れて研究している人がたまたまいなかったのでしょう。その後何も増えてないですが、
次のような私のページも作られました。

    http://mathworld.wolfram.com/topics/Suzuki.html

 FNさんからのコメントです。(平成22年9月23日付け)

 前に引用した論文では、perfect configuration について調べているわけですが、n 本
の直線で、n(n−2)/3個の三角形ができる条件について調べているということで、らすか
るさんが次のページでされてることの部分集合という感じです。

    http://www10.plala.or.jp/rascalhp/nlines.htm
    http://www10.plala.or.jp/rascalhp/nlines2.htm

らすかるさんの考察の方が深いと思います。ただ、「n が3の倍数でない場合は、三角形が
n(n−2)/3個になるパターンは、作れないことになります。」との主張は、n=17のときに
85個が実現できていますから間違っていることになります。これについて、らすかるさんに
よれば、4-3

  すると、a の反対側は、(3)のパターンにはなることが出来ませんので、再び(2)の
 パターンとなります。


という部分に、考え落としがあって間違いだったとのこと。(平成22年9月23日付け)




      以下、工事中