◆東京都 かえる さんからの解答。
【問題１】
頂点Ａに集まる辺は５つ。
これを赤と青の２色で塗り分けるのだから、少なくとも３つの辺が同色になる。
ここで、ＡＢ、ＡＣ、ＡＤを赤としても、一般性は失われない。
ＣＤ、ＤＢ、ＢＣの少なくとも１つが赤の場合
→ 例えばＢＣが赤とすれば△ＡＢＣが３辺赤になるので、必ず３辺赤の三角形ができる。
ＣＤ、ＤＢ、ＢＣが全て青の場合
→ △ＢＣＤが３辺青の三角形になる。
以上より、必ず３辺同色の三角形ができることが示された。
【問題３】
平面座標上で考える。
円Ｏ1： ｘ2＋ｙ2＋a1ｘ＋a2ｙ＋a3＝０ ・・・(1)
円Ｏ2： ｘ2＋ｙ2＋b1ｘ＋b2ｙ＋b3＝０ ・・・(2)
円Ｏ3： ｘ2＋ｙ2＋c1ｘ＋c2ｙ＋c3＝０ ・・・(3)
とする。
円Ｏ2と円Ｏ3、円Ｏ3と円Ｏ1、円Ｏ1と円Ｏ2の交点を、
Ｐ1とＰ2、Ｑ1とＱ2、Ｒ1とＲ2とする。
直線Ｐ1Ｐ2： (2)−(3)：
（b1−c1）ｘ＋（b2−c2）ｙ＋b3−c3＝０ ・・・(4)
直線Ｑ1Ｑ2： (3)−(1)：
（c1−a1）ｘ＋（c2−a2）ｙ＋c3−a3＝０ ・・・(5)
直線Ｒ1Ｒ2： (1)−(2)：
（a1−b1）ｘ＋（a2−b2）ｙ＋a3−b3＝０ ・・・(6)
直線Ｑ1Ｑ2と直線Ｒ1Ｒ2の交点をＳ（Ｘ，Ｙ）とすると、(5)、(6)より、
（c1−a1）Ｘ＋（c2−a2）Ｙ＋c3−a3＝０ ・・・(7)
（a1−b1）Ｘ＋（a2−b2）Ｙ＋a3−b3＝０ ・・・(8)
が成立する。
−（(7)＋(8)）より、
（b1−c1）Ｘ＋（b2−c2）Ｙ＋b3−c3＝０ ・・・(9)
が成立。
(4)、(9)より、Ｓ（Ｘ，Ｙ）は、直線Ｐ1Ｐ2上の点であることがわかる。
また、図より、交点Ｓは、それぞれの線分上にあることが明らか。
以上より、３線分は１点で交わることが示された。
◆東京都 T.Kobayashi さんからの解答。
【問題１】
題意を満たす三角形が存在しないと仮定する。
このとき、一つの頂点(*)から同じ色の線分が三本出ていると、それらの線分の(*)ではない端点のうち二つを結ぶ線分はそれとは違う色でなければならず、結局それらの線分の(*)ではない端点を結んで出来る三角形は題意を満たす三角形になってしまうから、一つの頂点からは同じ色の線分が三本以上出ていてはならない。
従って、一つの頂点から出ている青の線分は二本以下、赤の線分も二本以下、結局一つの頂点から出ている線分の総数は四本以下でなければならない。
ところが、題意より一つの頂点からは五本の線分が出ているから、これは矛盾である。
従って、題意を満たす三角形は存在しなければならない。
【問題２】
任意の点から出発して、既に通った点に戻らないように通っていくと、各点からは四本以上出ているという
条件(以降、四本条件と呼ぶ)から、図1の黒線部は確実に通れる。
(点の位置関係は見やすいものを選んだ)
(i) 図1の状態において、折れ線の端点から、まだ通っていない点に引くことができない場合。
このとき、通れない道を黄色で示すと、図2のようになる。
四本条件より、図3の黒線部は通れることになる。
図3において太く示した経路が題意を満たす。
(ii) 図1の状態において、折れ線の端点から、まだ通っていない点に、一回だけ引くことができ、それ以上
伸ばすことができない場合。
このとき、通れる部分を黒で、通れない部分を黄色で示すと、図4のようになる。
四本条件から、通れる道を黒で示すと、図5のようになる。
図5において、A と B とがつながっている場合は、図6に太く示した経路が題意を満たす。
A と B とがつながっていない場合は、四本条件より、図7の黒線部が通れ、太く示した経路が題意を満たす。
(iii) 図1の状態において、折れ線の端点から、まだ通っていない点に二回引くことができる場合。
このときの状況は図8のようになる。
ここで、A と B とがつながっている場合は、題意を満たす経路が存在することは明らかである。
A と B とがつながっていないと仮定する。
このとき、A は 1, 2, 3, 4 の三点以上とつながり、B は 0, 1, 2, 3 の三点以上とつながっている。
したがって、A のつながっている点 x 、B のつながっている点 y で、
x=y+1 をみたすものが存在する。
このときの状況は、図9か図10かのいずれかである。
それぞれにおいて、太く示した経路が題意を満たす。
【問題３】
x2+y2+px+qy+r=0 と x2+y2+p'x+q'y+r'=0 との交点は、
直線 (p-p')x+(q-q')y+(r-r')=0 の上に乗っていることは明白である。
すなわち、これが二円の交点を通る直線である。
もう一つの円 x2+y2+p"x+q"y+r"=0をも考えれば、問題にいう三直線は、
(p-p')x+(q-q')y+(r-r')=0,
(p'-p")x+(q'-q")y+(r'-r")=0,
(p"-p)x+(q"-q)y+(r"-r)=0 である。
このうち任意の二つを連立させると、他の一つと等しくなることは明白である。
すなわち、これらの三直線は同一であるか、または一点で交わる。
三直線が同一でないこと、また、線分に限定しても一点で交わることは、図から明らかである。
◆出題者のコメント。
かえるさん、T.Kobayashiさん、解答ありがとうございます。
お二人ともすべて正解です。
いずれの証明も実に鮮やかですね。
【問題１】は、赤線で結ばれた２点は知り合い同士で青線で結ばれた２点は知り合い同士でないと解釈すると、
６人がいれば、互いに知り合い同士の３人か、互いに知り合い同士でない３人が、必ず存在することを意味します。
すぐ分かることですが、５人ではそのような３人が必ず存在するとは限りません。
ですから、互いに知り合い同士か互いに知り合い同士でないｎ人が必ず存在する最少人数をＦ(ｎ)とすると、
Ｆ(３)＝６です。
また、明らかにＦ(２)＝２です。
ところが、ｎが大きくなると急に複雑になるため、Ｆ(６)は未だに分かっていないそうです。
【問題２】は、以下のような一般形の問題にしても証明は可能です。
よろしければ挑戦してみてください。
ｎ(≧３)点あり、どの点も他のｋ点以上と直接線で結ばれている。
このとき、どの点からであっても他のすべての点を１度ずつ通り戻ってこれることを示せ。
| ただし、ｋは | ｎ ２ |
以上の最小な整数。 |
◆東京都 かえる さんからの解答。
【問題４】
８人をＡＢＣＤＥＦＧＨとする。
まず、丁度６人友達を持つ人がいるので、ＡとＢＣＤＥＦＧを友達、ＡとＨを友達でない、としても一般性は
失われない。
ここで、Ｈが丁度６人友達を持つと仮定すると、ＡとＨは友達でないことから、ＨとＢＣＤＥＦＧが友達にな
るが、全員少なくとも２人以上友達を持つことになってしまうので、１人しか友達を持たない人がいる条件に
反する。
従って、Ｈは６人友達を持つことはなく、丁度６人友達を持つ人がＡの他に１人いるので、Ｂが丁度６人友達
を持つとしても一般性は失われない。
ここで、ＢがＨと友達でない、すなわち、ＢがＡＣＤＥＦＧと友達と仮定すると、ＡＢＣＤＥＦＧは友達を２
人以上持つことになり、１人しか友達を持たない人が２人いる条件に反する。
従って、ＢとＨは友達であり、ＢがＡＣＤＥＦＨと友達であるとしても一般性は失われない。
この状態で、１人の友達を持つのはＧＨの２人だけであるので、この２人は他の友達を持てない。
丁度５人友達を持つ人がいるので、ＧＨの友達を増やせないことを考慮して、ＣがＡＢＤＥＦと友達であると
仮定しても一般性は失われないが、ＡＢＣＤＥＦの友達は３人以上になってしまい、友達を丁度２人持つ人が
いる条件に反する。
以上より、題意の条件を満たすことがないことが示された。
（感想）あまりエレガントでなく、どろどろした解答になってしまいました・・・。
【問題５】
ｎ(≧２)チームによる総当たり戦の結果には、
矢印に従って進んでもｎ個の点すべてを１度ずつ通る道筋が必ず存在する・・・（＊）
ことを数学的帰納法により示す。
（１）ｎ＝２のとき
勝者から敗者に矢印が引けるので（＊）は成立。
（２）ｎ＝ｋのとき（＊）が成立すると仮定する。
ｎ＝ｋ＋１のとき（＊）が成立することを示す。
ある特定のチームをＸとする。
チームＸを除くｋ個のチームについて、仮定によりｋ個の点を全て１度ずつ通る道筋が存在する。
その道筋の順に、チームに１、２、３、・・・ｋと番号を付ける。
総当たり戦なので、チームＸはチーム１、チーム２、・・・チームｋと戦っており、
（ア）チームＸがチーム１に勝つ
（イ）チームＸが、チームｐに負けて、チームｐ＋１に勝つ（１≦ｐ≦ｋ−１）
（ウ）チームＸがチームｋに負ける
のいずれかが必ず起こっている。
（ア）の場合、Ｘ→１→２→・・・→ｋ
（イ）の場合、１→２→・・・→ｐ→Ｘ→ｐ＋１→・・・→ｋ
（ウ）の場合、１→２→・・・→ｋ→Ｘ
と、いずれの場合も、ｋ＋１個の点を全て１度ずつ通る道筋が存在し、
ｎ＝ｋ＋１のときも（＊）が成立。
以上より、題意が示された。
◆出題者のコメント。
かえるさん、解答ありがとうございます。
【問題４】も【問題５】も、みごとな証明だと思います。
とりわけ【問題５】は実に鮮やかですね。
この【問題５】と『一方通行の経路』は、すべての２点間に向き(優劣)が存在するときの代表的な証明問題です。
ちなみに【問題４】は私の考案ですが、論理を駆使すれば中学生でも解ける筈です。
以下は、出題者として考えていた証明です。
「６人」と答えた２人は、それぞれある１人以外は全員友達です。
そこで、「６人」と答えた人と友達でない各１人を捜してみます。
もし、「６人」と答えたある１人が、「１人」と答えた２人以外と友達でないなら、
「６人」と答えたもう１人は、「１人」と答えた２人のどちらとも友達でない筈です。
すると、「６人」と答える筈はなく、明らかに不合理です。
また、「６人」答えた２人とも、「１人」と答えた同じ１人と友達でないなら、
「１人」と答えたもう１人は、「６人」と答えた２人のどちらとも友達の筈です。
すると、「１人」と答える筈はなく、明らかに不合理です。
よって、「６人」と答えた２人は、「１人」と答えた２人の内の互いに別な１人と友達ではありません。
これを角度を変えて表現すると、
「５人」,「４人」,「３人」,「２人」と答えた４人は、「６人」と答えた２人のどちらとも友達で、
「１人」と答えた２人は、「６人」と答えた２人の内の互いに別な１人と友達です。
このことから、もし「６人」と答えたその２人がその場にいなければ、
「５人」,「４人」,「３人」,「２人」,「１人」,「１人」と答えた６人は、
「３人」,「２人」,「１人」,「０人」,「０人」,「０人」と答えた筈です。
すると、６人の内で友達がいる人は、「３人」,「２人」,「１人」と答えた３人なので、
「３人」と答えた人の友達は、多くても２人しかいない筈です。
これは、明らかに不合理です。
◆東京都 かえる さんからの解答。
【問題６】
どの３点も同一直線上にない、ｎ個ずつの赤い点と青い点が同じ平面上にあるとき、どの２本も接しない両端
点が赤と青のｎ本の線分が引ける。・・・（＊）を数学的帰納法で示す。
（１）ｎ＝１のとき 明らかに（＊）は成立する。
（２）ｎ＝ｋのときに（＊）が成立すると仮定する。
ｎ＝ｋ＋１のとき、仮定より、ある特定の赤点Ｒ、青点Ｂを除く、ｋ個ずつの赤、青の点について、どの２本
とも接しない両端点が赤と青のｋ本の線分が引ける。
線分ＲＢがｋ本の線分のうちｐ個の線分と交点を持つ場合、ｐ個の線分の端点である赤、青の点を交点がＲに
近い方から順に、
Ｒ（１）、Ｒ（２）、・・・Ｒ（ｐ）、Ｂ（１）、Ｂ（２）、・・・Ｂ（ｐ）とする。
このとき、線分ＲＢ（１）、Ｒ（１）Ｂ（２）、Ｒ（２）Ｂ（３）、・・・・・、Ｒ（ｐ−１）Ｂ（ｐ）、Ｒ
（ｐ）Ｂ及び残りの（ｋ−ｐ）本の線分は、どの２本も接しない両端点が赤と青の（ｋ＋１）本の線分にな
る。
線分ＲＢがｋ本の線分と交点を持たない場合には、線分ＲＢとｋ本の線分が、どの２本も接しない両端点が赤
と青の（ｋ＋１）本の線分になる。
よって、ｎ＝ｋ＋１のとき（＊）が成立する。
（１）（２）より自然数ｎについて（＊）が成立し、題意が示された。
【証明了】
【問題７】
ｎ個の点を１つの曲線で結び、並び順に、Ｐ（１）、Ｐ（２）、・・・Ｐ（ｎ）とする。
（１） Ｐ（１）とＰ（２）〜Ｐ（ｎ）を結んで（ｎ−１）辺。
（２） Ｐ（２）とＰ（３）〜Ｐ（ｎ）を結んで（ｎ−２）辺。
（３） （１）（２）の辺が邪魔をするので、Ｐ（３）〜Ｐ（ｎ）は隣同士しか結べない。
Ｐ（３）Ｐ（４）、Ｐ（４）Ｐ（５）、・・・Ｐ（ｎ−１）Ｐ（ｎ）の（ｎ−３）辺。
以上より、（１）＋（２）＋（３）＝（ｎ−１）＋（ｎ−２）＋（ｎ−３）＝３ｎ−６辺
【証明了】
◆出題者のコメント。
かえるさん、解答ありがとうございます。
コメントが２年近くも遅くなってしまい、非常に申し訳なく思っています。(汗)
【問題６】
残念ですが、
「線分{Ｒ,Ｂ1}、線分{Ｒ1,Ｂ2}、線分{Ｒ2,Ｂ3}、…、線分{Ｒp,Ｂ} のどの２本も接しない」
とは限りません。
〔反例〕
各点の位置をｘｙ座標で表します。
線分{Ｒ(0,0),Ｂ(4,0)}が、線分{赤(1,-1),青(1,3)}と線分{赤(2,-3),青(2,1)}の２本と交点を持つとき、
Ｒ1＝赤(1,-1)、Ｒ2＝赤(2,-3)、Ｂ1＝青(2,1)、Ｂ2＝青(1,3) となりますが
線分{Ｒ(0,0),Ｂ1(2,1)}と線分{Ｒ1(1,-1),Ｂ2(1,3)}は交わってしまいます。
【問題７】
示された方法をとると、確かに交差しない辺は(３ｎー６)本存在し、それが最多ですね。
でも、別の方法ならどうなのでしょう？
示された方法で、ｎ(≧３)個の点には交差しない辺が(３ｎー６)本は確実に存在するので、
〔 ｎ(≧３)個の点における交差しない辺の最多は(３ｎー６)本以上である 〕
ことは理解できますが、(３ｎー６)本が最多である証明にはなっていないと思います。
つまり、どのような方法でも(３ｎー６)本が最多であることを証明しなければならないのでは…。
◆愛知県 迷子の雄猫 さんからの解答。
【問題６】
●証明１
まず、ｎが２以上のとき、とある直線で、直線のどちらの側にも赤い点／青い点の両方があり、かつ直線の片側には赤青同数の点があるように分割できる・・・（＊１）ことを
示す。
（１−１）
どの３点も同一直線上にないため、特定の赤い点／青い点を結ぶと、赤い点／青い点が辺上と外部にはないが頂点上または内部にある、凸多角形を作ることができる。
（１−２）
上記の凸多角形の辺のうち、赤い点と青い点を結んだ辺がある場合、その辺と平行な直線で、その辺とそれ以外に分割できるため、（＊１）は成立する。
（１−３）
上記の凸多角形の辺の全てが同色である場合、一般性を失わずに全て赤色としてよい。
上記の凸多角形の外部に黒い点Ｂを、多角形から十分離してとると、以下の条件を満たすように、直線Ｌ（１）〜Ｌ（ｎ−１）を引くことができる。
条件１．直線Ｌ（ｋ）の点Ｂ側には、赤い点と青い点をあわせてｋ個の点が存在する。
条件２．直線Ｌ（ｋ）の点Ｂ側に存在する点は全て、直線Ｌ（ｋ＋１）の点Ｂ側に存在する。
直線Ｌ（１）の点Ｂ側には赤い点が１つ存在するが、直線Ｌ（ｎ−１）の点Ｂ側には赤い点より青い点のほうが１つ多く存在する。
よって直線Ｌ（１）〜Ｌ（ｎ−１）のうち少なくとも一本について、（＊１）が成立する。
●証明２
どの３点も同一直線上にない、ｎ個ずつの赤い点と青い点が同じ平面上にあるとき、どの２本も接しない両端点が赤と青のｎ本の線分が引ける。・・・（＊２）を数学的帰納法で示す。
（２−１）ｎ＝１のとき 明らかに（＊２）は成立する。
（２−２）ｎ＝ｋ以下のときに（＊２）が成立すると仮定する。
ｎ＝ｋ＋１のとき、証明１より、（＊１）を満たすように分割すると、直線Ｌの点Ｂ側にはｋ個以下の点があるから、直線Ｌの点Ｂ側だけを考えると、（＊２）が成立するように線分を引くことができる。
直線Ｌの点Ｂ側でないほうも、同様に（＊２）が成立するように線分を引くことができる。
引いた線分は直線Ｌに接しないし交わらないため、全体として（＊２）が成立するように線分を引くことができる。
よって、ｎ＝ｋ＋１のとき（＊）が成立する。
（２−１）（２−２）より自然数ｎについて（＊２）が成立し、題意が示された。
証明おわり
◆出題者のコメント。
迷子の雄猫さん、解答ありがとうございます。
みごとな証明だと思います。
特に凸多角形の頂点がすべて同色のときの証明が実に鮮やかです。
「赤点が１つ多い状態に赤点か青点のどちらかを１つずつ加えていくと最後は青点が１つ多い状態だった」
ならば、加えていく途中で赤点と青点が同数の状態が少なくとも１回は必ずあった筈。
この論法、とても説得力がありますが、これも中間値の定理なんでしょうね。