(※追伸)国際数学オリンピックの難問から~バッタの問題~
上記のリンクでは、バッタが n回ジャンプする場合、ジャンプする順序をうまく変えることによって、途中に存在する (n-1)点のいずれにも着地しないで最終着地点に到達できることを証明する問題を紹介し、私なりの解答を掲載した。
では、途中に存在するの点の数が、ジャンプ回数に等しい n点であった場合はどうであろうか。
果たして、「Mの要素である点に着地しないと最終着地点に到達できない」場合が確実に存在する。
M = {a(1),a(2)・・・,a(n)}
と決めた場合である。
その理由は明らかだ。
1回目のジャンプとして、a(1),a(2)・・・,a(n)のうちのどれを選んでも、選択した値はMに含まれるからである。これはもうどうしようもない。
では、 M の要素が {a(1),a(2)・・・,a(n)}とどれくらい違いが生じた場合に、最終着地点に到達できるようになるのだろうか?
もし、1回目のジャンプにおいて、 M の要素である点に着地しない選択が1通りだけ可能な場合
を考える。つまり、
M = {a(1),a(2)・・,a'(k),・・,a(n)} (a'(k)≠a(k))
の場合である。
この時、 n回のジャンプの順序をうまく入れ替えることにより、M の要素である点に着地しないで最終着地点に到達できると言えるのか?
答は「No」である!
例えば、
n=4
a(1) = 3, a(2) = 6, a(3) = 9, a(4) = 12
s = a(1)+a(2)+a(3)+a(4) = 30
M = {6,9,12,15}
の場合を考えよう。
1回目のジャンプとして、a(2)=6,a(3)=9,a(4)=12のいずれを選んでも、M の要素である点に着地することがわかる。
ではなく、a(1)=3を選んだらどうか。
第 2回目のジャンプの選び方にかかわらず、M の要素である点に着地してしまう。a(1)+a(2)=3+6=9∈M、a(1)+a(3)=3+9=12∈M、a(1)+a(4)=3+12=15∈M と、いずれの場合でも、 2回目のジャンプの着地点はMの要素である点なのである。
以上より、このジャンプでは、必ずMの要素である点に着地してしまう。
同様な計算により、
n=3
a(1) = 2, a(2) = 4, a(3) = 6
s = a(1)+a(2)+a(3) = 12
M = {4,6,8}
も、必ずMの要素である点に着地してしまう。
一般化すると、
a(1) = m, a(2) = 2m, ・・・, a(n) = nm
s = a(1)+a(2)+・・・+a(n) = n(n+1)m/2
M = {2m,3m,・・・,(n+1)m}
を満たすならば、どのようにジャンプの順序を変えても、必ずMの要素である点に着地してしまう。
・・・・・・・・・・(※)
これは、簡単に証明ができる。
ただし、1回目のジャンプで M の要素である点に着地しない選択が1通りだけ可能で、かつ、必ずMの要素である点に着地してしまう、というケースは他にも存在する。
例えば、
n=3
a(1) = 1, a(2) = 5, a(3) = 6
s = a(1)+a(2)+a(3) = 12
M = {5,6,7}
である。
さらに調べると、
n=3
a(1) = 1, a(2) = 2, a(3) = 3
s = a(1)+a(2)+a(3) = 6
M = {3,4,5}
の場合も該当する。しかもこの場合など、1回目のジャンプで M の要素点に着地しない選択が2通り(a(1)とa(2))可能なのである。
(※)をさらに一般化する。
a(1) = m, a(2) = 2m, ・・・, a(n) = nm
s = a(1)+a(2)+・・・+a(n) = n(n+1)m/2
M = ({t-n+1)m,(t-n+2)m,・・・,tm}(t は自然数で、 n≦ t< (n(n+1)/2) )
を満たすならば、どのようにジャンプの順序を変えても、必ずMの要素である点に着地してしまう。
検証は難しくない。
間隔をmとしてMの要素点が n個並んでいるから、そこを通過する場合に、必ずどれかの点に着地してしまうのである。
この話を進めていくと、面白いゲームができそうである。