An "Oldie" with a twist of lemon

[bonanova]

An ogre with a top land speed of 4 mph, but incapable of swimming, stalks the shore of a circular lake. The fair maiden out in the boat can outrun the ogre on land, but her rowing speed is nothing to write home to mother about. How fast must she be able to row to effect an escape?

Make the assumption that the ogre is hungry [or otherwise desirous of the girl] and uses a best-strategy pursuit.

[Prime]

I have a cold, my head is stuffed, I feel like an Ogre. I am not figuring out the differential equations to deny hungry Ogre his meal. However, here is some food for thought for those Brain Denizens who took the maiden's side. Indeed, she could go slower. Mayhap, someone will try carrying out the required calculations, make an error and give the maiden a wrong advice.

To make the contest fair, the maiden should have only so much time for rowing. Having exhausted it, she falls asleep. Whereafter, the Ogre should start blowing at the boat pushing it towards the shore...

Edited February 22, 2013 by Prime

[Prime]

I would recommend the maiden should first find the radius r where she could circle in the same time it takes the Ogre to run around the entire lake of the radius R. She must do so while keeping the center of the lake between herself and the Ogre in a straight line. Once she has achieved that, she should make a dash for the shore in a straight line of the length R - r. While the Ogre will have to run around half the lake (Pi*R) distance to catch her.

If the speed of the maiden is M and the Ogre - O, then

1). Pi*R/O = Pi*r/M; ==> r = M*R/O; (equation for the circle)

2). (R-r)/M = Pi*R/O (equation for the dash.)

Solving for the M, we get: M = O/(Pi + 1);

If she cannot row faster, she must use her cell phone to call Ogre Protection Agency.

Nice problem.

Edited February 20, 2013 by Prime

[ThunderCloud]

If I were the girl in the boat, I think I'd start by centering the boat in the lake. Then, I would row directly away from where the ogre is standing. The girl will have to row a distance equal to the radius of the lake (

r), in less time than than the ogre can run a distance equal to half the circumference of the lake (Pi*r). Since it will take the ogre (Pi*r / 4) hours to complete the distance (assuming the radius is expressed in miles, of course), the girl must row with minimum speed S so that r / S = Pi * r / 4. With a little algebra, S = 4 / Pi mph.

Edited February 20, 2013 by ThunderCloud

[CaptainEd]

Assuming that the maiden's goal is merely to get out of the lake without encountering the ogre, that she has no particular direction she is obliged to go.

Wouldn't it behoove the maiden to perform continuous reevaluations of her course and steer to the spot currently opposite the ogre at every moment? I'll bet she'd have to be terribly slow oarswoman to lose this race. (However, I don't have the numbers...

Edited February 20, 2013 by CaptainEd

[ThunderCloud]

Assuming that the maiden's goal is merely to get out of the lake without encountering the ogre, that she has no particular direction she is obliged to go.

Wouldn't it behoove the maiden to perform continuous reevaluations of her course and steer to the spot currently opposite the ogre at every moment? I'll bet she'd have to be terribly slow oarswoman to lose this race. (However, I don't have the numbers...

Drat! You're right...

She could "spiral" her way out of the lake at slower speed. The question is how much slower... this problem is trickier than I thought.

[CaptainEd]

Assuming that the maiden's goal is merely to get out of the lake without encountering the ogre, that she has no particular direction she is obliged to go.

Wouldn't it behoove the maiden to perform continuous reevaluations of her course and steer to the spot currently opposite the ogre at every moment? I'll bet she'd have to be terribly slow oarswoman to lose this race. (However, I don't have the numbers...

Drat! You're right...

She could "spiral" her way out of the lake at slower speed. The question is how much slower... this problem is trickier than I thought.

Drat! You're right...I thought she could certainly spiral her way out. But a sufficiently slow-paddling maiden could actually be driven back into the center. Trickier than I thought, too.

Edited February 20, 2013 by CaptainEd

[bonanova]

I would recommend the maiden should first find the radius r where she could circle in the same time it takes the Ogre to run around the entire lake of the radius R. She must do so while keeping the center of the lake between herself and the Ogre in a straight line. Once she has achieved that, she should make a dash for the shore in a straight line of the length R - r. While the Ogre will have to run around half the lake (Pi*R) distance to catch her.

If the speed of the maiden is M and the Ogre - O, then

1). Pi*R/O = Pi*r/M; ==> r = M*R/O; (equation for the circle)

2). (R-r)/M = Pi*R/O (equation for the dash.)

Solving for the M, we get: M = O/(Pi + 1);

If she cannot row faster, she must use her cell phone to call Ogre Protection Agency.

Nice problem.

Are you sure she has to row that fast?

[Prime]

I would recommend the maiden should first find the radius r where she could circle in the same time it takes the Ogre to run around the entire lake of the radius R. She must do so while keeping the center of the lake between herself and the Ogre in a straight line. Once she has achieved that, she should make a dash for the shore in a straight line of the length R - r. While the Ogre will have to run around half the lake (Pi*R) distance to catch her.

If the speed of the maiden is M and the Ogre - O, then

1). Pi*R/O = Pi*r/M; ==> r = M*R/O; (equation for the circle)

2). (R-r)/M = Pi*R/O (equation for the dash.)

Solving for the M, we get: M = O/(Pi + 1);

If she cannot row faster, she must use her cell phone to call Ogre Protection Agency.

Nice problem.

Are you sure she has to row that fast?

The question in the OP is: "How fast she must she be able to row..." (meaning top speed.)

Her average speed could be less. She could take time getting onto the perimeter of the small circle. However, once there,

R - r distance for maiden vs. Pi*R for Ogre seems to be the optimal.Her speed has to be ~ 4/4.14 mph. I'd say I mph to maintain some distance. (Ogres have long hands.)

Alternatively, maiden coulld make smaller circles while the Ogre runs all the way around the lake, until he drops from exhaustion.

[Prime]

Once she is off her small cirle making her dash for the shore, and the Ogre chose his direction; she could continue spiraling away. Would it buy her an additional advantage? How well versed are Ogres in Calculus?

[bonanova]

We have a sufficient condition.

Escape is possible if the ogre's speed ratio advantage is not greater than [ 1 + pi ].

Is it also an necessary condition?

I.e. can she escape if the speed ratio is higher? How much higher?

That's the "twist" mentioned in the title.

[Yoruichi-san]

I think I need a clarification on "best-strategy pursuit". Does this mean the ogre will move towards/wait at the point in the circle that is closest to the maiden's current position? Or does it mean it will try to 'follow' the maiden based on her current trajectory?

[bonanova]

I think I need a clarification on "best-strategy pursuit". Does this mean the ogre will move towards/wait at the point in the circle that is closest to the maiden's current position? Or does it mean it will try to 'follow' the maiden based on her current trajectory?

The ogre will try to be on the shore where the boat lands before the boat gets there. It is a game. Whoever gets to that point first wins. The rower and ogre each act in their own best interest. The rest is part of the puzzle. The rower can row anywhere on the lake and the ogre can run anywhere on the shore. Assume each can turn on a dime [infinite acceleration, maximum speed.]

Best strategy pursuit means to imply that the ogre will not lie down and take a nap.

And the specific question now is Can the rower overcome a ogre speed ratio of greater than (1 + pi)?.

[Yoruichi-san]

Right, it is a game...and when it comes to games there's the whole trying to outguess your opponent part...

Since the maiden's motion is not constrained to smooth curves and is not constrained to a constant velocity?, it's pretty hard for the ogre to guess her landing point and/or time. She could row to, like, just out of grabbing distance of one edge, and then 'feint' accelerating movement towards the opposite edge, wait til the Ogre gets to her apparent landing point, then make a mad dash towards her original point, etc.

If the Ogre fell for the feint, and thinks she's going to land on the opposite edge, it's in his best interest to move in that direction as quickly as he needs to catch up with her apparent acceleration, but if he thinks she might go in a different direction or stop accelerating, it's in his best interest to move at a slower rate, and if he thinks she's going to make a mad dash back to the closest point on the circle, it's in his best interest to stay where he is.

[bonanova]

Wow ... in puzzles as in life.

[Prime]

I was developing a winning strategy for the Ogre based on the inertia of the boat. But then Bonanova added an infinite acceleration.

Once outside her small circle perimeter, maiden can no longer keep the center of the lake between herself and Ogre. However, she could point the nose of her boat to the point opposite Ogre. As long as she still approaches the shore. Would that help?

If maiden went at an angle, would she increase her distance at lesser rate than Ogre's?

What if maiden zig-zagged her boat pointing to the left and right of the point on the shore opposite to the Ogre's position? I hope the Ogre is smart enough to ignore the direction where maiden goes and head to the point on the shore closest to her boat.

Either way, the Ogre is at disadvantage. Whenever maiden feels she is not making it, she could always turn back to the center of the lake. Ogre should try and woe her instead of chasing.

Edited February 21, 2013 by Prime

[bonanova]

I was developing a winning strategy for the Ogre based on the inertia of the boat. But then Bonanova added an infinite acceleration.

Once outside her small circle perimeter, maiden can no longer keep the center of the lake between herself and Ogre. However, she could point the nose of her boat to the point opposite Ogre. As long as she still approaches the shore. Would that help?

OgreMaiden.gifIf maiden went at an angle, would she increase her distance at lesser rate than Ogre's?What if maiden zig-zagged her boat pointing to the left and right of the point on the shore opposite to the Ogre's position? I hope the Ogre is smart enough to ignore the direction where maiden goes and head to the point on the shore closest to her boat.Either way, the Ogre is at disadvantage. Whenever maiden feels she is not making it, she could always turn back to the center of the lake. Ogre should try and woe her instead of chasing.

This looks promising. How much advantage might be gained?

[CaptainEd]

Actually, you folks have convinced me that

aiming at the spot on the other end of O's current diameter is very suboptimal. Prime's original proposal of having M head towards the closest spot on shore (after moving to the far side of M's orbit) is almost optimal. I have the feeling that there's some real-time adjustment that M can/should make, but they still involve aiming at the nearest spot where M can get to before O can get there. It feels very much like a book I marveled at years ago, called Differential Games. I fear that Diff Eq is required, which means I'll be simulating with Excel, if I'm so lucky.

[TimeSpaceLightForce]

The ogre will try to be on the shore where the boat lands before the boat gets there.

The lady get as near the ogre as she can be..face to face. Then at slowest speed start rowing backward

until the ogre is at her back.Then full speed ahead.

[CaptainEd]

even if M speed is slightly less than the breakeven speed O/(1+pi), M can benefit from a slight course correction, once O has made a commitment. So, assume M follows Prime recommendation, and starts at the far side of M's smaller circle, heading directly away from O. O chooses a direction (CW or CCW) and hustles around. If M's speed is 99% of break even, M can wait until O has gone as much as 90% of the way around, and then change course several degrees, and reach shore before O arrives. The slower M is, the earlier she must make this correction. In my simulation, I found that if M is slower than 95% of break even, there is no such correction possible. I don't see what is special about 95, so I'm a little doubtful of my analysis.

[bonanova]

even if M speed is slightly less than the breakeven speed O/(1+pi), M can benefit from a slight course correction, once O has made a commitment. So, assume M follows Prime recommendation, and starts at the far side of M's smaller circle, heading directly away from O. O chooses a direction (CW or CCW) and hustles around. If M's speed is 99% of break even, M can wait until O has gone as much as 90% of the way around, and then change course several degrees, and reach shore before O arrives. The slower M is, the earlier she must make this correction. In my simulation, I found that if M is slower than 95% of break even, there is no such correction possible. I don't see what is special about 95, so I'm a little doubtful of my analysis.

Good Job, Cap'n, you've lowered the bar for M, giving her time for a little

touch-up for the reporters sure to be at the shore covering the story

for CNN.

Can you go beyond 5%?

[phaze]

Assuming that the maiden's goal is merely to get out of the lake without encountering the ogre, that she has no particular direction she is obliged to go.

Wouldn't it behoove the maiden to perform continuous reevaluations of her course and steer to the spot currently opposite the ogre at every moment? I'll bet she'd have to be terribly slow oarswoman to lose this race. (However, I don't have the numbers...

rather than the spot opposite from the ogre more basically put "away from the ogre" ?

The reason I ask is that this could be translated in this manner

a maiden that is on the brink of winning the contest sees the ogre is 2 or 3 meters away choose instead of grasping victory cross almost the entire length of the lake once more to get the opposite side of the lake from the ogre

At a guess maiden needs to be able to go over 1 1/3 miles per hour travels pi * lake radius/2 while the ogre runs 3/4 of the way around the lake

[CaptainEd]

Yes, phaze, I was way off base.

M should move to the Prime location, then head toward the closest land she can reach before the Ogre does.

If there is none, but she's almost fast enough, I can advise to keep going until the Ogre has committed to a side of the lake, and then make a heading change, but the proper time and direction are a matter of simulation rather than closed form for me right now.

[Yoruichi-san]

So clever and head-ache inducing feinting aside, I think that her best strat is to go in S-shaped movements that slowly drift backwards while the ogre is kept going in a 'pendulum' type motion on the opposite side of the lake.

Basically she needs to turn around before the ogre is committed to one direction each time...so her range of motion would have to decrease as she gets farther away from the Ogre, so it'd look something like a dampened harmonic...

I shoveled somewhere between 150-200 cubic feet of snow today so I don't really feel like doing the math right now tho...hooray for the snow-pocalypse...I think I prefer zombies >.<

[bonanova]

Prime has got the answer, at least as far as I have analyzed it.

That being true, I will post my analysis and people can take pot shots at improving it.

The large circle, radius R, is the lake. The smaller circle, radius r, contains the escape starting point for the boat. The ogre's speed multiple is f > 1, so R = f.r, using the period to mean multiplication. The rower has thus achieved her greatest possible separation from the ogre for which she can maintain the lake's center directly between them. We now compare two escape strategies.

[1] Radial escape.

The three black dots are, from right to left, the Ogre's and the rower's starting points, and the point on the shore that each heads for as the chase begins. The black circular arc is the ogre's path, and the black leftward arrow is the rower's path. The equation of simultaneous arrival is simply

f.x = R.pi = f.r.pi
x = r.pi

Noting that x = R-r = r(f-1) we obtain

f = 1 + pi = 4.14159...

as the maximum ogre speed factor advantage that can be overcome using radial escape.

She must be able to row 0.966 mph.

[2] Tangential escape.

The red dot now is the point on the shore that each is headed for. The sum of the black and red circular arcs is the ogre's new path, and the red upward arrow is the rower's new path. The equation of simultaneous arrival is a little more complicated, but not much.

First, we need to find the extra path length for the ogre. It's simply a.R [the red arc] where a is the angle from horizontal to the new destination point. Thus

f.y = R(pi + a) = f.r(pi + a)
y = r(pi + a)

Noting that tan(a) = y/r

tan(a) = pi + a which gives a = 77.45 degrees.

Noting that cos(a) = y/R = 1/f, we obtain f = 1/cos(77.45)

f = 4.6033

This is an 11% increase in the ogre's speed that can be overcome using tangential escape compared to radial escape.

Thus the rower can row 11% slower and still escape.

She need only row 0.869 mph.

--------

Two comments.

First, this is also only a sufficient condition. This analysis does not rule out a more efficient escape strategy. Spirals are good next steps to investigate. Piecewise linear escape paths would be easier to investigate.

Second, one could ask whether the ogre, once he sees the direction taken by the rower, might not help himself by switching directions and taking the shorter route to the red dot. The answer is no. If he does, the rower fires up photoshop, constructs a new, larger inner circle, and heads tangentially for shore in the other direction, the result of which is actually to the rower's net advantage. The ogre's best strategy is to stay the course [clockwise in this case] for the red dot.

The drawing is for a value of f in the general range we are considering. That is, a is not exact, but close to 77.45 degrees. Thus it is valid to perceive the advantage of tangential escape by noting that y is not significantly larger than x, while a + pi is significantly larger than pi. Tangential escape makes the ogre's task more difficult.

Edited February 22, 2013 by bonanova
Giving proper attribution to Prime

[Prime]

Phaze has got the answer, at least as far as I have analyzed it.

That being true, I will post my analysis and people can take pot shots at improving it.

The large circle, radius R, is the lake. The smaller circle, radius r, contains the escape starting point for the boat. The ogre's speed multiple is f > 1, so R = f.r, using the period to mean multiplication. The rower has thus achieved her greatest possible separation from the ogre for which she can maintain the lake's center directly between them. We now compare two escape strategies.

[1] Radial escape.

The three black dots are, from right to left, the Ogre's and the rower's starting points, and the point on the shore that each heads for as the chase begins. The black circular arc is the ogre's path, and the black leftward arrow is the rower's path. The equation of simultaneous arrival is simply

f.x = R.pi = f.r.pi

x = r.pi

Noting that x = R-r = r(f-1) we obtain

f = 1 + pi = 4.14159...

as the maximum ogre speed factor advantage that can be overcome using radial escape.

She must be able to row 0.966 mph.

boat escape.gif

[2] Tangential escape.

The red dot now is the point on the shore that each is headed for. The sum of the black and red circular arcs is the ogre's new path, and the red upward arrow is the rower's new path. The equation of simultaneous arrival is a little more complicated, but not much.

First, we need to find the extra path length for the ogre. It's simply a.R [the red arc] where a is the angle from horizontal to the new destination point. Thus

f.y = R(pi + a) = f.r(pi + a)

y = r(pi + a)

Noting that tan(a) = y/r

tan(a) = pi + a which gives a = 77.45 degrees.

Noting that cos(a) = y/R = 1/f, we obtain f = 1/cos(77.45)

f = 4.6033

This is an 11% increase in the ogre's speed that can be overcome using tangential escape compared to radial escape.

Thus the rower can row 11% slower and still escape.

She need only row 0.869 mph.

--------

Two comments.

First, this is also only a sufficient condition. This analysis does not rule out a more efficient escape strategy. Spirals are good next steps to investigate. Piecewise linear escape paths would be easier to investigate.

Second, one could ask whether the ogre, once he sees the direction taken by the rower, might not help himself by switching directions and taking the shorter route to the red dot. The answer is no. If he does, the rower fires up photoshop, constructs a new, larger inner circle, and heads tangentially for shore in the other direction, the result of which is actually to the rower's net advantage. The ogre's best strategy is to stay the course [clockwise in this case] for the red dot.

The drawing is for a value of f in the general range we are considering. That is, a is not exact, but close to 77.45 degrees. Thus it is valid to perceive the advantage of tangential escape by noting that y is not significantly larger than x, while a + pi is significantly larger than pi. Tangential escape makes the ogre's task more difficult.

Tangential escape does not seem the optimal even for the straight line escapes. The straight line escape with a 45-degree angle seems to perform better.