あみだくじは何回引けば元に戻る - 操作としての順列

同じあみだくじを続けて引くと、いつか元の並びに戻ります。5 人のあみだくじなら、6 回で戻るものもあれば 4 回で戻るものもある。

並び方を「結果」ではなく「動かす操作」として見ると、こういう問いに答えられます。順列のもう一つの顔です。

並びではなく移り方を見る

これまで順列は、$n$ 個を並べた結果でした。$12345$ を $31524$ に並べ替える、という具合です。

同じことを、番号を動かす操作として読むこともできます。1 番の人が 3 番の位置へ、2 番の人が 1 番の位置へ、という移り方の指定です。

あみだくじは、この操作そのもの。上から入って下へ出るまでに、どこへ移るかが決まっています。

たどると輪ができる

1 番がどこへ行くかを追い、その行き先がまたどこへ行くかを追う。これを繰り返すと、いつか 1 番へ戻ります。

戻るまでの道のりが 1 つの輪になります。残った番号でも同じことをすると、また別の輪ができる。

こうして、どんな操作も輪の集まりに分かれます^[1]。

例：輪に分ける

6 人の操作で、1 が 3 へ、2 が 1 へ、3 が 5 へ、4 が 2 へ、5 が 4 へ、6 が 6 へ移るとします。

1 から追うと $1\to 3\to 5\to 4\to 2\to 1$ で、長さ 5 の輪になります。

残るのは 6 だけ。6 は自分の位置に留まるので、長さ 1 の輪です。

この操作は、長さ 5 の輪と長さ 1 の輪に分かれました。

何回で元に戻るか

長さ $k$ の輪は、$k$ 回繰り返すと元に戻ります。1 周するのに $k$ 回かかるからです。

輪が複数あるときは、全部が同時に戻る回数を探します。それぞれの長さの最小公倍数です^[1]。

さきほどの例なら、長さが 5 と 1 なので最小公倍数は 5。5 回引けば元の並びに戻ります。

例：戻るまでの回数が変わる

5 人のあみだくじを 2 つ比べます。

1 つ目は $1\to 2\to 3\to 1$ と $4\to 5\to 4$ に分かれるとします。長さ 3 と 2 なので、最小公倍数は 6。6 回で戻る。

2 つ目は $1\to 2\to 1$ と $3\to 4\to 3$ と $5\to 5$ に分かれるとします。長さ 2、2、1 で最小公倍数は 2。2 回で戻ります。

同じ 5 人でも、輪の分かれ方で回数が変わる。並びの見た目からは分かりません。

5 人で最も長くかかるのは

5 人の場合、輪の長さの組は 5 の分割になります。$5$、$4+1$、$3+2$、$3+1+1$、$2+2+1$、$2+1+1+1$、$1$ を 5 個の 7 通り。

それぞれの最小公倍数は 5、4、6、3、2、2、1。いちばん大きいのは $3+2$ の 6 です。

つまり 5 人のあみだくじは、どんなに長くても 6 回で元に戻ります。

横棒 1 本は入れかえ

あみだくじの横棒 1 本は、隣り合う 2 人を入れかえる操作です。この形を入れかえといいます^[1]。

横棒を何本か引けば、その入れかえを順に行ったことになる。どんな並べ替えも、入れかえを繰り返せば作れます。

長さ $k$ の輪は、$k-1$ 回の入れかえで作れます。$1\to 2\to 3\to 1$ なら 2 回。

偶奇は変わらない

同じ並べ替えを作るのに、入れかえの回数は 1 通りではありません。遠回りすれば増やせます。

ただし、回数の偶奇は必ず同じになる^[1]。偶数回で作れる並べ替えは、何度やり直しても偶数回でしか作れません。

だから、あみだくじの横棒の本数は、目的の並びによって偶数か奇数かが決まっています。

例：偶奇を確かめる

$12345$ を $21345$ にするには、1 と 2 を入れかえる 1 回で足ります。奇数回です。

$12345$ を $23145$ にするには、$1\to 2\to 3\to 1$ の輪なので 2 回。偶数回になります。

輪の長さから計算できます。長さ $k$ の輪が $k-1$ 回なので、輪の長さから 1 を引いた値をすべて足せばよい。

例：席替えを繰り返す

30 人のクラスで、同じ規則の席替えを繰り返します。何回で元の席順に戻るか。

輪に分けて、長さの最小公倍数を求めます。30 人でも手順は変わりません。

長さが 2、3、5 の輪に分かれていれば、最小公倍数は 30。30 回かかります。

長さが 6 と 10 と 14 なら、最小公倍数は 210。人数より多い回数がかかることもあります。

例：カードを切る

52 枚のカードを、いつも同じ手順で切ります。何回切れば元の並びに戻るか。

これも輪に分けて最小公倍数を取る問題です。カードの動き方が決まっていれば、回数が計算できる。

同じ手順を繰り返すかぎり、いつかは必ず元に戻ります。輪の長さが有限だからです。

例：戻らない場合はあるか

ありません。番号は有限個なので、たどればいつか出発点に帰ります。

もし帰らないとすると、途中で 2 か所から同じ番号へ入ることになる。操作は 1 対 1 なので、それは起こりません。

だから、どんな操作でも必ず輪に分かれます。

よくある誤り

順列を結果としてではなく、動かす操作として読む。この見方に切り替えると、繰り返しの問いに答えられます。

参考文献

^[1] が輪への分解と入れかえと偶奇、^[2] が順列の基本、^[3] が分割の考え方、^[4] と ^[5] が各国語での整理です。