手をつなぐ                                 戻る

 当HPがいつもお世話になっているHN「よおすけ」さんからの出題です。
                                     (平成24年11月28日付け)

  5つの国から集まった人たちが両手つないで1つの輪をつくる。どの異なる2つの国をとっ
ても、それぞれの国から来た人たちがどこかで手をつなぐようにしたい。

 このような輪をつくることができる最小の人数を求めよ。(出典:1970年 大阪大学)




































(答) らすかるさんから解答を頂きました。(平成24年11月28日付け)

   10人。

例:ACDAEBDECB

        


 攻略法さんからのコメントです。(平成24年11月29日付け)

 5点A、B、C、D、Eを正5角形の頂点として並べる。点Aから順に、B、C、D、E、A、C、E、
B、D、Aと一筆書きで結んでいく。辺と対角線が、それぞれの国から来た人たちが手をつな
いだことになる。


(コメント) 攻略法さんの解法は、とても自然ですね!感動しました。

  自分以外の全ての人と手をつなぐということは、完全グラフで、
 例えば、左図の正5角形。

  その図形を一筆書きで結んでいくと、らすかるさんの解以外に
 もたくさん例を作ることが出来る。

  また、条件を満たす最小の数が「10」ということも、辺と対角
 線の数を数えることにより合点がいく。素晴らしい!