◆超難問◆

>>38の解答が、大数２０００年９月号に掲載されている。
取り敢えず答えを。
λ≧1/(ｎ-1)

講評：今年の最難問。結果だけを見れば基本操作だけを考えればよいが、
それを直接証明するのは非常に困難。（中略）全選手中、解けた（６点以上）のは
わずか１６人。日本チームでは●●君のみ。

以前長助が解いたときのコピペ。俺が読んだすう折の本の解答より簡単だし、
実際、彼（彼女だっけ？）も難しいとは思ってない風だった。

C=1/λ-(n-1) とおく。
問題中の操作によって、右端のノミが変更されないときにこの操作をα、変更されるときにβと呼ぶ。
ノミの配置に関する関数Sを右端のノミとその他のノミとの各距離の和として定める。
とくに、初期配置に対するSの値をS_0とする。
操作βによって右端のノミの位置がdだけ右に変更されたとする。この時、Sの増加量は、
(n-1)d-d/λ=-Cd

(i) C > 0 であるとき不可能である事の証明。
全体の操作からβのみを抜き出したとき、右端のノミの位置が、d_1, d_2, d_3, ... d_m と動いたとする。
Sのとる値は正であるから、
S_0 +｛αによる増加量｝+｛βによる増加量｝＞０
｛αによる増加量｝＜０であるので、
S_0 +｛βによる増加量｝＞０
S_0 - C(d_1+d_2+d_3+ ... +d_m) >0
d_1+d_2+d_3+ ... +d_m < S_0/C
よって不可能。

(ii) C≦0 であるとき可能である事の証明。
右端のノミと左端のノミに関してβをｍ回繰り返したときの、右端のノミの移動をd_1, d_2, d_3, ... d_m とする。
｛２匹のノミの距離｝＞S/(n-1)、であるので、d_k > λS/(n-1), ( k=1, 2, ..., m )
βに関してSは単調に増加するので、S≧S_0，d_k > λS_0/(n-1)
d_1+d_2+d_3+ ... +d_m > m{ λS_0/(n-1) }
となるので、ｍを十分に大きくとれば、右端のノミはMよりも右に移動する。
さらに、その他のノミと右端のノミに関して操作を施す事によりすべてのノミがMの右側に移動する。

したがって、C≦0 ⇔ λ≧1/(n+1) が答え。