22
$\begingroup$

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.

$\endgroup$
22
  • 2
    $\begingroup$ I think you mean the speeds of the monster and lady are specified, not their velocities. $\endgroup$
    – user856
    Commented Apr 5, 2011 at 13:38
  • 3
    $\begingroup$ 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? $\endgroup$
    – TROLLHUNTER
    Commented Apr 5, 2011 at 15:31
  • 3
    $\begingroup$ @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 $\endgroup$
    – TROLLHUNTER
    Commented Apr 5, 2011 at 15:40
  • 3
    $\begingroup$ 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? $\endgroup$
    – Fabian
    Commented Apr 5, 2011 at 15:56
  • 2
    $\begingroup$ @joriki: me too! The correct ordering of letters was never my strength (there are $n!$ combinations of a word of length $n$ which looks rather sacry);-) $\endgroup$
    – Fabian
    Commented Apr 5, 2011 at 16:14

8 Answers 8

Reset to default
22
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – joriki
    Commented Apr 5, 2011 at 18:36
  • 1
    $\begingroup$ 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? $\endgroup$
    – joriki
    Commented Apr 5, 2011 at 19:15
  • $\begingroup$ @joriki : The obvious answer would be by symmetry. But I'm (wildly) guessing Brouwer will come up somewhere :) $\endgroup$
    – yatima2975
    Commented Apr 5, 2011 at 20:28
  • $\begingroup$ @yatima: I don't see the symmetry. $\endgroup$
    – joriki
    Commented Apr 5, 2011 at 20:33
  • 1
    $\begingroup$ @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). $\endgroup$
    – joriki
    Commented Apr 5, 2011 at 21:05
9
$\begingroup$

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}$.

$\endgroup$
7
  • $\begingroup$ 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... $\endgroup$
    – joriki
    Commented Apr 5, 2011 at 19:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – joriki
    Commented Apr 5, 2011 at 20:50
  • 1
    $\begingroup$ 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})-\pi/2<\pi$. $\endgroup$
    – joriki
    Commented Apr 5, 2011 at 21:04
  • $\begingroup$ @joriki: I added a comment why the constraint is as I claimed - is it wrong? $\endgroup$
    – user8268
    Commented Apr 5, 2011 at 21:21
  • 1
    $\begingroup$ 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$. $\endgroup$
    – joriki
    Commented Apr 5, 2011 at 21:28
5
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – Fabian
    Commented Apr 5, 2011 at 16:04
  • 1
    $\begingroup$ @Fabian: +1 for thinking beyond the pond $\endgroup$
    – joriki
    Commented Apr 5, 2011 at 16:08
  • $\begingroup$ @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). $\endgroup$
    – Fabian
    Commented Apr 5, 2011 at 16:11
2
+250
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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/…. $\endgroup$
    – SBF
    Commented Apr 6, 2011 at 6:47
2
$\begingroup$

This is my first answer on this site. I don't know how to format it beautiful yet. Sorry for the inconvenience. The solution provided by Henry seems plausible.

  1. Why the first statement is true? "the lady can reach a distance $\frac{r}{k}$ from the centre and keep the monster directly behind her, a distance $r(1+\frac{1}{k})$ away. "
    I know that the result is given by the equation, $$\frac{\frac{r}{k}*\theta}{1} = \frac{r*\theta}{k}$$ which means the angle they go are the same. But still, it is a little bit ambiguous to me.

  2. If we take the first argument as granted, the second choice is how the lady swim to the shore. The answer provided by Henry has two implicit assumptions, 1. the monster cannot change direction 2. right-angle , therefore, he comes up with the equation $$ \pi + \cos^{-1}(1/k) = k\sqrt{1-1/k^2}$$ The thing is, if the lady wants to fool the monster, and once monster starts to run, the lady changes the direction and monster still runs the same direction, the equation above is correct. But if the monster is a rational animal, it will change direction too (all happens in a very short time, otherwise the equation cannot hold).
    Also, why right angle? As assumed, they meet at the shore, the meeting point to the center is angle $\alpha$, I come up with the equation (use Law of cosines) below $$\frac{\sqrt{(r/k)^2+r^2-2r(r/k)\cos{\alpha}}}{1}=\frac{(\pi-\alpha)r}{k}$$ If I choose $\alpha = \cos^{-1}(1/k)$ and change $\pi-\alpha$ to $\pi + \alpha$, I will have the same equation as $$ \pi + \cos^{-1}(1/k) = k\sqrt{1-1/k^2}$$ So it is a function between $\alpha$ and k. It is not any trajectory problem, so we can expect when lady choose go straight, the distance is shortest, and it is the fastest routine. Rearrange the terms, we solve the quadratic equation to get the expression of $k$ as $$k=\cos{\alpha}+\sqrt{\cos^2{\alpha}-1+(\pi-\alpha)^2}$$ It is easy to prove and use python to visualize that it is a decreasing function of $\alpha$, so the max $k$ is achieved when $\alpha=0$, and $k_{max}=1+\pi\approx 4.142$

$\endgroup$
1
$\begingroup$

This actually seems like a plus sum game. If the lady escapes, she gains something. But the monster doesn't actually lose anything as he only loses the option to try to eat the lady and that option can never succeed.

If the lady wins, the monster loses nothing. However, for the lady getting eaten is not the same staying forever. If the monster wins, she loses. If the lady loses by staying forever, the monster gains nothing. If the monster loses, the lady wins.

If the lady values her life more than freedom it is a plus sum game to let her leave.

So if they have some money or other currency that both value she can pay the monster to leave. As the monster will never get to eat her anyways, it can't trick a rational actor to pay her again, because he has proven he will cheat so leaving and staying are equivalent options once he has been paid. So he might also leave. Also, the monster cannot pay the lady to be eaten because she wouldn't be alive to spend the money.

If there is a reputation somehow, then it is +ev for the monster to honor the agreement. For example if there is a chance they might end up in a similar situation again, if he honors the deal now then he will get a similar deal next time while breaking the deal gains him nothing.

If the monster only cares about food the lady can chop off a hand and feed it to monster as a payment.

$\endgroup$
0
$\begingroup$

In the case where the lady cannot escape, they seem to stay in a sub-optimal for both Nash equilibrium: the lady won't exit the lake, and the monster will not leave its shores as long as the lady is in because then he would get nothing at all.

Game theoretically speaking, (disclaimer: Imho...) it is very difficult to just decide the matter by themselves. Say they decide to toss a coin for it. The first problem would be that they would never agree to the proper odds for the toss. The second problem is that whoever lost from the coin toss would just not keep his world. If the lady losses, she will have to choose between keeping her word to a disgusting, uncivilized monster, or die by being eaten alive. And we all know monsters only keep their word on Disney movies (and even then not always).

One way to solve the fist problem is to say they agree to 50%, but this makes no sense, the lady risks her life, while the monster a dinner... To solve the second problem, they might decide to break it to an infinite set of moves, where each move only increases slightly the chance of the lady escaping. The problem is that supposing perfect knowledge, this cannot happen, for each state the lady either escapes or not. (Note in the real world the game has noise, things are a bit fuzzy, e.g. we have estimations and could in fact imagine such a game exists)

The solution would be to have some external force i.e. a king improve the situation ordering the lady to exit and be eaten by the monster, or the monster leave the lake. Alternatively he could have the lady exit, but pay tribute the monster for life. Of course he could also kill the monster to use as tapestry and "marry" the lady, since they stupidly gave him power over them all.

$\endgroup$
-1
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .