数学の部屋へもどる。◆広島県 清川 育男 さんからの解答。
【問題１】
1) A-E-B-C-D-A 12分
2) A-D-C-B-E-A 12分
【問題２】
図は奇点が２個なので一筆書きは可能ですが、奇点は起点か終点でなければならばい。
この場合
B---------D、D--------Bは可能である。
しかし、この問題は、Aが起点でかつ終点でなければならないので、一筆書きは不可能です。
ここでB-C、C-Dに道を入れると（往路と復路は別と考える）すべての点が偶点となる。
そうなるとどこを起点にしても、一筆書きが可能で起点が終点となる。
この場合は最短経路となる。
A-D-C-D-E-C-B-C-A-B-E-A 28分
答え ２８分。
◆海外 西野 友朗 さんからの解答。
【問題１】
１２分
例えば、Ａ→Ｄ→Ｃ→Ｂ→Ｅ→Ａ
２ １ ２ ３ ４
【問題２】
２８分
１．全ての道を通る最短ルートは、それぞれの道を１回だけ通る「一筆書き」のルートです。
ある図形が一筆書きできるかどうかは、以下の様に確認できます
(証明は省略)。
☆奇数個の線が出ている点を「奇数点」、偶数個の線が出ている点を「偶数点」とよぶことにすると：
ａ）奇数点が０個か２個の時だけ，一筆書きで図形が書ける。
ｂ）奇数点が２個の時はその一つから書き始めなければいけない。
その場合、一筆書きはもう一方の奇数点で終わる。
ｃ）偶数点ばかりだったら，どこから書き始めてもよい。
その場合、一筆書きの始点と終点は一致する。
２．問題の図形の各点が、奇数点・偶数点のどちらになるか確認すると：
| 点 | 線の数 | 奇数点or偶数点 |
| Ａ | ４ | 偶数点 |
| Ｂ | ３ | 奇数点 |
| Ｃ | ４ | 偶数点 |
| Ｄ | ３ | 奇数点 |
| Ｅ | ４ | 偶数点 |
となります。
一筆書きはできますが、その場合始点・終点がＢ・Ｄ（またはその逆）となり、題意を満たしません。
３．題意を満たすためには、幾何学的にはこの図形に線を追加して、偶数点だけからなる図形にしなくてはなりません。
ただし、無制限に線を追加していい訳ではなく、既存の線を２本にするような形で追加しなくてはなりません
（これは、この線の道を２回通ることに相当する）。
さらに、この問題は最短ルートを求めるものなので、追加する線はできる限り短くなくてはなりません。
４．それでは、どの様に線を追加すれば良いか検討します。
奇数点をなくして偶数点にしなくてはなりませんので、線の始点をＢ・Ｄにすべきことは明らかです。
ＢとＤを結べば話が早いのですが、新しい道を作ることになり上記の条件を満たしません。
また、Ｂから始まる線の終点とＤから始まる線の終点が異なる場合（例えば、Ｂ―ＣとＤ―Ｅ）、それらの終点が新たに奇数点となってしまい、これも条件を満たしません。
よって、Ｂから始まる線の終点とＤから始まる線の終点は一致しなくてはなりません。
Ａ・Ｃ・Ｅそれぞれの場合で、追加する線の長さがどうなるかを計算すると：
Ａの場合： Ｂ―Ａ４分、Ｄ―Ａ２分、計６分
Ｃの場合： Ｂ―Ｃ２分、Ｄ―Ｃ１分、計３分
Ｅの場合： Ｂ―Ｅ３分、Ｄ―Ｅ３分、計６分
となり、Ｂ―Ｃ、Ｄ―Ｃの線を追加する（この道を２回通る）場合が最短となることがわかります。
５．この結果、最短ルートの所要時間は２８分（各ルートの合計＋３分）となります。
これは例えば：
Ａ→Ｄ→Ｃ→Ａ→Ｂ→Ｃ→Ｅ→Ｄ→Ｃ→Ｂ→Ｅ→Ａ ２ １ ３ ４ ２ ３ ３ １ ２ ３ ４ ２回通る部分で実現できます。［完］
◆栃木県の小学生 Ｍ−善範 さんからの解答。
【問題１】の回答
Ａ−Ｅ−Ｂ−Ｃ−Ｄ−Ａ
【問題２】の回答
Ａ−Ｂ−Ｃ−Ｂ−Ｅ−Ａ−Ｄ−Ｃ−Ｄ−Ｅ−Ｃ−Ａ
２８分
学校（６年２学期）では、一筆書きは、それぞれの点に集まる線の数が、どこも偶数のときと、奇数の点が２つのときに書けると勉強した。
この問題は、奇数の点が２つで普通ならできるが、スタート地点とゴールが交わる点が偶数のＡと決まっているので一筆書きでは書けない。
そのために、Ｂの点とＤの点の一番少ない２分と１分の線を往復することにより２８分になりました。
スタート地点が決まっていなければ、
Ｂ−Ａ−Ｅ−Ｂ−Ｃ−Ｅ−Ｄ−Ｃ−Ａ−Ｄ となり簡単に書くことができる。
◆富山県 いくまる さんからの解答。
【問題１】
Ａ→Ｄ→Ｃ→Ｂ→Ｅ→Ａ (12分)
【問題２】
それぞれの地点から出ている道の数は、
A:4本、B:3本、C:4本、D:3本、E:4本。
BとDからは奇数本の道が出ており、この2点から出ている道のうち少なくとも1本ずつは2回通る必要がある。
これらの道から最も時間のかからない道をそれぞれ選び(B-CおよびC-D)、2回通るように経路を選ぶと、
Ａ→Ｂ→Ｃ→Ｂ→Ｅ→Ａ→Ｃ→Ｅ→Ｄ→Ｃ→Ｄ→Ａ(25+2+1=28分)
問題2の解答はこれで良いと思うのですが、問題1はヒントの時間があるのでこれが答えだと分かりました。
しらみつぶしで探すしかないのでしょうか。
◆東京都 Asami さんからの解答。
【問題１】
最低４本の異なる道を通らねばならないが、異なる道を４本しか使わないとき、どの道も２回以上使わねばならないので和は少なくとも
(1+2+2+3)×2＝16
異なる道を最低５本使うとき、
もし１，２，２，３，３(和が11)の道を通ることが実現可能なら、それが最短である。
しかし、ＡからスタートするのでＡ→Ｄ→Ｃ→Ｂを通らねばならないので、あと３，３で再びＡに戻ることはできない。
次に、和が12となるルートを探してみる。
Ａ→Ｄ→Ｃ→Ｂ→Ｅ→Ａで、確かに和が12となるルートが実現している。……(答え)
補足
ここでは
『“ｎ地点”のすべてを通るルート(再び同じ地点に戻る必要はない)が存在するならば、異なる道は少なくともn-1本存在しなければならない』
『“ｎ地点”と“n-1本の道”に対し、地点Ａからスタートしてすべての点を巡って再びＡに戻ってくるには、どの道も少なくとも２回通らねばならない』
を認めてしまっています。
グラフ理論の最初の方に出てきそうな、直感的にほぼ明らかな命題であるとは思いますが、ついでですので、証明を書いておきます。
『“ｎ地点”のすべてを通るルート(再び同じ地点に戻る必要はない)が存在するならば、異なる道は少なくともn-1本存在しなければならない』………★
◆証明：
ｎ＝２のとき明らか
ｎ＝ｋのとき成り立つと仮定して、ｎ＝k+1のとき、
どの地点からも２本以上の道が出ているなら、
異なるすべての道の数≧2(k+1)／2＝k+1
ある地点Ａから１本しか出ていないなら、たとえばＡ→Ｂとなっていたとすると、
”Ａ”と“→”を取り除いた残りのｋ地点に関して、これらすべての地点を通るルートが依然として存在しているので、帰納法の仮定により、これらの間には
少なくともk-1本の異なる道が存在している。
再び“Ａ”と“→”を戻すことによって、異なる道が少なくともｋ本あることがわかる。
(以上帰納法によって証明終了)
『“ｎ地点”と“n-1本の道”に対し、地点Ａからスタートしてすべての点を巡って再びＡに戻ってくるには、どの道も少なくとも２回通らねばならない』
◆証明：
ｎ＝２のとき明らか
ｎ＝ｋのとき成り立つと仮定して、ｎ＝k+1のとき、
Ａからスタートして次に着いた地点をＢとすると、Ｂとはまったく別の地点ＣからＡへと戻って巡回を終えることはあり得ない。
なぜなら、ＣＡ間の道を取り除いたら、k-1本しか道はないのだが、依然として“k+1地点”のすべてを通るルートが存在しているので、★より矛盾が生じるからである。
従って最後もＢ→Ａと戻ってくるしかなく、ＡＢ間の道と点Ａを除けば、ＢからスタートしてＢへ戻るルートになっているが、これは帰納法の仮定より、どの道も少なくとも２回通っている。
従って、再びＡＢ間の道と点Ａを戻すことによって、どの道も少なくとも２回通らねばならないことがわかる。
(以上帰納法によって証明終了)
【問題２】
すべての道を通らねばならないので、もし、一回ずつ通るようなルート(＝一筆書き)が存在すればそれが答えなのだが、Ｂ，Ｄは通過点だからそれぞれに接続する道は、偶数でないので不可能と分かる。
(やっぱりそこまで甘くないですね(^^;))
同時に、「全ての道を少なくとも１回は通らなければならない」ので、Ｄ，Ｂに接続する道で、少なくとも２回通らねばならない道が必ず存在することも分かる。
もし、ＣＤ間とＢＣ間を丁度２回通るようなルートが存在すれば、それが最短ルートである。
実際、
Ａ→Ｅ→Ｂ→Ｃ→Ｅ→Ｄ→Ａ→Ｃ→Ｄ→Ｃ→Ｂ→Ａ
の和が28のルートが存在している。………(答え)
◆石川県 平田 和弘 さんからの解答。
【問題１】の解答
Ａをスタートとして最短で進むパターンは(逆順を除いて)次の10通りとなります。
順路 合計TIME(分) Ａ→Ｂ→Ｃ→Ｅ→Ｄ→Ａ 14 Ａ→Ｂ→Ｅ→Ｃ→Ｄ→Ａ 13 Ａ→Ｂ→Ｅ→Ｄ→Ｃ→Ａ 14 Ａ→Ｃ→Ｂ→Ｅ→Ｄ→Ａ 13 Ａ→Ｃ→Ｄ→Ｅ→Ｂ→Ａ 14 Ａ→Ｄ→Ｃ→Ｅ→Ｂ→Ａ 13 Ａ→Ｄ→Ｅ→Ｃ→Ｂ→Ａ 14 Ａ→Ｄ→Ｅ→Ｂ→Ｃ→Ａ 13 Ａ→Ｅ→Ｂ→Ｃ→Ｄ→Ａ 12 Ａ→Ｅ→Ｄ→Ｃ→Ｂ→Ａ 14従って
【問題２】の解答
この問題は一筆書きの問題と関連がありまして、この図形自体は一筆書きが可能です。
それは有名な一筆書きの定理、
「有限個の点を有限個の線で結んだ図形(グラフ)が一筆書きできるための必要十分条件は、グラフの勝手な２個の頂点を結ぶ辺(線)の列があり(連結)、かつ奇頂点(１個の頂点から出ている線の数が奇数の頂点)の個数が０または２である。」
によります。
具体的には、Ｄをスタート地点として
Ｄ→Ａ→Ｃ→Ｄ→Ｅ→Ｃ→Ｂ→Ｅ→Ａ→Ｂ
または、Ｂをスタート地点として
Ｂ→Ａ→Ｃ→Ｄ→Ｅ→Ｃ→Ｂ→Ｅ→Ａ→Ｄ
などのルートで可能ですが、必ず奇頂点がスタート地点でないとできません。
(奇頂点がスタートでない(途中にある)と、その頂点へは入→出→入となって最後の点になってしまいますがそのような点が２つあるのは矛盾しているので。)
従って、この問題でもＡ地点をスタートしては一筆書きは不可能です。
ところがすべての地点が偶頂点であれば可能です。
具体的には、もしＢとＤを結ぶ線があればすべての頂点が偶頂点となりますので、
Ａ→(Ｂ→Ｄ)→Ｅ→Ｃ→Ｂ→Ｅ→Ａ→Ｃ→Ｄ→Ａ・・・・(1) Ａ→(Ｂ→Ｄ)→Ｅ→Ｃ→Ｂ→Ｅ→Ａ→Ｄ→Ｃ→Ａ・・・・(2) Ａ→Ｅ→Ｃ→(Ｂ→Ｄ)→Ｅ→Ｂ→Ａ→Ｃ→Ｄ→Ａ・・・・(3) Ａ→Ｅ→Ｃ→(Ｂ→Ｄ)→Ｅ→Ｂ→Ａ→Ｄ→Ｃ→Ａ・・・・(4) Ａ→Ｅ→(Ｂ→Ｄ)→Ｅ→Ｃ→Ｄ→Ａ→Ｂ→Ｃ→Ａ・・・・(5) Ａ→Ｅ→(Ｂ→Ｄ)→Ｅ→Ｃ→Ｄ→Ａ→Ｃ→Ｂ→Ａ・・・・(6) Ａ→Ｂ→Ｅ→Ｃ→(Ｂ→Ｄ)→Ｅ→Ａ→Ｃ→Ｄ→Ａ・・・・(7) Ａ→Ｂ→Ｅ→Ｃ→(Ｂ→Ｄ)→Ｅ→Ａ→Ｄ→Ｃ→Ａ・・・・(8) Ａ→Ｂ→Ｅ→Ｄ→Ｃ→(Ｂ→Ｄ)→Ａ→Ｅ→Ｃ→Ａ・・・・(9) Ａ→Ｂ→Ｅ→Ｄ→Ｃ→(Ｂ→Ｄ)→Ａ→Ｃ→Ｅ→Ａ・・・・(10)(逆ルートも同じ)で一筆書きが可能です。
ところが問題図ではＢ→Ｄの線がないので複数の線の組み合わせで代用する(代わりのルートを使用する)しかありません。
Ｂ→Ｄを２辺で代用する組み合わせは、次の３通り
Ｂ→Ｃ→Ｄ 合計3分
Ｂ→Ｅ→Ｄ 合計6分
Ｂ→Ａ→Ｄ 合計6分
となり、Ｂ→Ｃ→Ｄのルートが最短となります。
以上より
上記(1)〜(10)のうちＢ→ＤをＢ→Ｃ→Ｄで置き換えた
Ａ→Ｂ→Ｃ→Ｄ→Ｅ→Ｃ→Ｂ→Ｅ→Ａ→Ｃ→Ｄ→Ａ Ａ→Ｂ→Ｃ→Ｄ→Ｅ→Ｃ→Ｂ→Ｅ→Ａ→Ｄ→Ｃ→Ａ Ａ→Ｅ→Ｃ→Ｂ→Ｃ→Ｄ→Ｅ→Ｂ→Ａ→Ｃ→Ｄ→Ａ Ａ→Ｅ→Ｃ→Ｂ→Ｃ→Ｄ→Ｅ→Ｂ→Ａ→Ｄ→Ｃ→Ａ Ａ→Ｅ→Ｂ→Ｃ→Ｄ→Ｅ→Ｃ→Ｄ→Ａ→Ｂ→Ｃ→Ａ Ａ→Ｅ→Ｂ→Ｃ→Ｄ→Ｅ→Ｃ→Ｄ→Ａ→Ｃ→Ｂ→Ａ Ａ→Ｂ→Ｅ→Ｃ→Ｂ→Ｃ→Ｄ→Ｅ→Ａ→Ｃ→Ｄ→Ａ Ａ→Ｂ→Ｅ→Ｃ→Ｂ→Ｃ→Ｄ→Ｅ→Ａ→Ｄ→Ｃ→Ａ Ａ→Ｂ→Ｅ→Ｄ→Ｃ→Ｂ→Ｃ→Ｄ→Ａ→Ｅ→Ｃ→Ａ Ａ→Ｂ→Ｅ→Ｄ→Ｃ→Ｂ→Ｃ→Ｄ→Ａ→Ｃ→Ｅ→Ａ逆ルートも含めると
Ａ→Ｄ→Ｃ→Ａ→Ｅ→Ｂ→Ｃ→Ｅ→Ｄ→Ｃ→Ｂ→Ａ Ａ→Ｃ→Ｄ→Ａ→Ｅ→Ｂ→Ｃ→Ｅ→Ｄ→Ｃ→Ｂ→Ａ Ａ→Ｄ→Ｃ→Ａ→Ｂ→Ｅ→Ｄ→Ｃ→Ｂ→Ｃ→Ｅ→Ａ Ａ→Ｃ→Ｄ→Ａ→Ｂ→Ｅ→Ｄ→Ｃ→Ｂ→Ｃ→Ｅ→Ａ Ａ→Ｃ→Ｂ→Ａ→Ｄ→Ｃ→Ｅ→Ｄ→Ｃ→Ｂ→Ｅ→Ａ Ａ→Ｂ→Ｃ→Ａ→Ｄ→Ｃ→Ｅ→Ｄ→Ｃ→Ｂ→Ｅ→Ａ Ａ→Ｄ→Ｃ→Ａ→Ｅ→Ｄ→Ｃ→Ｂ→Ｃ→Ｅ→Ｂ→Ａ Ａ→Ｃ→Ｄ→Ａ→Ｅ→Ｄ→Ｃ→Ｂ→Ｃ→Ｅ→Ｂ→Ａ Ａ→Ｃ→Ｅ→Ａ→Ｄ→Ｃ→Ｂ→Ｃ→Ｄ→Ｅ→Ｂ→Ａ Ａ→Ｅ→Ｃ→Ａ→Ｄ→Ｃ→Ｂ→Ｃ→Ｄ→Ｅ→Ｂ→Ａの20通りが28分で最短となります。
(感想)
問題１は最短ルートの場合を分けて根気よく調べていけばわかります。
問題２はすべての辺の和は25(分)でかつ、Ａからスタートして一筆書きができないので時間は多分間違いないと思いますが、ルートがどうも上記(1)〜(10)ですべて出し尽くしているかどうかは自信がありません。
◆福岡県 中山 さんからの解答。
「問題１」
Ａ→Ｄ→Ｃ→Ｂ→Ｅ→Ａ の順に移動すれば、１２分で巡回できる
「問題２」
Ａ→Ｂ→Ｃ→Ａ→Ｄ→Ｃ→Ｅ→Ｄ→Ｃ→Ｂ→Ｅ→Ａ
の順に移動すれば、２８分で巡回できる
問題１は、１分や２分の道を利用することで、１２分で巡回できます。
このルート（またはその逆の手順）が最短の道のりです。
問題２は、Ｂ→Ｄという道があれば一筆書きの要領で巡回できることを考慮して、Ｂ→ＤのかわりにＢ→Ｃ→Ｄ（もしくはＤ→Ｃ→Ｂ）という手順を加えることで、最短の２８分で巡回できます。
解答は最短手順の一例で、他の巡回ルートも考えられます。
今回の問題は、一筆書きの法則を知っていれば割と解きやすい問題のようですね。
◆奈良県 岸本 大和 さんからの解答。
【問題１】
Ａ→Ｄ→Ｃ→Ｂ→Ｅ→Ａ 12分
（Ａ→Ｅ→Ｂ→Ｃ→Ｄ→Ａでも同じ）
【問題２】
ケーニヒスベルクの橋を思い出しました。
一筆がきの各点は
@書き始めかつ書き終わり
A通過点
B書き始めであり、書き終わりでない
C書き始めでなく、書き終わり
の４種類で、@Aは偶点、BCは奇点。
定義から奇点がゼロまたは２個の場合のみ一筆がきが可能。
◆静岡県 ぶん さんからの解答。
【問題１】
最低12分です。
A→(2)D→(1)C→(2)B→(3)E→(4)→A
【問題２】
(悪魔のささやき ヒント を見てしまった)
ひとふでがきができればいい。
なるほど。
一筆書きができるためには、奇数本の線が出ている点が2個か0である必要がある。
この問題の場合は、Ｂ，Ｄが奇数本であとは偶数本。
ということは、ＢかＤからスタートすれば一筆書きができる。
でも、本問の場合はＡからスタートしてAに帰るということなので、ＢとＤを結ぶ経路を作ってしまえばいい。
こうすれば、ＢからでてＢにもどることができる。
つまり、閉じた輪ができるのだから、ＡからＡに戻ることも同じ。
経路に要する時間を考えて、ＢＣ間、ＣＤ間にもう1ぽんずつ経路を作ってしまいましょう。
全部の経路の時間を合計すると25分なので、ＢＣ，ＣＤの3分をあわせた28分が正解！
たとえば
Ａ→(4)Ｂ→(2)Ｃ→(3)Ａ→(2)Ｄ→(1)Ｃ→(2)Ｂ→(3)Ｅ→(3)Ｄ→(1)Ｃ→(3)Ｅ→(4)A
これって、全部で何通りの答えがあるのだろうか？
樹系図を書こうと思ったけど止めました。
◆ 問題へもどる
◆ 今週の問題へ