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 の点に一度も着地しないように選べることを証明せよ。
ステップ 2/5: 右側に地雷がある安全なチェックポイント
前のステップ次のステップ
ざっくり言うと

チェックポイントの先に地雷があれば、その手前の地雷は少なすぎて短い跳躍をすべて妨げられない。

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

x∉Mx\notin M かつ M∩(x,∞)≠∅M\cap(x,\infty)\ne\varnothing とする。xx 以下の禁止点は高々 n−2n-2 個である。n−1n-1 個の長さ a1,…,an−1a_1,\ldots,a_{n-1} とそれらの点に帰納法の仮定を適用し、点を踏まずに xx へ到達する。最後の跳躍 ana_n は x+an=sx+a_n=s に着地し、これは MM に属さない。