あみだくじの問題です．あみだくじの横線は，隣り合う縦線をつなぐように引かなければなりません．たとえば，下図のように横線を $3$ 本引くと，$ABCDEF$ というならびは，$BCAEDF$ というならびになります．
さて，$ABCDEF$ というならびを $DAFBEC$ にするために引く横線の最小本数はいくつでしょうか．
ヒント
解答例
最低本数は $7$ 本であることを示します．まず，下図のように $7$ 本引けば，問題のあみだくじを実現できることがわかります．(どのようにしてこの引き方を見つけたかは後述します)
つぎに $7$ 本が最低本数であること，すなわち，$6$ 本以下の横線をどのように引いても問題のあみだくじは実現できないことを示します． まず，下図のように，$2$ 直線上に，適当に，$6$ つずつ，点を配置します．
つぎに，上の各アルファベットから，下の対応する各アルファベットに線分をひきます．このとき，$3$ 本以上の線分が共点をもたないようにしておきます．(必要なら各点同士の間隔や直線の間隔を適当に調整すれば，この条件を必ず満たすようにできます)
このように線分を引いてつくれらた図形はひとつのあみだくじを表しています．つまり，線分同士の交点が，あみだくじの横線に対応しています．
逆に，ひとつのあみだくじが与えられると，それは上の各アルファベットから，下の対応する各アルファベットに曲線を引くことに対応します．このとき，曲線同士の交点が横線の本数に対応しています．すると，必ず $2$ つの曲線の交点の個数は，図形 $X$ における対応する $2$ つの線分の交点の個数以上になります．つまり， $$(問題の条件を実現する横線の本数) \ge (線分同士の交点の個数)$$ が成り立ちます． ここで，図形 $X$ の線分同士の交点の個数を数えると，$7$ 個です．
したがって， $$(問題の条件を実現する横線の本数) \ge 7$$ が成り立ちます．
結局，線分で繋いだときが最小になるので，冒頭のあみだくじは，線分でつないでつくられたということです．
