問題

直線上を座標 $x_i (x_i \lt x_{i+1})$ に並んだ $N$ 体のロボット $R_i$ は、それぞれ次の操作が可能である。

今いる座標 $x$ から、座標 $x-2, x-1$ の空いている好きな方に移動する

座標が0以下でゴールになる。 $N$ 体のロボットの順位としてありえるパターンを求める。

考察

$i \lt j$ で $R_j$ が $R_i$ よりも先にゴールするとき、座標 $x−1$ が空席、座標 $x$ に $R_i$ が、座標 $x+1$ に $R_j$ がいる状態になり、 $j$ 番目のロボットが座標 $x−1$ に移動するような場面がある。ここで、 $R_i$ が座標 $x−1$ に移動すれば状況を入れ替えることができ、 $i \lt j$ かつ $R_j$ が $k$ 位でゴールできるなら、 $R_i$ は $k$ 位かそれよりも良い順位でゴールできることを示せた。

次に、 $i$ 番目のロボットが1位でゴールできる時、 $R_j (j \lt i)$ は座標 $2j-1$ に並ぶことができ、またそのとき限り1位になれることを示す。

$R_j (j \lt i)$ が座標 $2j-1$ に並べないとき $R_i$ が1位にならないことを示す

$R_j (j \lt i)$ が座標 $2j-1$ に並べないとき、座標 $x_l \lt 2l-1 (l \lt i)$ なる $R_l$ が存在する。 $R_i$ が $R_l$ を飛び越え1位になるためには、それ以前のロボットが全て1つ以上のマスを開けて並ぶ必要があり、これを実現しようとすると少なくとも $R_1$ がゴールしてしまう。よって、 $R_j (j \lt i)$ が座標 $2j-1$ に並べないとき1位にならない。

$R_j (j \lt i)$ が座標 $2j-1$ に並ぶとき $R_i$ が1位になれることを示す

$R_i$ についての帰納法で示す

$i \leq 2$ の時は自明
$i = k$ で成り立つとき、 $i = k+1$ で成り立つことを示す

$R_j (j \lt k)$ を座標 $2j-1$ に並べる（帰納法の仮定より可能）。 $R_k$ の初期の座標が $2k-1$ 以上のときのみ、 $R_k$ を $2k-1$ に移動できる。このとき、 $R_k, R_{k+1}$ をそれぞれ座標 $2k-1, 2k$ に移動できる。その後 $R_{k+1}$ を1つ飛ばしで動かせば $R_{k+1}$ が1位になれる。

以上より、 $R_j (j \lt i)$ が座標 $2j-1$ に並ぶとき $R_i$ が1位になれる。したがって、 $i$ 番目のロボットが1位でゴールできる時、 $R_j (j \lt i)$ は座標 $2j-1$ に並ぶことができ、またそのとき限り1位になれることが示された。

また、 $R_i$ の最高順位が $k$ 位のとき、 $R_l (l \lt i)$ から $k-1$ 体除いた $i-k+1$ 体が座標 $1, 3, \cdots, 2(i-k)+1$ に並ぶことができ、またそのときに限る。このことから、 $R_i$ の最高順位は $R_{i-1}$ の最高順位か、それ $+1$ だということもわかる。