# A lady and a monster

A famous problem: a lady is in the center of the circular lake and a monster is on the boundary of the lake. The speed of the monster is $v_m$, and the speed of the swimming lady is $v_l$. The goal of the lady is to come to the ground without meeting the monster, and the goal of the monster is to meet the lady.

Under some conditions on $v_m,v_l$ the lady can always win. What if these conditions are not satisfied?

Edited: the monster cannot swim.

If the conditions are not satisfied, then monster can always perform a strategy such that the lady will not escape the lake. On the other hand this strategy is not desirable for both of them because they do not reach their goals.

As there was mentioned, this deals with undecidability of the problem. On the other hand, if you imagine yourself to be this lady/monster, you can be interested in the strategy which is not optimal. What is it? If there are such strategies in the game theory?

Edited2: My question is more general in fact. If we have a game with one parameter $v$ when two players $P_1, P_2$ are enemies and if $v>0$ then for any strategy of $P_2$ the player $P_1$ wins.

If $v\leq 0$ then for any strategy of $P_2$ there is a strategy of $P_1$ such that $P_2$ does not win and vice versa. I am interested in this case. From the mathematical point of view as I have understood the problem is undecidable since there is no an ultimate strategy neither for $P_1$ nor for $P_2$. But we are solving somehow these problem IRL.

Imagine that you are a lady in this game - then you would like to win anyway even while knowing that your strategy can be covered by the strategy of the monster. On the other hand, the monster knows that if he will cover all strategies of the lady she will never reach the shore and he will never catch her. I mean they have to develop some non-optimal strategies. I hope now it's more clear.

-
I'm not sure I understand what you mean by "can always win". Unless you're saying that this is related to undecidability, it seems that this sort of game should be decidable and thus the only answer to "What if the conditions aren't such that the lady can always win" could be "Then the monster can always win." Don't you mean something like "Under some conditions the lady obviously wins. What if those conditions aren't satisfied?"? – joriki Apr 5 '11 at 13:36
I think you mean the speeds of the monster and lady are specified, not their velocities. – Rahul Apr 5 '11 at 13:38
I dont get it, there is no degree of optimality in solutions, the lady either dies, wins, or stays inside forever. Total 3 possible outcomes. What is the question? – TROLLKILLER Apr 5 '11 at 15:31
@Gortaur Well if she cant win (get to the shore without dying) she can do whatever she wants aslong as shes inside the lake, like fishing, but its no more a math question. The question is, can she get to the shore without dying if the monster follows the optimal strategy? Its a yes/no question, there is no intermediate case – TROLLKILLER Apr 5 '11 at 15:40
Maybe the lady and the monster can agree that the monster lets the lady escape and live for 10 more years at which point the lady comes back to the lake and scarifies herself? – Fabian Apr 5 '11 at 15:56

Since you seem to know the answer, I will give it here.

Suppose that $v_l = v_m / k$ and the radius of the lake is $r$. Then the lady can reach a distance $\frac{r}{k}$ from the centre and keep the monster directly behind her, a distance $r\left(1 + \frac{1}{k}\right)$ away. One way would be to swim in a spiral gradually edging outwards as the monster runs trying to close the distance; another would be to swim in a semi-circle of radius $\frac{r}{2k}$ away from the monster once it starts to run. And the lady can sustain this distance by going round in a circle as the monster tries in vain to close the distance.

The next stage is for the lady to try to swim direct to shore at some point away from the direction the monster is running. If the monster starts at the point $(-r,0)$ running anti-clockwise and the lady starts at the point $\left(\frac{r}{k},0\right)$ her best strategy is to head off in a straight line initially at right angles to the line between her and the monster: a less steep angle and the monster has proportionately less far to run than the lady has to swim, but a steeper angle and it is worth the monster changing direction. (If the monster changes direction in this right-angle case, the lady changes too but now starts closer to shore.) As they are both trying to get to the point $\left(\frac{r}{k},r \sqrt{1-\frac{1}{k^2}}\right)$ then they will arrive at the same time if $\pi + \cos^{-1}(1/k) = k \sqrt{1 -1/k^2}$ which by numerical methods gives $k \approx 4.6033$.

So if the monster is less than 4.6033 times as fast as the lady, the lady can escape; if not then she stays in the lake and the monster stays on the edge and they live unhappily ever after.

-
Nice. The surprising part is that the lady can't do any better than stay on the same straight line even after the monster can no longer change direction -- I checked that explicitly by taking the derivatives, but is there an easier way to see it? – joriki Apr 5 '11 at 18:36
Put in a different way: Why do the direction a) in which she initially has to swim to keep the monster opposite her and the direction b) in which she has to swim to maximize the time difference between her arrival and the monster's, assuming the moster doesn't change direction, coincide? It seems like a coincidence; do you see a deeper reason for this? – joriki Apr 5 '11 at 19:15
@joriki : The obvious answer would be by symmetry. But I'm (wildly) guessing Brouwer will come up somewhere :) – yatima2975 Apr 5 '11 at 20:28
@yatima: I don't see the symmetry. – joriki Apr 5 '11 at 20:33
@Henry: See my comment under @user8268's answer for the explanation of the supposed discrepancy between the two answers. The answer from your method is actually $4.6033$ (with the $0$ and $6$ swapped). – joriki Apr 5 '11 at 21:05

edit: I corrected a silly mistake, now I get the same answer as Henry.

Let $k=v_m/v_l$. We can suppose $v_l=1$, hence $v_m=k$, and that the radius of the lake is 1. Let's reformulate the problem in this way: lady swims as before, but monster stands still and turns the lake with speed $\leq k$. The (vector) speed of the lady is a point in a disc of radius $1$, and the monster can control the center of the disc - he can move it from $0$ in the tangent direction by at most $kr$, where $r$ is the distance of the lady from the center.

If $r<1/k$ then $0$ is inside the disc, so the monster has no control over the direction of lady's movement. She can therefore get to $r=1/k$ to the point away from monster.

When $r>1/k$ then $0$ is no longer in the disc and the monster can force (by turning at full speed) the constraint $|dr/d\phi|\leq r/\sqrt{k^2r^2-1}$ (where $\phi$ is the angle of the position of the lady). The question is whether she can get from $r=1/k$, $\phi=0$, to $r=1$, $\phi<\pi$ ($r=1$, $\phi=\pi$ is the position of monster). This is possible iff $\int_{1/k}^1 \sqrt{k^2-r^{-2}}\, dr <\pi$.

edit: Here is why $|dr/d\phi|\leq r/\sqrt{k^2r^2-1}$ (it's a bit difficult to explain without a picture, but I'll try). The possible speeds of the lady form a disc with the center at $(0,kr)$ and with the radius $1$. The speed with the largest slope is the point of tangency from $0$ to the circle. Its slope can be seen from the right-angled triangle, with hypotenuse $kr$ and two other sides $1$ and $\sqrt{(kr)^2-1}$ - so the slope is $1/\sqrt{(kr)^2-1}$.

-
Wow, this did get quite interesting after all! I thought I'd checked Henry's answer; now I'm quite keen to see who turns out to be right... – joriki Apr 5 '11 at 19:58
@user8268: You seem to be missing a factor $r$ in your calculation of the constraint for $\mathrm{d}r/\mathrm{d}\phi$? However, that doesn't quite bring your result into agreement with Henry's, so it may just be a mistake on my part. – joriki Apr 5 '11 at 20:50
I take that back -- Henry just happened to switch two digits in his answer -- the correct answer from his method is 4.6033, and that's also what you get from your method if you include the factor of $r$. That yields $\int_{1/k}^1\sqrt{k^2-1/r^2}\mathrm{d}r=\sqrt{k^2-1}+\arctan(1/\sqrt{k^2-1})-\p‌​i/2<\pi$. – joriki Apr 5 '11 at 21:04
@joriki: I added a comment why the constraint is as I claimed - is it wrong? – user8268 Apr 5 '11 at 21:21
Yes, it's wrong -- the slope is correct, but $\mathrm{d}r/\mathrm{d}\phi$ is $r$ times that slope. $dr/d\phi=r dx/dy$. – joriki Apr 5 '11 at 21:28

I don't see that there is any game theory to be done here.

For the lady to have a winning strategy means that there exists a legal lady path $\gamma_l$, which reaches the shore, such that for all legal monster paths $\gamma_m$, a monster following path $\gamma_m$ does not catch the lady.

For any choice of $v_l$ and $v_m$, either the lady has a winning strategy or she doesn't, and it sounds like you know how to find out which is which. If she doesn't, then inverting the quantifiers, for every legal lady path which reaches the shore there exists a monster path which catches it. So in this case she cannot reach the shore without being caught.

However, the lady can always force a draw by not reaching the shore.

-
In principle the lady can wait until the monster falls asleep and then sneak out. Alternatively, the monster can take swimming lessons and catch the lady inside the lake. – Fabian Apr 5 '11 at 16:04
@Fabian: +1 for thinking beyond the pond – joriki Apr 5 '11 at 16:08
@joriki: thank you. When the question started out I thought I might be interesting. After all the edits, it looks like the OP wants us to think beyond the pond (and therefore it seems unsuitable for a math forum). – Fabian Apr 5 '11 at 16:11

The monster can know if he can win or not at any time, likwise the lady.
They can't agree to enter a phase where the probability that either wins is something other than 0% or 100%.

If the lady can't win, so the monster won't win if she stays in the lake, they can toss a coin to determine her faith.

-
Thank you all for your effort and nice comments. I voted for all answers since all of them are helpful - on the other hand, this answer helped me to find an answer on my question. Indeed, in the current state the problem cannot be solved even using real-life principles - the formulation of the problem should be changed - so I ask you to continue the discussion here math.stackexchange.com/questions/31284/…. – Ilya Apr 6 '11 at 6:47

I was thinking about this problem and it seems to me that in a given formulation this game is somehow equaivalent to the following game.

If $v_m/v_l>k$ then on any action of the lady monster can either move (M) and follow her an catch her if she will come to the shore or stay (S) on the same place and wait (and thus let the lady run away). The lady also has to possibilities - either to move (M) and get out of the lake - or to stay (S) always inside the lake.

From these arguments it's easy to see that M is a dominating strategy for the monster (if we don't consider a penalty for the moving), hence it's optimal for the monster to follow the lady. Hence the lady on her side have to stay inside the lake.

For a pair (Lady, Monster) if $v_m/v_l>k$ there is a Nash equilibrium (Stay, Move).

-