パズルの国のアリス

蜘蛛たちのジャンプ力(解答)

 ウォーミングアップ問題,つまり蜘蛛たちの技量が完璧な場合は,典型的な例を1つ見いだせばよいだけだから簡単すぎたかもしれない。たぶん一番わかりやすい例は,すべての蜘蛛が等間隔dで東西に一列に並んでいる場合だ。いつも東端の蜘蛛が西端の蜘蛛を越えて跳んでいくことを考えると,跳ぶ前のその2匹の距離は(n−1)dだから,技量が完璧な場合,着地点は西端にいた蜘蛛のさらに西に距離dだけ進んだ地点になる。つまり,蜘蛛全体で考えれば,皆が西にdだけずれた結果になる。これを何度も繰り返していれば,蜘蛛たちは全体として好きなだけ西にずれていくことができる。

 上の例で簡単のため各蜘蛛の間を同距離dとしたことは本質的でない。重要なのは常に東端の蜘蛛が西端の蜘蛛を跳び越すことで,例えば,蜘蛛が3匹いて,それらがabという間隔で東から西に並んでいる場合,最初のジャンプで蜘蛛たちの西最前線は距離d1=(ab)/2だけ西に移動する。次のジャンプではd2=(a+3b)/4だけ移動する。

 一般にk回目のジャンプで西最前線が移動する距離をdkとすると,漸化式dk+2=(dk+1dk)/2が成り立つ。よって,高校数学程度の数列の知識があれば

が導けるだろう。

 明らかにdkは(a+2b)/3に収束するから,蜘蛛がジャンプするごとにその西最前線は平均で(a+2b)/3ずつどこまでも西へ移動していくことがわかる。蜘蛛がn匹いて,それぞれがa1,……,an−1という間隔で東から西に並んでいる場合も同様で,いつも東端の蜘蛛が西端の蜘蛛を跳び越す場合,西最前線は平均で

ずつ西に進み続けるようだが,それを説明するのによいアイデアがないか読者のお知恵を拝借したいところだ。

 さて,ここまでは蜘蛛たちの技量が完璧な場合であり,実はそうではないから,蜘蛛たちの西への移動に限界があることを証明したい。まず2匹だけの場合を考えてそれを参考にしよう。2匹が東西に距離dだけ隔たっているとする。東の蜘蛛が西の蜘蛛を跳び越して着地する地点は,現在の西の蜘蛛からさらに西へrd進んだ地点だ。これを繰り返すと,次は西最前線の位置がさらにr2d進む。このように西最前線の位置は次第に西に移動するが,k回のジャンプ後でも元の東の蜘蛛の位置からの累計は

にとどまり,d/(1−r)を超えることはない。

 一般にn匹の場合はどうだろうか?

 東西に座標軸を取り,東から順に各蜘蛛の座標をx1x2,……,xnとする。すなわちx1x2≦……≦xnである。2匹のときの座標Mx1d/(1−r)のようなものを見つけて,どの蜘蛛の座標もMを超えられないことを示せばいい。いささか天下りだが,どの時点でも一番西にいる蜘蛛の座標xnだけを特別扱いして,変量

Wxnrx1+…+xn−1)

というものを考える。

 xi<xj(≦xn)のとき,xiにいる蜘蛛がxjにいる蜘蛛を跳び越えたとする。その蜘蛛の新しい座標をx′iとすると

xi<xjx′ixjrxjxi)=(1+rxjrxi

である。その位置が一番西にいる蜘蛛の位置xnより西に来た場合,その2匹の蜘蛛の役割が入れ替わるので,新しいWの値は元の値と比べると

xnrxi)−(xirxn)=(1+rxnrxi−(1+rxjrxi=(1+ r)(xnxj)≧0

だけ減少する(jnの場合は変化しない)。また,新しい位置xiが西最前線を更新しない場合,新しいWの値は元の値と比べると

rxirx′irx′ixi)>0

だけ減少する。いずれにせよ,Wは増加することはないから,初期状態でのWの値をW0とすると,どの時点でもxnW0/{1−rn−1)}となることはない。なぜなら,もしそうなったら,そのときのWの値は,他の蜘蛛の位置xi(≦xn)がどうなっていようとも

Wxnrx1+…+xn−1)≧xnrn−1)xnxn{1−rn−1)}>W0

となり,Wが非増加であることに矛盾するからだ。

 こうして,蜘蛛の西最前線は(よってどの蜘蛛も)座標W0/{1−rn−1)}の点Mを超えて西に進むことはできないことが示された。

 余談だが,蜘蛛たちが西へ進みたい場合,西方向への動きばかりにこだわるのは実は賢明ではない。蜘蛛が3匹以上いるなら,真ん中近くにいる蜘蛛が東西両端の蜘蛛の助けを借りて,東西へ交互に跳ぶのがよいだろう。それほど技量がなくても,これを繰り返していれば,東西どちらの方向にも好きなだけ前線を進めることができる。そうしたうえで,最西端にいる蜘蛛に全員を引き寄せてもらえばいい。興味を持った読者には,この戦略の有効性を確かめていただきたい。

問題はこちらです