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 の点に一度も着地しないように選べることを証明せよ。
ステップ 4/5: 難しい場合に安全な対を見つける
前のステップ次のステップ
ざっくり言うと

チェックポイントの地雷は対のどちらも妨げず、他の各地雷は高々一つの対しか妨げられない。

x∈M,M∩(x,∞)≠∅x\in M,\quad M\cap(x,\infty)\ne\varnothing
詳しい解説

次に x∈Mx\in M かつ M∩(x,∞)≠∅M\cap(x,\infty)\ne\varnothing とする。m=max⁡Mm=\max M とおく。1≤i≤n−11\le i\le n-1 を満たす各 ii について ui=s−aiu_i=s-a_i、vi=s−ai−an=x−aiv_i=s-a_i-a_n=x-a_i と定める。このとき vi<x<uiv_i<x<u_i なので、地雷 xx はこれら n−1n-1 個の対のどちらも妨げない。uiu_i は相異なりすべて xx より大きく、viv_i も相異なりすべて xx より小さい。したがって残りの n−2n-2 個の地雷はそれぞれ高々一つの対しか妨げない。ゆえに、これら n−1n-1 個の対の中にある ii で ui∉Mu_i\notin M かつ vi∉Mv_i\notin M となる。