図1 AとBを入れ換えるには横棒が最低1本必要。

図2 A,B,Cを逆順にするには横棒が最低3本必要。

図3 A,B,C,DのAだけを一番右に移動させるには
最低3本の横棒が必要。

図4 図3の下に別のあみだくじを継ぎ足してB,C,D,Aの
B,C,Dの部分だけを逆順にするには図2と同じ位置
関係にある3本の横棒を持つ図4に示すあみだくじが
あればよい。

図5 図3の下に図4を繋ぎ合わせたものが図5である。

図6 A,B,C,D,EのAだけを一番右に移動させるには
最低4本の横棒が必要。

図7 図6のB,C,D,E,AのB,C,D,Eの部分だけを逆順に
するには図5と同じ位置関係にある6本の横棒をもつ図7
に示すあみだくじがあればよい。

図8 図6の下に図7を繋ぎ合わせたものが図8である。

以上を繰り返して下記のようなあみだくじを作れば、A,B,C,D,E,F,G,H,I,Jの
10個が全て逆順になる。
このときの横棒の本数は、1+2+3+4+5+6+7+8+9=45 より45本
図9

上記の解法では45本が最低本数であることの証明にはなっていません。
例えば、A,B,C,Dを全て逆順にするあみだくじは図5だけではなく、
下記のようなものでも可能であり、横棒の本数は図5と同じ6本です。

図10

A,B,C,Dを逆順にするためには横棒が最低6本必要である理由は
次のように説明できます。

まず、図5に示したあみだくじのそれぞれの経路を、なめらかな線で
書くと次のようになります。

図11


図12
図11のなめらかな線の部分だけを抜き出したものが左図
になります。


図13
左図は図12の線を更になめらかにしたもので、あみだくじの
横棒1本が、線と線の1つの交点に対応しています。
横棒のところでは図1で示したように、左右の入れ替え
が起こりますので、交点でも左右が入れ替わります。
A,B,C,Dを逆順にするためには、
AとBの入れ替え A⇔B @
AとCの入れ替え A⇔C A
AとDの入れ替え A⇔D B
BとCの入れ替え B⇔C C
BとDの入れ替え B⇔D D
CとDの入れ替え C⇔D E
が必要ですから、少なくとも6個の交点が必要です。
つまり、横棒は少なくとも6本必要になります。
※異なる色の線が1度だけ交わる場合が、横棒を
  最低本数にしたあみだくじに対応します。

A,B,C,D,E,F,G,H,I,J の10個を逆順にするためには以下の入れ替えが必要になります。
従って、少なくとも必要な横棒の本数は
1+2+3+4+5+6+7+8+9=45 より 45本


IMDパズルランド TOPへ