第5問

黒板上の $n$ 個の数を1列に並べ、左から右への位置を用いて $q=\sum_{i=1}^n(i-1)a_i$ とおく。ただし $a+b$ は常に消された右側の数の位置に書かれるものとする。位置 $i<j$ に $a,b$ があったとき、操作により $q$ は $(i-1)(1-a)+(j-1)((a+b)-b)=(i-1)+a(j-i)\ge a\ge\gcd(a,b)$ だけ変化する。したがって $q-t$ は決して減少せず、常に $q-t\ge q_0-t_0=\tfrac{n(n-1)}2$ が成り立つ。ここで $q_0=\tfrac{n(n-1)}2$（すべて $1$ の初期値）、$t_0=0$ である。