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 の点に一度も着地しないように選べることを証明せよ。
ステップ 5/5: 安全な二跳躍の尾で完了する
ざっくり言うと

帰納法で選んだ二跳躍の直前まで進み、その二跳躍で安全な二つのチェックポイントを経て安全な全和に到達する。

(b1,…,bn−2,an,ai)(b_1,\ldots,b_{n-2},a_n,a_i)
詳しい解説

上で得た ii に対し、aia_i と ana_n 以外の n−2n-2 個の長さと禁止集合 M∖{x,m}M\setminus\{x,m\} に帰納法を適用する。その全和は viv_i で禁止されていないので、安全な順序を (b1,…,bn−2)(b_1,\ldots,b_{n-2}) とする。順序 (b1,…,bn−2,an,ai)(b_1,\ldots,b_{n-2},a_n,a_i) を用いる。前半は残りの地雷を避け、次の着地点は vi+an=uiv_i+a_n=u_i、最後の着地点は ui+ai=su_i+a_i=s であり、いずれも安全である。これで帰納法が完了する。