◆広島県 清川 育男 さんからの解答。
以前出題された『６人の村人』という問題を連想しました。
現在、試行錯誤でさがしています。
八角形の頂点を反時計回りに、A,B,C,D,E,F,G,Hとする。
AB,BC,CD,DE,EF,FG,GH,BD,DF,FH,HBを青線とする。
このとき、
ACE,ACF,ACG,ADG,AEG,BEG,CEG,CEH,CFHの９個が三辺が赤線の三角形となる。
いまのところ最小値は９個です。
アイデアが浮かびません。
【出題者のコメント】
初めから最小値を設定して問題を出そうかどうか悩んだのですが、この手の問題は、あらかじめ最小値がわかってしまうと、その値を気にしながら証明になってしまうので、自分ではなかなか気づかない欠陥が生じることが良くあります。
(かくいう私もそう (^^))
そこで最小値はみなさんに考えてもらうことにしました。
実はこの問題はみかけによらず難しいことに気づかれるかと思います。
私も(自分自身で納得できるような)エレガントな解法は見つかっていないので、みなさんの発想力(アイディア)にゆだねようということで出題しました。
(あっ、これって前回と同じパターンだ！(笑))
ヒントですが最小値は９よりももっと小さいです。
◆三重県 久保田 尚 さんからの解答。
いい方法が思いつかないので、試行錯誤で考えました。
まず、正８角形の各頂点を８つの点と考えます
（各辺がすでに８本ある）
次に、適当な点から時計周りに点を２つとばすように順番に線を引いていきます。
すると８本引いて元の点に戻ってきます。
これで１６本の線が引けたことになり、まだ３角形は１つもありません。
（形としては長方形が縦横斜めに４つクロスする形になっているはずです）
最後の１７本目の線ですが、１６本まで引いた形が完全な対称形なので、どの点で考えてもいいことになります。
ある点から１７本目の線を引く形は、１つとばしか、３つとばし（ちょうど反対の点）のどちらかですが、どちらに引いたとしても３角形が４つできます。
ということで最小の数は、４つだと思います。
【コメント】
図を書いて考えてみたのですが、三角形がたくさんできてしまいました。
私の勘違いだと思うのですが、どこがおかしいのでしょう。
◆三重県 久保田 尚 さんからのコメント。
回答ではなく、確認の質問なんですが、この問題の三角形とは「８つの頂点のうち３つを結ぶ三角形」という意味ではないのでしょうか？
清川さんの答えを図に書いて確認してもそういう意味だったので、ボクもそう理解していましたが・・・
もし、３本の線に囲まれた三角形の事を意図しているとすると、根本から考え直さないといけなくなるので、出題者の方のコメントをお待ちしています。
【出題者のコメント】
一見たくさんありそうですが、よく見てみると………
８つの点のある点(どこでもいい)からはじまって１,２,３,……,８と番号を振っていきます。
今、それらの点を偶奇で分類したとき、偶奇が一致する２点間は決して赤線分が存在していないことに注意すると、任意に３点を選んだとき、どうしても偶奇が一致する２点を選ばざるを得ないので、久保田さんの16本の引き方では赤い三角形は現れてこないと思います。
(実際に上記の16本の引き方の傘下で17本の引き方を構成したことで最小値は４以下だとわかるのですが、でもここからが山場なんですよね。
下から値を押さえる作業(＝最小値が３以下にならないことの証明)がけっこう大変(^^;))
◆広島県 清川 育男 さんからの解答。
久保田さんの解答とAsamiさんのヒントをもとに考えました。
８点を１，２，３，４，５，６，７，８と番号を付ける。
奇数番と偶数を赤線で結ぶ。
この場合の数は、
4Ｃ1×4Ｃ1＝１６。
この時点でどの３点をとっても３辺が赤線で結ばれた三角形は存在しない。
（その理由）
３点を偶数、奇数で分類する。
１）偶数番、偶数番、偶数番 （偶数番３個）
２）偶数番、偶数番、奇数番 （偶数番２個、奇数番１個）
３）奇数番、奇数番、偶数番 （偶数番１個、奇数番２個）
４）奇数番、奇数番、奇数番 （奇数番３個）
１）、４）は存在しない。
２）、３）の場合
偶数番−偶数番、奇数番−奇数番は結ばれていないので、３点が赤線で結ばれた三角形は存在しない。
残り１本の赤線の取り方。
１−３ ２−４
１−５ ２−６
１−７ ２−８
３−５ ４−６
３−７ ４−８
５−７ ６−８
これらは２群に分類される。
１群（８角形の頂点に点を取った場合 頂点を１個とばした結び方）
１−３ ２−４
１−７ ２−８
３−５ ４−６
５−７ ６−８
２群（８角形の頂点に点を取った場合 頂点を３個とばした結び方）
１−５ ２−６
３−７ ４−８
１群の場合 ４個
２群の場合 ３個
この場合は最小値３個となる。
この場合以外での結び方では１６本で少なくとも２個できる。
残り１本を加えたとき少なくとも１個以上増えるので最小値は３個となる。
答え ３個。
偶然にも最初に漠然と考えた根拠のない数と一致しました。
◆広島県 清川 育男 さんからの解答。
また間違えました。
解答の２群も４個でした。
結局、久保田さんの解答を確認しただけでした。
◆東京都 合屋 さんからの解答。
三角形を作らずに２点間を結ぶことを考えると，８つの点は同じ条件下にあるため、８つの点に任意の順に１〜８の番号を割り振って、１の点と結ぶ線を決め、次に２の点と結ぶ線を決めるというように順次結んでいきます。
まず、１の点を基点として、２〜８の点に結びます。
以下では、これを
１＝＞２，３，４，５，６，７，８
と表します。
２の点から１の点へは既に結んであります。
以下では、これを
２＝＞（１）
と表します。
この状態では１から結ぶ点は無く、２〜８の点はすべて１と結ばれているため、２〜８のどの２点を結んでも１との間で三角形ができます。
このように結び方を考えていくと、線の結び方は以下の４つのケースになります。
●ケース１（１から７本）
１＝＞２，３，４，５，６，７，８
２＝＞（１）
３＝＞（１）
４＝＞（１）
５＝＞（１）
６＝＞（１）
７＝＞（１）
８＝＞（１）
線の数＝７
●ケース２（１から６本）
１＝＞２，３，４，５，６，７
２＝＞（１，）８
３＝＞（１，）８
４＝＞（１，）８
５＝＞（１，）８
６＝＞（１，）８
７＝＞（１，）８
８＝＞（１，７）
線の数＝１２
●ケース３（１から５本）
１＝＞２，３，４，５，６
２＝＞（１，）７，８
３＝＞（１，）７，８
４＝＞（１，）７，８
５＝＞（１，）７，８
６＝＞（１，）７，８
７＝＞（２，３，４，５，６）
８＝＞（２，３，４，５，６）
線の数＝１５
●ケース４（１から４本）
１＝＞２，３，４，５
２＝＞（１，）６，７，８
３＝＞（１，）６，７，８
４＝＞（１，）６，７，８
５＝＞（１，）６，７，８
６＝＞（２，３，４，５）
７＝＞（２，３，４，５）
８＝＞（２，３，４，５）
線の数＝１６
・注
１からの線が３，２，１本の場合はケース３〜１を番号の順序を変えたものであり、その他の結び方も同様に番号を並べ変えたものになる。
（久保田さんからの解答中の図はケース４）
そうで無ければ、三角形ができているか、三角形を作らずに結べる線がある。
以下の図はケース４の一例である。
（点の位置、番号の振り方は任意なのでこのような点の配置であっても三角形を作らずに１６本結べる）
本来の問題は１７本の線を結んだ場合であるから、ケース４に於いてはもう１本結ぶ必要がある。
ここで例えば２と３を結ぶと１と２および１と３は既に結んであるから１−２−３を頂点とする三角形ができる。
これは１を基点とする時の右辺に２も３もあることをチェックすることで確認できる。１＝＞２，３，４，５
〜 〜 〜
この確認方法で右辺に２と３の両方を含む基点を探すと１、６，７，８の４つがあるので２と３を結べば４つの三角形ができることが分かる。
ケース４ではどの２点を結んでも４つの三角形ができます。
ケース３の場合は既に１５本結んであるから、あと２本結ぶことになる。
いずれか２点を結び線を１本増やすと３つの三角形ができる。
もう１本結ぶとさらに３つでき、計６つの三角形ができる。
ケース１および２ではそれぞれ１０本と５本の線を増やすことになるが、１本結ぶと最低１つの三角形ができるので少なくとも５つ以上の三角形ができる。
よって、それぞれの点から４本の線が出るように結んだケース４に１本加えた線の結び方の時が最低で４つの三角形ができる。