6号館自転車探索問題

自転車をどこにとめたか毎回忘れてしまう人がいたので定式化してみた．

簡単のため，1次元で考えることにする．
6号館の玄関は[-1,1]の位置を占めていて，自転車を停めることができるのは[-M,-1]∪[1,M]であるとする．
このとき，t君は原点から出発して移動をし，
自転車の存在する位置x∈[-M,-1]∪[1,M]に到達すれば自転車を発見することができる．
t君が自転車をみつけるまでに移動した道程をL(x)とする．

t君は忘れっぽいので，自転車を停めた位置xについての情報は何ももっていないものとする．
このとき，

ρ=sup_{x∈[-M,-1]∪[1,M]} L(x)/|x|

を最小化するようなアルゴリズム（移動経路）を考えたい．

例えば，0->M->-Mと移動するアルゴリズムの場合，
x=-1のとき最大値ρ=2M+1となる．
Mが小さいときはこれが最適であるが，大きい場合は別のアルゴリズムが最適となる．
どのようなアルゴリズム最適となるか？

ρはMによらない定数でおさえられるはず．
randomizedにすればρの値はさらに小さくできる．