手をつなぐ
当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」ということも、辺と対角 線の数を数えることにより合点がいく。素晴らしい! |