（※続・追伸）国際数学オリンピックの難問から～バッタの問題～

yamanujan.hatenablog.com

 　以上述べたように、

（命題）

　a(1),a(2),⋯,a(n) を相異なる正の整数とし、M を n-1個の正の整数からなる集合とする。M は s=a(1)+a(2)+⋯+a(n) を含まない。

　数直線の0 の地点にいるバッタが、数直線の正の向きに n 回ジャンプする。

n 回のジャンプの距離は a(1),a(2),⋯,a(n) の並べ替えである。

　このとき、並べ替えをうまく選べば、バッタがM の要素に対応するn-1点に、一度も着地しないようにできる。

を最初に証明した。なお、「M は s=a(1)+a(2)+⋯+a(n) を含まない。」の箇所は、「M は s=a(1)+a(2)+⋯+a(n) より小さい要素しか含まない。」と厳しく読み替えて証明しても、題意を損なわないので、そう読み替えた上で証明をした。

　ここで、上記の命題を変形させて、　

（命題）

　a(1),a(2),⋯,a(n) を相異なる正の整数とし、M を n個の正の整数からなる集合とする。M は s=a(1)+a(2)+⋯+a(n) より小さい要素しか含まない。また、M の要素のうち少なくとも一つは、a(1),a(2),⋯,a(n) のいずれとも異なる値をもつ。

　数直線の0 の地点にいるバッタが、数直線の正の向きに n 回ジャンプする。

n 回のジャンプの距離は a(1),a(2),⋯,a(n) の並べ替えである。

　このとき、並べ替えをうまく選べば、バッタがM の要素に対応する n点に、一度も着地しないようにできる。

 という命題を作成して、これが正しいことを証明しようとした。

　が、失敗であった。反例が容易に見つけられた。特定のパターンのa(1),a(2),⋯,a(n) に対しては、M の要素をうまく選ぶことにより、どのようにジャンプの並べ替えを選んでも、バッタがM の要素に対応する点に着地することを余儀なくされたのであった。

　では、こういうゲームを考えてみるのはどうであろうか。

（準備）

攻撃側と守備側に分かれる。正の整数 nが与えられる。

（手順）

①攻撃側は、異なる正の整数、a(1),a(2),⋯,a(n) を選択する。

②守備側は、攻撃側の選択に対応して、s=a(1)+a(2)+⋯+a(n) より小さいn個の正の整数からなる集合Mを作成する。ただしM の要素のうち少なくとも一つは、a(1),a(2),⋯,a(n) のいずれとも異なる値でなければならない。

③攻撃側は、並べ替えをうまく選び、バッタがM の要素に対応する n点に一度も着地しないように試みる。

（結果）

③が成功→攻撃側の勝ち、③が失敗→攻撃側の勝ち

　

　このゲームにおいては、ジャンプの内容が与えられるのではなく、攻撃側が任意に選択することができる。攻撃側が優秀であれば、どんなに能力の高い守備側をも打ち負かせるのか、それを考察したい。