『一筆書き』解答


◆東京都 けめ丸 さんからの解答。

どんな一筆書きも、必ず交差しないようにすることができます。
具体的には、次のようにします。

まず、交差を許して、一筆書きのルート
(スタート地点、ゴール地点、進行方向)をひとつ決めます。

次に、スタート地点からルートに従って進んでいき、交差に遭遇したら、その都度、以下のルールに従ってルートを変更します。

  D          D
  ↑          ↑
A→・→B(交差)を A→・←B(非交差)にとりかえる。
  ↑          ↓
  C          C
図のAは、今交差に進入してきた道を表している。
ルート変更の際、進入してきた道(A)の向きは変えないが、
向きの変わる道(B,C)については、
その途中(B−C間)の道([*]と表す)もすべて向きを変えるものとする。

交差していたときには、
A→B→[*]→C→Dの順で一筆書きされていたのですから、
A→C→[*]→B→Dの非交差ルートは、[*]を逆行しているだけで、もちろん一筆書きルートです。
またこのことから、ルートが連結性を保つことも分かります。

ここでは十字路(4差路)のみを考えていますが、6差路や8差路などの多重交差点は、4差路にほどいてから上記のルールを適用すればよいので、問題ありません。

また、3差路や5差路などの奇数交差点は、必ずそこがスタート地点かゴール地点になっているはずなので、スタートもしくはゴールする道を交差点から外してよく、結局偶数交差点に帰着されます。

交差点に出会う度に上記のルールに従って変更すれば、ゴールしたときには、交差のないルートが得られていることは明らかでしょう。


 『一筆書き』へ

 数学の部屋へもどる