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

Question

半径 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
をご覧下さい。

age_momo · Accepted Answer

少し考えてみました。それぞれの速度を1、θとしても円の半径をRとして
ある限り一般性を失わないのでこれで書いてみます。

まず、円の中心から鬼と反対側に泳ぎだします。それに対して鬼はどちらでも
同じなので反時計回りに回り始めるとします。Aさんはこの動きに対して絶えず
円の中心が間に来るように方向を変えながら泳ぎます。螺旋に似た動きに
なります。理論的には無限大の時間が必要になりますが、いずれAさんは
反時計回りに半径θRの円を描いて泳ぐことになります。この泳ぎをしている
間は鬼に対して円の中心を挟んで反対側で最も遠いところにいますので
ポジションとしては最適なのは間違いないと思います。よって、時間のfactorが
ない(1),(3)に関してはここから考えることになると思います。

原点を中心とする半径Rの円を考えてある時間にAさんが(θR,0)鬼が(-R,0)に
いてこの時にAさんが行動を開始したとします。
行動の仕方は(R,0)から(θR,R√(1-θ^2))のどこかに直線的に逃げることになります。
今、(R,0)に向けて真っ直ぐに逃げると#4さんの回答になると思いますが、
最適かどうかを考えるために(Rcosω,Rsinω)に向けて逃げ出したと考えると
その点にAさんが到着する時間と鬼が到達する時間の差の関数
f(ω)=1/θ*√{(Rcosω-θR)^2+(Rsinω)^2}-R(π+ω)
=R/θ*√(1+θ^2-2θcosω)-R(π+ω)

ωで微分して増減を調べれば分かりますが、
0≦ω≦arccosθ
の範囲内で単純減少であり、ω=arccosθつまり、(θR,0)から真上に
逃げることが最も良いことになります。

これ以上の左は考えません。理由は二つあります。
・半径θRの円の内部を通ることになり、無駄が出る。
・内部に向かう⇔鬼の進行方向から反対側に出ることになるので
鬼が反転して回って来る。

なお、(θR,0)から真上に逃げた場合、鬼は反転しません。
なぜならばAさんが鬼と中心を結んだ線上にいるためには
θRの円を描いて泳ぐ必要がありますが、これから離れた瞬間から
絶えずAさんは鬼の進行方向に近いところにいます。
仮に鬼が反転すればそれにあわせてAさんも向きを変えれば
より有利になりますから題意から鬼が反転することはありません。
(θRの円から出た瞬間からAさんが鬼の進行方向の反対側に行くことは
できません)

Aさんの脱出をθRの円の接線方向と決定するとそれぞれの時間の差の
関数は

g(θ)=R/θ*√(1-θ^2)-R(π+ω)

となり、これが0になるθをnewton法で数値的に求めると

θ≒0.2172336282112216574082793

となりました。

montmort · Answer

No.8,9です．
＞実は今、鬼が最適でない戦略をとったときに、
＞その隙をついて最終的な鬼からの距離を最大限離すためには
＞どうしたらよいかを考え中です。
そうですよね．とりあえずそのまま進むっていうのは数学的にルーズですから，最適解を出すのは自然ですね．

＞ただ、ここまでが長くなりましたので、
＞いったん締め切って新しく質問した方がよいとお考えの方は、
＞その旨お伝えください。
確かに長くなりましたね．新しく質問しなおしたほうがいいかもしれませんが，ちょうど(2)が解けたので書いてもいいですか？

簡単のため池を単位円,鬼の角速度を1としてあります．
前半を，やはり中心が(v/2,π/2)で半径v/２の円に沿って逃げ，後半をこの円の接線上を逃げ，ちょうど鬼に捕まる条件を求める．前半から後半に移る時点のAさんの位置をP(r,θ)とする．その位置は，P(v*sinθ，θ）と表わせる．またAさんが最終的に池のたどり着く地点をQ(1,θ+φ) とする．△OPQにおいて∠QOP=φ,∠OPQ=π-θである．よって，
 ∠PQO=θ-φ
である．また，OP=vsinθ,OQ=1である．PQ=kとすると，△OPQにおいて正弦定理を適用し，
1/sin(π-θ）=visnθ/sin(θ-φ）=ｋ/sinφ…(2)
また，求める条件は，
π+φ=k/ｖ …(3)
であるから，これらからφ，kを消去する．
(2)より，
sin(θ-φ）=vsin^2（θ）
よって，
φ=θ-arcsin（visn~2（θ）） 
また，k=sinφ/sinθ=sin（θ-arcsin（vsin^2(θ)）/sinθ であるから，(3)は，
π＋θ-arcsin（vsin^2(θ)）＝sin（θ-arcsin（vsin^2（θ））/（vsinθ）
これを満たすθだけ前半小円上を動き，その後その円の接線上を行けばちょうど鬼にぶつかりますから，ちょっとθをふやせば鬼から逃げれます．
ただし，この方程式の解が意味をもつのは
0.21723362821122165＜v＜1/π
です．
それより小さいと，鬼につかまります．
大きいと，最初から直線で逃げます．

この戦略が最適という自信はありません．検討をお願いします．

montmort · Answer

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 · Answer

質問者さんとともに別サイトから移動してきました．このサイトの登録に手間取っていました．
ここまでの私の経過は変分法を用いてアプローチするというものでしたが，見当違いでした．後半Aは直線ではなく曲線で泳ぐという前提で話を進めてきました．しかし，それは大きく遠回りをして結局kts2371148さんの答えにたどり着くという結果になり，それは直線となりました．
また，v/V>0.217233628211221となり，ktsさんの答えと一致しました．
１）Aは池の中心を通り直径の長さがRv/Vの円上を逃げる．最初の瞬間の方向は鬼と反対の方向．鬼が方向を変えない限りこの運動を続ける．方向を変えた場合は同時に鬼と自分を結ぶ直線について対称な軌跡上をたどる．この間，終始Aと鬼は中心を挟んで反対側にいる．最終的に池の中心からRv/Vだけ離れた位置にたどり着く．鬼はやはり反対側にいる．
ここまでを前半とする．
後半は，池の中心を中心とし，半径Rv/Vの円に接する直線状を逃げる．方向はどちらでもいいが，今まで泳いできた方向と同じほうが自然であろう．この途中鬼は追う方向を変えることは鬼にとって最善ではないが，ちょうど鬼が反対側に行ったところでAは切り返せば問題ない．
Arccos（v/V)＋π＝√（（V/v)^2－１）を満たすｖ/Vでちょうどつかまるので，それより速い速度が必要．
3）は本質的に(1)と同様の問題と思われ，前半を半円弧，後半を直線という考え方でいいと思います．
2)についてもやはり前半と後半で考えるのがいいと思いますが，ひょっとしてこの問題に関しては汎関数の入り込む余地があるかも知れないと思っています．ちょっと未練がましい．

SortaNerd · Answer

No5です。
ああ…微分か。判別式からどうするんだっけとかずっとやってた。
自分の数学力(特に微積力)のなさが恨めしい…。

で、反対側から回った方が早いということについてですが、それは結果論です。
No6さんも書いていますが、
r(No6さんの書き方ではθR)地点から進む時に、仮に鬼が反対に回りだしたらその瞬間人も反対に回ればいいのです。
また、それ以降には、各時刻において鬼と人の場所を考えて見れば分かりますが、鬼と人の間の中心角は常に180度未満ですから反転はあり得ません。
rの外側では人は鬼より速い角速度で動くことはできませんから。

ちなみに答えは幾何的に考えると、r地点と上陸地点の間の中心角をθとして(No5のθと同じ。No6さんのθとは別)、
Rsinθ=R・v/V・(π-θ)
となり、v/VをWとおいて書き換えると
√(1-W^2)=W・(π-acosW)
acosW=π-√(1-W^2)/W
W=cos{π-√(1-W^2)/W}
となり、三角関数力もない自分にはこれ以上変形できないのですが、厳密解も求められそうな予感がします。

さてこれで(1)がとけたと同時に(3)も多分解けていますね。あとは(2)ですか。

SortaNerd · Answer

まだ解けていませんが解き方は分かりました。

No3,4さんのrを使って、
rだけ進んだ地点から斜めに一直線に進んで、半径方向に進んだ場合より池の中心を基準にθだけ離れた所に着くための時間は、
√{ (Rsinθ)^2 + (r-Rcosθ)^2 }/v
それまでに鬼が進む時間は
(2π+θ)V
となります。
あとはどうにかすれば最適解が求められそう。

ちなみに、これで最適解が求められる証明は、
ある地点において、
・鬼は離れているほど良い
・岸に近いほど良い
ので、鬼を反対側に保ってrのところまで進むのは明らかに最適。
そこから先は、
・途中でr圏内に入れば振り出しに戻るので考えない。
・途中で鬼が前方に来ればもう間に合わないので考えない。
r圏内に入らず、鬼が前方に来ない限り鬼は一方向に進むので、その間に最も長い距離を進めるコースは直線。
でいいと思います。

なお、本当に一直線に進むと鬼が反対から回ってきますので、最初に反対側に無限小の距離だけ進みます。

syouji_08 · Answer

#3です。
間違いではないと思いますが、少し冗長な考え方をしている部分があったので訂正します。

＞(3)については、

Ｒ、Ａ、Ｖはそれぞれ条件を満たすように固定されているものとし、
半径ｒの地点で着地目標地点に対して鬼のいる反対側の位置になるまで周回を近づける事が前提となり、その上で、（Ｒ－ｒ）/ＡＶを最小とするようにｒを定める事だと思います。
すなわち(5)より、ｒはＲＡ（＝Ｒ×（ｖ/Ｖ））に限りなく近い値に設定すれば良いと思われます

（Ｒ－ｒ）/ＡＶが最小であるという捉え方をするよりも、
単純に（Ｒ－ｒ）が最小であると捉えるべきだと思われました。
少々補足しておきますと、Ｒ－ｒの距離が小さければ、Ａが陸に着くまでにかかる時間がより少なくなり、その間に鬼が追いかけて進む距離も小さくなるので、結果として、鬼はＡが着地した地点から最も離れる事になるかと思います。

syouji_08 · Answer

(1)についてですが、
特に、（鬼が半周する時間）＜（Ａが距離Ｒだけ真っ直ぐに進む時間）の場合に、魔の手から確実に逃れられるための戦略としては以下のようになるかと思います。

「Ａが池の中心から半径ｒだけ進み、そこで、着地する目標位置と鬼の位置とが離れるように周回しつつ調整します。あるところまで離れれば（最大１８０度まである）即、Ａは陸地を目指して直進します。」

この戦略で逃げられるケースが存在するための必要十分条件は以下の２項目を満たしたときである。

(1)半径ｒだけ離れた箇所において、（Ａが１周する時間）＜（鬼が１周する時間）とならなければならない。

(2)半径ｒの位置から直進して陸に向かうケースでは、（ＡがＲ－ｒだけ進む時間）＞（鬼が半周する時間）とならなければならない。

この２条件さえ満たせばこの戦略で確実に逃げる事が可能です。
ｖ/Ｖ＝Ａとおくと、

(1)より、

（２πｒ）/（ＡＶ）＜２πＲ/（Ｖ）
ｒ/Ａ＞Ｒ
ｒ＜ＲＡ---(3)

(2)より、

（Ｒ－ｒ）/ＡＶ ＜　（πＲ）/Ｖ
（Ｒ－ｒ）/Ａ ＜　πＲ
（Ｒ－ｒ）＜πＲＡ
Ｒ（１－πＡ）＜ｒ---(4)

(3)(4)より、

Ｒ（１－πＡ）＜ｒ＜ＲＡ---(5)
(5)の不等式を満たすためには、
Ｒ（１－πＡ）＜ＲＡ---(6)
厳密には、０≦Ｒ（１－πＡ）＜ＲＡ ≦ Ｒ--(7)
まず(6)を解くと

A >１/(π＋1)--(8)

(7)を解くと、(1/π) ≧ A > 1/(π+1)となるが、
1/π < Aの場合はこの戦略を用いなくても、池の中心から、ただ鬼がいる反対側の方向に直進して逃げればよい。そういう意味では確実に逃げられるための必要十分条件は(8)のみで良いと思われる。

(3)については、

Ｒ、Ａ、Ｖはそれぞれ条件を満たすように固定されているものとし、
半径ｒの地点で着地目標地点に対して鬼のいる反対側の位置になるまで周回を近づける事が前提となり、その上で、（Ｒ－ｒ）/ＡＶを最小とするようにｒを定める事だと思います。
すなわち(5)より、ｒはＲＡ（＝Ｒ×（ｖ/Ｖ））に限りなく近い値に設定すれば良いと思われます。

(2)については、

結局Ａは（半径Ｒ）＋（半径ｒの時点で何度か周回する距離）だけ進むことになる。なので、ｒの位置で周回する際に出来る限り早く鬼の反対側に来て、直進出来るように実現すれば良いと思われます。よって、ｒを出来る限り小さくするように設定すればよいと思います。
すなわち(5)より、ｒ　＞　Ｒ（１ーπＡ）＝Ｒ（１－π（ｖ/Ｖ））となる事からｒをＲ（１－πＡ）よりも出来る限り近い値に設定すればよいかと思われます。

BONUSU · Answer

余計なお世話ですが、ご質問の内容が不完全ですよ。
ご記述の内容だけ見るとｖ＞Ｖであれば簡単に逃げることが出来てしまいます。

Ａさんは岸に向かってまっすぐ進み、
岸の直前で岸に沿って方向を替え、鬼から離れたところで岸に上がればよいのですから…

でもリンク先をみて
こりゃぁ手に負えない難問とわかりましたｗ
ご検討を祈ります。

noname#58440 · Answer

私なら潜って川の底をひっそりと出ていきます。
池の周囲を回ってる鬼には見つからないと思います、見つからない為にもゆっくり泳ぐ方が良いと思います。

あるいは、泳がずに岸から手の届かない場所でジッ～っと待って鬼が池の反対に行った時に急いで池から出て行きます。

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

少し考えてみました。

No.8,9です．

この回答への補足

No.8です．まだこのサイトの使い方がわかっていません．

この回答への補足

質問者さんとともに別サイトから移動してきました．このサイトの登録に手間取っていました．

No5です。

この回答への補足

まだ解けていませんが解き方は分かりました。

#3です。

(1)についてですが、

余計なお世話ですが、ご質問の内容が不完全ですよ。

この回答への補足

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング