４．作図の問題
縦、横、斜め、どの方向でも秒速１cmで動けるペンを 備えた作図装置がある。 ペンが紙についていれば動きに従って線が描かれ、 ペンが紙から離れていれば何も描かれない。 この装置で下の図形を描くのに最短で何秒かかるか。 ただし、図に現れる角はすべて直角とし、 ペンを紙につけたり離したりする動作には 時間はかからないものとする。
問題の出典
第５回日本数学オリンピック予選（１９９５）問題
「数学オリンピック１９９１〜１９９６」
日本評論社
答えと解説
４．縦、横、斜め、どの方向でも秒速１cmで動けるペンを
備えた作図装置がある。
ペンが紙についていれば動きに従って線が描かれ、
ペンが紙から離れていれば何も描かれない。
この装置で下の図形を描くのに最短で何秒かかるか。
ただし、図に現れる角はすべて直角とし、
ペンを紙につけたり離したりする動作には
時間はかからないものとする。
回答・その１
（ペンネ−ム：碧都柊一）
1cm/1secとして、点線の部分は実際にはかかないところ、
SQR(2)。従って全体では12+SQR(2)秒。
回答・その２
（ペンネ−ム：コレクトコ−ルは１０６番！）
この作図装置において最も描くのに適している図形は 「一筆書きのできる図形」である。 なぜならば、「描いていない時間」つまり「ムダな時間」が ０になるからである。
さて、問題の図の点をＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｉとおく。
一筆書きの可能な図形の条件
@各々の点から伸びている線の本数がすべて偶数である。
A伸びている線の本数が奇数になっている点が２ヶ所だけ。
@Aのいすれかが成り立てばよい
残念ながら、問題の図形は上に掲げた条件に合致しないので、 一筆書きはできない。
そこで、図形にできるだけ短い線を書き加え、 一筆書きのできる図形を作図するのが、最も合理的である。 （書き加えた線の部分はペンを紙から離しておけばよい。）
この図形には、線が３本延びている点が４ヶ所（点Ｂ、Ｄ、Ｆ、Ｈ） あるので、うち２ヶ所を直線で結べば、上の条件のAに合致するので、 一筆書きが可能になる。 そこで、とりあえずＢＦを結び、 （別に、ＢＤでもＤＨでもＦＨでもよい。）これを点線で表記する。
ＢＦの長さは、ＢＣ＝ＣＦ＝１cmであり、 ∠Ｃ＝∠Ｒ（90ﾟ）なので、 三平方の定理よりSQR(2)cmになる。 また、実線部分の総延長は、考えてみればわかるが１２cmになる。
さて、作図装置のペン先を点Ｈがくる位置におく。 そして、下に示すようにたどる。 （下図にル−トを模式的に示す。この他にも距離の同じになるル−トはある。）
Ｈ→Ｇ→Ｄ→Ｅ→Ｈ→Ｉ→Ｆ→Ｂ→Ｃ→Ｆ→Ｅ→Ｂ→Ａ→Ｄ
これが最短ル−トである。前述よりこのル−トの長さは、12+SQR(2) cm
作図装置は１cm/秒だから、12+SQR(2)秒
回答・その２・コメント
完璧なレポ−トだね！ 12+SQR(2)秒が最短だという理由もきちんと示されている。
正解者（ペンネ−ム）
ＢＲＡＩＮＭＡＮＩＡ
ＫＯＵ
ＦＬＡＳＨ！
凡人。
ミネラル Ｗａｔｅｒ
石川ごえもん
Ａｈ！Ｍｙ Ｇｏｄｄｅｓｓ
はなフムフム
ぜにがたのとっつあん
ベジタリアンな肉食獣
ＢＡＢＹ ＭＩＮＮＩＥ
サンジェルマン
まとめ
一筆書きの問題だということがわかったかな？ もし、ペンを最初から最後まで離さずに描ければ（一筆書きできれば） 一番無駄がないわけで、 そうすると１２秒です。
しかし、この図形は一筆書きできませんから、１２＋α。 このαをいかに小さくするかが問題です。
ところで、一筆書きといえば、「ケ−ニヒスベルグの７つの橋問題」。
ケ−ニヒスベルグの７つの橋問題
今から２世紀以上も昔、ドイツがまだプロシャと呼ばれていた時代、
ケ−ニヒスベルグの町の話である。
この町を流れるプレ−ゲル川に２つの島とそれらを結ぶ７つの橋があった。
この７つの橋のどの橋もちょうど１回ずつ渡るような散歩のコ−スは
ないだろうか？ というのが人々の話題となっていた。
この問題を解決したのが、スイス生まれの偉大な数学者オイラ−（1707-1783）です。
オイラ−はこう考えたのです。
まず陸と島を点で表し、橋はそれらを結ぶ線とする。
これが下の図です。この図が一筆書きできるかどうかによる、と。
そこで、どんな図形が一筆書きができて、どんな図形ができないかを研究して得たのが 「一筆書きの定理」です。
すなわち、各点から出ていく（or入ってくる）辺が偶数のときこの点を偶点、 奇数ならば奇点と呼ぶ。そして、図形全体に奇点がいくつあるか数えます。 （奇点の個数が奇数ということはありえない。 なぜなら、１つの辺は必ず両端で１回ずつ、つまり２回カウントされるからです。）
@奇点がないならばこの図形はどこから書き始めても一筆書きできる。
A奇点が２つある図形は、どちらか一方の奇点から書き始めれば、 もう一方の奇点で書き終わり、一筆書きできる。
B奇点が４つ以上ある図形はどうやっても一筆書きできない。 ケ−ニヒスベルグのグラフは４点すべてが奇点ですから不可能というわけです。
@Aのケ−スについて更に付け加えるならば、どうやっても必ず一筆書きできるというわけではなく、
うまいル−トをたどればできる、ということです。誤解のなきよう。
さて問題に戻りますが、与えられた図形は奇点が４つあり、従ってα≠０。
（一筆書きできないからネ）
そこで、２つの奇点を結ぶ線分を付け加えて、この２点を偶点に変えてしまえばいいのだ！
(ペンネ−ム：コレクトコ−ルは１０６番！）さんの回答通りですね。
戻る