ホーム >> その他 >> 特殊な作図装置による最短の作図時間
hide or visible

問題の説明

与えられた図形は $1$ 辺が $1cm$ の正方形が $7$ つつながった図形です.平面上を自由に動く作図装置でこの図形を描くのにかかる最短時間を求めてください.

ヒント・考え方

まず,与えられた図形の長さの和は $20 cm$ ですから,$20$ 秒以上かかることは明らかですね.さらに,この図形は一筆書き可能ではありません.これは下の主張からすぐにわかります.

一筆書きの一般論: 平面上の図形が一筆書き可能であるための必要十分条件は,奇数次数の点が $0$ または $2$ 個であることである.

このことより,$20$ 秒で描くことは不可能であることがわかります.つまり,どこかで必ずペンを紙から離さなければなりません.この時間をいかに減らすかがこの問題のポイントです.

解説

与えられた図形を $H$ とします.また,平面上に与えられた図形 $X$ の長さの和を $|X|$ で表すことにします.たとえば,$|H|=20cm$ です.さて,求めるべきは与えられた作図装置で図形 $H$ を描くのにかかる最短時間です.まず,つぎの主張を示します.

主張: 図形 $H$ を含む平面上の図形であって,一筆書き可能であるもののうち,長さの和が最小のもの(のひとつ)を $G$ とする.求めるべきは $|G|$ である.

これはつぎのようにわかります.まず,作図装置で $H$ を含む図形 $G$ を描くことを考えます.ただし,図形 $H$ の部分を描いているときはペンを紙につけており,そうでないときにはペンを紙から離していると考えます.すると,図形 $G$ の長さの和は,作図装置で図形 $H$ を描く時間に相当します.したがって,主張が成り立ちます.

さて,残った問題は主張中の $G$ を見つけることです.
図形 $H$ において,下図の赤い $4$ つの点のみ次数 (つまり,接している辺の本数)が奇数であり,他の点はすべて次数が偶数です.
一筆書き
一筆書きの一般論より,赤い $4$ つの頂点のうちの $2$ 点を線分でつないだ図形は一筆書き可能です.このうち,たとえば下図のように結べばその図形の長さの和が最小になります.
一筆書き
まとめると,この赤い線分も含めた図形 $G$ は $H$ を含む一筆書き可能な図形のうち,長さの和が $20+\sqrt{2} cm$ で最小です.したがって,与えられた図形を描くためには,最短で $20+\sqrt{2}$ 秒かかります.