6本の縦線を持つあみだくじで、置換$(1, 6)$を実現するものを考える。このとき、必要な横線の最小本数を求める。

1. 問題の内容

6本の縦線を持つあみだくじで、置換$(1, 6)$を実現するものを考える。このとき、必要な横線の最小本数を求める。

2. 解き方の手順

あみだくじは、縦線の順序を入れ替える操作を表す。置換$(1, 6)$は、1番目と6番目の縦線の行き先を入れ替える操作である。

* 縦線が$n$本の場合、隣り合う縦線を入れ替える互換（基本互換）は$(i, i+1)$ ($i=1, 2, ..., n-1$)の形で表される。

* 任意の置換は、基本互換の積で表せる。置換$(1, 6)$は、1番目と6番目を入れ替えるので、隣接互換の繰り返しで実現できる。

* $(1, 6)$を隣接互換の積で表すことを考える。

$(1, 6) = (1, 2)(2, 3)(3, 4)(4, 5)(5, 6)(4, 5)(3, 4)(2, 3)(1, 2)$

このように隣接互換の積で表現すると、9回の隣接互換が必要となる。

しかし、あみだくじでは同じ隣接互換を繰り返しても良い。例えば $(1, 2)(1, 2)$ は何もしないのと同じである。

$(1, 6) = (5,6)(4,5)(3,4)(2,3)(1,2)(2,3)(3,4)(4,5)(5,6)$

隣接互換を並べたときに、最小本数になるような並び方を見つけることを考える。

必要な隣接互換は、

(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)を少なくとも1回ずつ使う必要がある。

また、$(1, 6) = (5, 6)(4, 5)(3, 4)(2, 3)(1, 2)(2, 3)(3, 4)(4, 5)(5, 6)$のような表現が最小本数となる。

隣接互換の組み合わせは、 $(1, 2)$から$(5, 6)$までの5個の隣接互換を順番に並べ、次に$(2, 3)$から$(5, 6)$まで並べるというように行うことで最小本数となる。

したがって、最小本数は5+4+3+2+1 =15ではない。

置換$(1,6)$をあみだくじで実現するためには、最低5個の隣接互換が必要である。

(1 6)を表すには、(1 2)(2 3)(3 4)(4 5)(5 6)(4 5)(3 4)(2 3)(1 2) となるので9個の隣接互換が必要。

互換(1,6)を表すあみだくじの最小の横線の数は５本である。これは、(1 2)(2 3)(3 4)(4 5)(5 6)(4 5)(3 4)(2 3)(1 2)とすることにより9本であみだくじを作成可能。また、(5 6)(4 5)(3 4)(2 3)(1 2)(2 3)(3 4)(4 5)(5 6)とするのも同値。

3. 最終的な答え

5本