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 の点に一度も着地しないように選べることを証明せよ。
ステップ 1/5: 帰納法の命題を強めて記号を定める
前のステップ次のステップ
ざっくり言うと

最長の跳躍を最後に使うのが自然であり、その直前の点が重要なチェックポイントになる。

a1<⋯<an,s=a1+⋯+an,x=s−ana_1<\cdots<a_n,\quad s=a_1+\cdots+a_n,\quad x=s-a_n
詳しい解説

nn に関する帰納法で少し強い命題を証明する。すなわち、n−1n-1 個以下の正の禁止点からなる任意の集合で、全和 ss が禁止されていなければ、跳躍を安全に並べられる。長さを a1<⋯<ana_1<\cdots<a_n と並べ、s=a1+⋯+ans=a_1+\cdots+a_n、x=s−anx=s-a_n とおく。n=1n=1 は明らかである。