円形の池の周りに鬼がいて、池の中心にＡさんがいて、鬼に捕まらずに逃げるには？

質問

半径 R の円形の池があり、中心にＡさんがいます。
Ａさんは一定の速度 v で泳げます。
池の周りには鬼がいて、速度 V で池の周囲のみを走ることができます。
鬼は可能な限りＡさんを捕まえようと最善の方法で走ります。
Ａさんは可能な限り鬼に捕まらないように池の外に最善の方法で出ようとします。
（鬼の位置によって進む方向を変えてもかまいません。）

このとき、
　(1) Ａさんの泳ぐ速度が鬼の何倍以上なら
　　　　Ａさんは鬼に捕まらずに池の外に出ることができるでしょうか？
　　　　その場合の戦略はどのようなものでしょうか？
　(2) Ａさんの速度が v で鬼の速度が V であるとき、
　　　　どのような戦略をとれば、最短時間で逃げられるでしょうか？
　(3) Ａさんの速度が v で鬼の速度が V であるとき、
　　　　どのような戦略をとれば、
　　　　鬼より最も離れたところで陸に上がることができるでしょうか？

実は、この質問はあるサイトの質問を少し変えたものです。
そのサイトでは、回答期限が１週間以内であるという重大な欠点があり、
だれも満足のいく回答を示すことはできませんでした。
そこで、回答の時間制限がなく、かつ閲覧者も多く、
優秀な回答者も多そうなこのサイトに投稿することにしました。

私も解いてみたのですが、計算・実験等してみたところ、
(1) については、おそらくＡさんが逃げ切れる速度の上限は v/V = 0.218 程度だと思います。
(3) は、もう少しで解けそうな気もします。
(2) は、解ける見通しが立っていません。

また、上記の質問は、ビルゲイツの面接試験問題
http://pitecan.com/Mixi/diary/2319810.html
http://pitecan.com/Puzzle/devil/
の条件を少し変えたものでもあるようです。
（これが元ネタかもしれません）

難問かもしれませんが、回答、もしくはヒント等頂ければ助かります。
解くには時間がかかるかもしれませんので、
その場合は「考え中です」とでも回答して頂ければよいと思います。

なお、他のＱ＆Ａサイトへリンクを貼る等、
「他のサイトへの誘導およびやりとりを促し当サイトへの営業妨害に繋がる恐れのある記述」
をすることはご遠慮下さい。回答を削除されてしまいます。
また、画像をどこかにアップロードしてリンクを貼るのも禁止事項のようです。
http://service.okwave.jp/cs/prohibition/
http://okwave.jp/qa3162570.html
http://okwave.jp/qa3289973.html
をご覧下さい。

回答No.9

montmort

No.8です．まだこのサイトの使い方がわかっていません．
＞結果として直線の戦略が最適だった、
＞という方法のほうがいいと思います。
はい，結果的にkts2371148さんの戦略が正しかったといえると思います．
きちっと検算をしていませんが，直線の方程式が，変分法のオイラーの方程式も満たすようです．
そもそも直線で行けるところをわざわざ曲線にこだわった私が愚かでした．

●前半の軌道について．
簡単のため，池の半径は１，鬼の速度は１，Aさんは速度ｖで泳ぐとします．
鬼は極座標（１,-π）にいて左周りに追いかけます．
Aさんは最初（0，0）に位置し，常に鬼から反対側つまりπだけ離れるようにつとめ，なおかつ外に向かって泳ぎます．
Aさんの位置を極座標（r,θ）とすると，
ｄθ/dt＝１，√（ｒ^２＋（dr/dt）^２)=v
という微分方程式が成り立ち，これを解くと，
v*sin(θ）＝r
となりこれは円をあらわします．（中心，(v/2,π/２），半径ｖ/２）
鬼はπ/2秒後に（１,-π/２），Aさんは（ｖ，π/２）（全て極座標）にいます．

●　鬼が途中で反対方向に走ったとき．
まず，前半が終わった時点，つまり，後半の始まりの時点で鬼が反転した場合は，Aさんは反対向きに同じ戦略をとればいいです．

後半の途中で鬼が反転した場合はAさんにとってはラッキーです．その時点でAさんは選択の幅が増えます．ぎりぎりの状況らら逃れられるからです．手っ取り早い方法は鬼がπだけ離れるまでそのまま進めばいいです．πだけ離れたときに次の戦略を考えればいいわけです．その際も選択の幅は広いです．楽に鬼から逃げれます．

これから(2)について考えようと思います．やはり円弧の一部+直線が自然でしょうね．

お礼

回答ありがとうございます。
おかげ様で、かなり理解できました。

>> そもそも直線で行けるところをわざわざ曲線にこだわった私が愚かでした．

私が書いたのは、決してそのような意味ではなかったのですが…
私が思ったのは、最適なルートが曲線ではなく直線であることを
何らかの仕方で証明する必要があるはずだ、
そのためには、
　曲線では最適にならないことを証明する
　montmortさんのように、あらゆる状況を想定して計算してみる
のどちらかが必要だと思うのです。
No.1～7の皆さんはそのどちらもされていないようなので、
montmortさんのようなアプローチも必要ではないか、と思ったのです。

と、ここまで書いたところで、No.5さんの回答に
>> r圏内に入らず、鬼が前方に来ない限り鬼は一方向に進むので、
>> その間に最も長い距離を進めるコースは直線。
と書いてあることに気づきました…
でも、montmortさんのようなアプローチも決して愚かではないと思います。

後半の戦略についてですが、鬼が途中で反対方向に走ったとき、
>> 手っ取り早い方法は鬼がπだけ離れるまでそのまま進めばいいです．
これでやっと納得できました。
ありがとうございます。

実は今、鬼が最適でない戦略をとったときに、
その隙をついて最終的な鬼からの距離を最大限離すためには
どうしたらよいかを考え中です。
皆さんの答えを少しいじるだけでできそうな気もしますが、
実は、曲線の可能性も想定して解いている途中です。
やっぱり直線になるだろうな、と思いつつ、
解く過程が (2) へのヒントになることを期待しているところです。

補足

（この問題に回答してくださった皆さんにお伝えしたいので、
　ここに書かせて頂きます。）

今までの皆さんの回答やmontmortさんの回答のおかげで、
皆さんがすでに (3) を完全に解いていることがやっと理解できました。
（本当はもっと早く理解すべきだったと思うのですが…）

それで、(2) に移りたいと思います。
ただ、ここまでが長くなりましたので、
いったん締め切って新しく質問した方がよいとお考えの方は、
その旨お伝えください。