ロボット救出作戦

最近は災害現場でロボットの活躍が期待されている。というかもう活躍し始めているらしい。それを聞いて考えたのが、ロボットが途中で故障したらやっぱりロボットが救出に行くのだろうか、ということ。過酷な状況下では救出に行くロボットも故障するだろうから、一回の出動で救出出来ない場合もあるだろう。そんなことをあれこれ考えていたらちょっとしたパズルを思いついた。

(問題)
ある災害現場で、出動したロボット(No.0)が故障して止まってしまった。場所は出発点から距離Lの地点。ロボットには貴重な情報が入っているので別のロボットでけん引して回収したい。しかし、救出用ロボットもNo.0の所まで行って戻ってくるだけの堅牢さはなく、途中で故障してしまう。そこで、次々と救出用ロボットを繰り出して戻って来れるところまでけん引しては次のロボットに引き継ぐことにした(図1)。

図1 ロボットの救出方法

救出用ロボットNo.1は距離a(<2L)しか走れないが、幸いなことに途中で技術が向上し、No.2はNo.1のb倍、No.3はNo.2のさらにb倍…というように、走行距離を増やしていける。さて、No.0をけん引して出発点まで戻って来れるのは何台めのロボットか。

（答え)
ロボットNo.kの最終位置をx(k)とする。x(k)は漸化式で表すことができる。

x(k)=2・x(k-1)-a・b^(k-1)
x(0)=L

なんか面倒な形になったが、ちょっと書き下してみるとこの漸化式は簡単に解くことができることがわかる。(面倒な人はWolfram先生に聞いてね！）

x(0)=L
x(1)=2・L-a
x(2)=2・(2・L-a)-a・b
x(3)=2・(2・(2・L-a)-a・b)-a・b^2
…
x(k)=2^k・L-a・(2^(k-1)+b・2^(k-2)+…b^(k-1))

よって、等比級数の公式を使って、

x(k)=L・2^k-a・(2^k - b^k)/(2-b)

となることがわかる。ここで、x(n)=0となるようなnを求めると、

n=log((a+(b-2)・L)/a)/log(b/2)

を得る。(ただしnは整数だから小数部分を切り上げた値が答えになる)
なお、図2はL=1の時のnのグラフをWolfram先生に描いてもらったもの。

n=log((a+(b-2)・L)/a)/log(b/2)のグラフ。(ただしL=1)

…とまぁこんな感じ。別に意外な結果が出るわけではない。しいて言えば漸化式が簡単に解けるところが面白い。