国際数学オリンピックの難問から～バッタの問題～
上記リンク先にて、国際数学オリンピック（IMO）で出題された過去難問に関する記事を発見した。
この中には、「過去問の中で最難問」と銘打って、2009年 IMOドイツ大会で出題された組み合わせ問題が紹介されている。その問題を、記号表記を見やすく書き直したものが、以下の通りである。
a(
のジャンプの距離は a(
上記リンク先によると、まあ超難問らしい。
この問題、数か月かかって、私はヘトヘトになりながら何とか解いた。少しの自慢にも値しないが。
とりあえず、以下の通りである。
（解答）
数直線の 0 から s までバッタが
が存在する場合を考える。
すなわち、
数直線の0 から sの間に、Mの要素に対応する (
に一度も着地することなく、
a(1),a(2),⋯,a(n)の並べ替えによるn 回ジャンプを行える。・・・（A）
ことを証明すればよい。
なお、この命題（A）が成立するならば、Mの要素に対応する点の数がn-1より少ない場合においても成立することは明らかである。
数学的帰納法を用いて証明する。
[1] n = 2 のとき
Mの要素は一つだけであり、この要素が、a(1) とも a(2) とも同時に等しくなることはないから、バッタは、この1点に着地しないようにジャンプできる。
[2] n ≦ k （kは任意の2以上の整数）のときに上記の命題（A）が成立すると仮定し、
n = k+1 での状況を調べる。
今、と仮定しても一般性を失わない。k+1回のジャンプ順として、{a(1),a(2),⋯,a(k+1)}を選択したとする。
一方、M = {m(1),m(2),⋯,m(k)} ( m(1)<m(2)<⋯<m(k) ) とおくと、k回ジャンプした到着地点を表す値、
a(1)+a(2)+⋯+a(k) (= s - a(k+1) )
に関して、次の４通りに分類することができる。
① m(k)より大きい場合
② m(k)に等しい場合
③ m(k)より小さくて、m(1),m(2),⋯,m(k-1)のいずれかに等しい場合
④ m(k)より小さくて、m(1),m(2),⋯,m(k-1)のいずれにも等しくない場合
①～④の各ケースに関して、Mの要素である点に着地しないようにジャンプできることを証明する。
＜①の場合＞
数直線の０から a(1)+a(2)+⋯+a(k) (= s - a(k+1) )へは、k回ジャンプして達するが、その間には、Mの要素である点が k点ある。
仮定より、a(1),a(2),⋯,a(k)の順序を入れ替えることで、m(1),m(2),⋯,m(k-1)のいずれの点にも着地しないようにジャンプすることができる。このとき、もしm(k)にも着地しないのであれば、Mの要素である点に着地しない場合であるから命題(A)が成立 する。
もしそうではなく、m(k)にだけは着地すると仮定する。今、m(k)に着地した際のジャンプと a(k+1)を入れ替えると、a(k+1)が最も大きいジャンプであるため、m(k)に着地しないジャンプとなる。
ゆえに、Mの要素である k点に 着地しなくなるから、命題(A)が成立する 。
＜②の場合＞
数直線の０から a(1)+a(2)+⋯+a(k) (= s - a(k+1) )へは、k回ジャンプして達して、その間には、Mの要素である点が (k-1)点ある。
仮定より、a(1),a(2),⋯,a(k)の順序を入れ替えることで、m(1),m(2),⋯,m(k-1)のいずれの点にも着地しないようにジャンプすることができる。
今、m(k)に着地した際のジャンプと a(k+1)を入れ替えると、a(k+1)が最も大きいジャンプであるため、m(k)に着地しないジャンプとなる。
ゆえに、①の場合と同様に、Mの要素である k点に 着地しなくなるから、命題(A)が成立する 。
＜③の場合＞
a(k+1)の出発点をm(i)としたとき、 i<k である。
a(1),a(2),⋯,a(k)のk回のジャンプのうちの1回を a(k+1)の後で行うように、つまり、最後のジャンプとなるように並べ替える。すると当然、a(k+1)の着地点は上図において左側（数直線での負の方向）へ移動するが、この着地点は、m(i)と最終着地点の間に位置している。よって、全 k通りの並べ替えのうち、少なくとも k - (k - i) = i 通りは、Mの要素 m(i+1),⋯,m(k)には着地しない（m(i+1),⋯,m(k)は全部で(k - i)点）。
この i 通りにおけるジャンプa(k+1)の始点は、数直線の 0とm(i)の間のそれぞれ相異なるi点である。数直線の 0とm(i)の間に存在するMの要素は (i-1)点だから、少なくとも1通りは、
a(k+1)の始点も終点もMの要素でなく、最後の始点も終点もMの要素ではない。
というケースが発生する。
つまり、最後の 2回のジャンプを除いて考えると、
間に存在するMの要素は、多くても(k - 2)点であり、ジャンプは(k - 1)回
という場合である。
仮定により、この(k - 1)回のジャンプの順序を並べ替えることによって、この区間のMの要素に対応する点には着地しないようにできる。
このようにして、数直線の 0から最終着地点の sまで、Mの要素である k点に一度も着地しない場合が少なくとも 1通りは存在することが証明された。
＜④の場合＞
a(1),a(2),⋯,a(k)のk回のジャンプにおいて、数直線の 0とa(1)+a(2)+⋯+a(k)の間には (k - 1)以下の個数のMの要素である点しか存在しないので、a(1),a(2),⋯,a(k)の順序をうまく入れ替えると、数直線の 0と a(1)+a(2)+⋯+a(k)の間のどのMの要素である点にも着地しないようにジャンプできる。残りのジャンプは a(k+1)だけである。つまり、数直線の 0から最終着地点の sまで、Mの要素である k点に一度も着地しない場合に該当する。
（証明終）
