hide or visible

問題の説明

$1$ から $n$ までの整数の並び方は $n!$ 通りあります.はじめ,これらの数字がどのように並んでいたとしても,与えられた操作を有限回繰り返すといずれは必ず左端の整数が $1$ となることを示す問題です.
与えられた操作によって,数字の並びが変わらないのは左端の整数が $1$ のときであり,そのときに限ります.したがって,状態がループすることなく,いずれは必ず停止することを示すことになります.

左端の数の最大値に注目する

左端の数として取りうる値は当然 $1$〜$n$ までの $n$ 通りしかないので,操作全体を通して,左端の数の最大値が存在します.その最大値を $M_1$ とします.たとえば, $$31425→41325→23145→32145→12345$$ の左端の数の最大値 $M_1$は $4$ です.

さて,一番左端に $M_1$ が来たあと操作を行うと,$M_1$ は左から $M_1$ 番目に移ります.このあと,$M_1$ が $M_1$ 番目から移動することはあるでしょうか.実はそのようなことは起こりえません.なぜなら,$M_1$ は左端にくる数の最大値だったので,以降の操作で左から $M_1$ 番目以降に影響を与えることはないからです.$M_1$ が左から $M_1$ 番目に移ったあとの過程で左端にくる数の最大値を $M_2$ とします.$M_1 > M_2$ です.同様に,$M_2$ が左端から $M_2$ 番目に移ったあとの過程で左端にくる数の最大値を $M_3$ とすると,$M_1 > M_2 >M_3$ となります.以下同様にして,左端に来る数の狭義単調減少列 $M_1 > M_2 >M_3 > \cdots$ がつくれます.$M_1,M_2,...$ はすべて正の整数なので,ある正の整数 $k$ があって $M_k=1$ となります.つまりいずれは左端の数が $1$ になります.