$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$ になります．
