MathLabs

第6問

a1,…,ana_1,\ldots,a_n を相異なる正の整数とし、MM を s=a1+⋯+ans=a_1+\cdots+a_n を含まない n−1n-1 個の正の整数の集合とする。バッタは 00 から出発し、長さ a1,…,ana_1,\ldots,a_n の跳躍をある順序で右向きに nn 回行う。この順序を、バッタが MM の点に一度も着地しないように選べることを証明せよ。
ステップ 3/5: 最後に残った地雷に当たる跳躍を置き換える
前のステップ次のステップ
ざっくり言うと

チェックポイントの右に地雷がなければ、短い経路が最大の地雷に達したとき最長の跳躍でそれを飛び越えられる。

m=max⁡M⟹m−ak+an>mm=\max M\quad\Longrightarrow\quad m-a_k+a_n>m
詳しい解説

まず x∉Mx\notin M で、xx より大きい地雷がないとする。MM が空なら終わりであり、そうでなければ m=max⁡Mm=\max M とおく。短い長さと M∖{m}M\setminus\{m\} に帰納法を適用する。得られた経路が mm に着地しなければ ana_n を最後に加える。kk 回目の長さ aka_k の跳躍が mm に着地するなら、その跳躍を ana_n に替え、aka_k を最後に置く。その段階の新しい点は m−ak+an>mm-a_k+a_n>m であり、それ以後の点もすべて mm より大きく、終点は ss である。x∈Mx\in M で xx より大きい地雷がない場合も、m=xm=x とし M∖{x}M\setminus\{x\} に帰納法を適用すれば同じである。