Once more with the Maiden

[bonanova]

Previously, Maiden’s boat could change its heading instantaneously. Ogre’s heading could change only by virtue of following a circular path along the shore at his current speed. His rotational speed was thus far from infinite, and perhaps that disadvantage was unfair.

So in this final puzzle iteration we’ll limit the boat’s linear speed to be f times that of Ogre, as before, but now we’ll also limit the boat’s angular speed to be never greater than g times Ogre’s top angular speed.

A moment’s thought tells us that unless g is greater than unity the boat’s best strategy is to run at full speed from the center to the shore, keeping its initial bearing, no matter where on the shore Ogre initially stands. That is, never to turn the boat. That sucks for Maiden (e.g., she loses if Ogre initially stands at the boat's initial heading) and it sucks as a puzzle. So we’ll say the boat can change heading faster than Ogre can. For clarity we’ll set g = 2.

We’ll implement that limit by giving the boat’s motor three discrete settings that can be switched instantly an unlimited number of times: clockwise (CW), full speed ahead (FSA), and counterclockwise (CCW.) In the two turning modes the boat turns but maintains its position; in FSA mode it moves forward but does not turn. Boat’s path is thus a succession of arbitrarily short line segments joined at angles of Maiden's choosing, with the time cost of the angle depending on its size.

If the boat starts in the middle of the lake, how large must f now be for Maiden to escape?

Edit: Extra credit (tough):
If Ogre's top speed is 1 lake-radius per minute, and Maiden chooses the boat's initial heading at the center, what's her shortest time safely to shore?

[plasmid]

I'm pretty sure this isn't optimal, but it's a start.

Spoiler

I think the solution for the previous problem (where the maiden could turn the boat instantaneously) came down to realizing that she could go in a circle of some radius R that’s smaller than the entire lake and be able to move at a radial speed faster than the ogre (she moves a number of degrees around that small circle that’s just slightly more than the number of degrees that the ogre can move around the edge of the lake in the same amount of time). As long as she can move around that inner circle faster than the ogre can move around the perimeter, she can set it up so she’s opposite the ogre when she makes a dash for the shore.

If the maiden tries that same strategy in this problem, first she needs to find a circle of radius R where she’s moving at a radial speed that’s faster than the ogre. Define the lake’s radius as 1 and the ogre’s speed as 1, so it will take the ogre 2 pi time units to run around the lake. For the maiden to paddle around a circle of radius R she would need to make a 360 degree turn, and the amount of time it takes to rotate the boat 360 degrees is 1/g times the amount of time it takes the ogre to circle the lake, so the maiden spends (2 pi)/g time units turning. The amount of remaining time she has to move the boat forward is [the amount of time it takes for the ogre to circle the lake] – [the amount of time spent rotating the boat] = (2 pi) – (2 pi)/g = (2 pi) (g-1)/g time units to move forward. Her forward speed is f, so she’ll travel a distance of f(2 pi) (g-1)/g. That’s the circumference of the circle she can paddle around, and its radius R is that divided by 2 pi, so R = f(g-1)/g.

She can position things however she likes within that circle, but then she’ll have to bolt for the shore. I suspect that just charging forward in a straight line is not optimal, but I’ll go ahead and solve for that strategy.

Her boat won’t be pointing toward the shore when she decides to bolt, it will be pointing parallel to the edge of the circle where she’s paddling. If she’s at a distance R from the center of the lake and just paddles forward in the direction she’s facing, the distance until reaching the shore would be sqrt(1-R²), or sqrt(1-(f(g-1)/g)²). As long as the maiden bolts when her landing spot will be opposite to the ogre’s current position, the ogre will have to travel a distance of pi to reach the landing point. With that strategy, the maiden can be sure of safety if the distance she has to travel is less than f times the distance the ogre has to travel, so the condition for victory is
sqrt(1-(f(g-1)/g)²) < f pi

For the case of g=2,
sqrt(1-(f/2)²) < f pi
sqrt((4-f²)/4) < f pi
sqrt(4-f²) < f 2 pi
4-f² < f² 4 pi²
4 < f² 4 pi² + f²
4 < f² (4 pi² + 1)
so f > sqrt(4 / (4 pi² + 1)) or about 0.31435

Kind of surprisingly, that strategy is only very marginally better than sitting in the center of the lake and rotating until she's facing away from the ogre and then taking off. With that strategy she would travel 1 lake radius and the ogre would have to run pi lake radii, so she wins if f > 1/pi or about 0.31831.

[plasmid]

After more thought:

Spoiler

My previous answer talked about finding a circle where the maiden could have a faster radial velocity than the ogre. She would get in as good of a position as possible within that circle and then make a straight dash for the exit.

Now I think her best trajectory is not a straight dash, but one that bends away from the ogre’s current position a little. If M is the maiden's distance from the center of the lake and dM is the rate of change in M, and dA is the rate of change in the angle from the ogre to the center of the lake to the maiden, then the optimal path should be the one with the largest dM/dA ratio. Define angle B as the difference between the direction the maiden is traveling and a line straight out from the center. dM is f cos(B). dA is the ogre’s angular velocity minus the maiden’s angular velocity, so 1 – f sin(B)/M. In principle you could find the angle B that maximizes dM/dA = f cos(B) / (1 – f sin(B)/M) by setting the derivative with respect to B to zero. But that would tell you the best strategy if she can change direction instantaneously and I’m not yet sure how to incorporate her turning speed into that part of the answer.

 

Edited October 8, 2019 by plasmid
Added a 1/M term to account for the change in angular velocity depending on distance from the center

[bonanova]

On 10/5/2019 at 12:10 PM, plasmid said:

I'm pretty sure this isn't optimal, but it's a start.

  Hide contents

I think the solution for the previous problem (where the maiden could turn the boat instantaneously) came down to realizing that she could go in a circle of some radius R that’s smaller than the entire lake and be able to move at a radial speed faster than the ogre (she moves a number of degrees around that small circle that’s just slightly more than the number of degrees that the ogre can move around the edge of the lake in the same amount of time). As long as she can move around that inner circle faster than the ogre can move around the perimeter, she can set it up so she’s opposite the ogre when she makes a dash for the shore.

If the maiden tries that same strategy in this problem, first she needs to find a circle of radius R where she’s moving at a radial speed that’s faster than the ogre. Define the lake’s radius as 1 and the ogre’s speed as 1, so it will take the ogre 2 pi time units to run around the lake. For the maiden to paddle around a circle of radius R she would need to make a 360 degree turn, and the amount of time it takes to rotate the boat 360 degrees is 1/g times the amount of time it takes the ogre to circle the lake, so the maiden spends (2 pi)/g time units turning. The amount of remaining time she has to move the boat forward is [the amount of time it takes for the ogre to circle the lake] – [the amount of time spent rotating the boat] = (2 pi) – (2 pi)/g = (2 pi) (g-1)/g time units to move forward. Her forward speed is f, so she’ll travel a distance of f(2 pi) (g-1)/g. That’s the circumference of the circle she can paddle around, and its radius R is that divided by 2 pi, so R = f(g-1)/g.

She can position things however she likes within that circle, but then she’ll have to bolt for the shore. I suspect that just charging forward in a straight line is not optimal, but I’ll go ahead and solve for that strategy.

Her boat won’t be pointing toward the shore when she decides to bolt, it will be pointing parallel to the edge of the circle where she’s paddling. If she’s at a distance R from the center of the lake and just paddles forward in the direction she’s facing, the distance until reaching the shore would be sqrt(1-R²), or sqrt(1-(f(g-1)/g)²). As long as the maiden bolts when her landing spot will be opposite to the ogre’s current position, the ogre will have to travel a distance of pi to reach the landing point. With that strategy, the maiden can be sure of safety if the distance she has to travel is less than f times the distance the ogre has to travel, so the condition for victory is
sqrt(1-(f(g-1)/g)²) < f pi

For the case of g=2,
sqrt(1-(f/2)²) < f pi
sqrt((4-f²)/4) < f pi
sqrt(4-f²) < f 2 pi
4-f² < f² 4 pi²
4 < f² 4 pi² + f²
4 < f² (4 pi² + 1)
so f > sqrt(4 / (4 pi² + 1)) or about 0.31435

Kind of surprisingly, that strategy is only very marginally better than sitting in the center of the lake and rotating until she's facing away from the ogre and then taking off. With that strategy she would travel 1 lake radius and the ogre would have to run pi lake radii, so she wins if f > 1/pi or about 0.31831.

@plasmid My bad. It's not polite to post a puzzle and then go dark for two months. Apologies.

In the first version there was no acceleration cost for either contestant. They both could stop on a dime, turn, and resume at full speed instantly.

So here I've added a cost for angular change of velocity (for the boat only) but none for linear acceleration. Before I finished my solution my hard drive fried. I replaced my computer but I lost my work. I'll share how far I got and maybe we can finish this off collaboratively.

Spoiler

We're in agreement on the general approach. Find the largest circle of safety, pick a landing point and sprint to it.

For the first version this had to be the right approach. It gives the boat its most advantageous starting point, at zero cost. The optimization problem was to select the best landing point head straight for it. EventHorizon's beautiful and succinct solution, here, which I have not verified but which matches my best calculation, gave the landing point with the greatest arrival time differential to be where the tangent intersects the shore.

For this version the first question is what is the radius of the (new and smaller) circle of safety? And, as you found, its f (g-1)/g. So to make things simple I set g=2 making the radius f /2.

The second question is what is the optimal landing point -- with now a third question, namely, if it's not the intersection of the tangent with the shore, then what is it, and what is its shape, given the cost of changing the boat's heading? (I think this is what you began addressing in your 2^nd post.)

My only progress on that point was an intuition that waiting for the boat to turn 90^o before sprinting (radially) for shore wouldn't be a good choice. Why wait at all, actually? At least begin along the tangent, and perhaps veer (slightly) away from the ogre.

But ... I found an ugly wrinkle, the last bit of progress I had made. It's this:

Spoiler

In the first version I was certain the best choice was to pick the landing point and head straight for it. The point being that, if the ogre anticipated that strategy, he could get to any landing point (other than the radial one) faster if he reversed direction after the boat began to move. With the result that his angular path would now be less than 180^o  instead of greater than 180^o.

But that does not work for him. Why? Because when the boat sees the ogre reversing direction, the boat immediately draws a new circle at present (larger) radius and heads to shore tangentially in the opposite direction herself. And that is a better starting point, because the starting radius is larger. In fact every time the ogre reverses direction things get worse for him. I think I worked out that if ogre reversed after each of his steps, the boat could actually zigzag to shore with the ogre remaining a full lake diameter away. So in the version where the boat has no turning cost, the ogre cannot reverse direction to his advantage.

But if there's cost for the boat to turn while ogre has no cost for reversing, that argument has to be revisited. I don't think I made any useful headway on it, and maybe it's more work than fun to pursue it?

So I recall considering a simplification: (which maybe we should now adopt)

Give the boat four instantly switchable settings: FSA, CW and CCW, as now, plus Full Speed Astern. That is, boat can reverse direction without penalty. The wrinkle now is that the boat's new tangent won't line up exactly with the old one. A bit of turning is needed. I'm betting it can be proved for a small delta of motion before reversal the cost of a then needed turn will turn out to be smaller than the benefit of a larger radius. If that can be proved, the ogre loses by reversing.

It would then only remain to calculate the new tangential path length (from a circle of radius f/2) to the shore, which gives in turn the optimal value of f .

Does that make sense?

========

I didn't analyze your second post, so maybe it's better than this.