This post is about yesterday's problem. I have to admit - the question is tougher than I thought it was (it's another of those I asked before solving). The question in the book is simply, "Imagine the demon goes four times as fast as your boat, how can you escape?" That question is purely conceptual. I'll answer it, then go as far as I can right now towards, "what is the minimum ratio of the speed of your boat to speed of the demon for you to be able to guarantee escape?" (Obviously less than 1/4).
I'll set the units of distance so the radius of the lake is 1, then set the units of time so the speed of your boat is also 1. The speed of the demon is D.
At first glance, you can realize that if D < Pi, you can just shoot for the shore opposite of where the demon is standing, and you'll get there first. But you can escape even if your ratio is worse than this.
Qualitatively, here is the plan: You start rowing in the direction directly away from the demon. He picks a direction and starts running that way, anticipating where you'll land. But it's to your advantage to keep the demon 180 degrees around the lake from you - as far as possible. To do this, just angle your boat a bit so whichever way the demon runs, you stay directly opposite him.
As long as you're still close to the center of the lake, this is easy to do. Your angular speed can be quite high because it's a small circle around the center. The demon's angular speed is low because he's so far out. Hence, you can keep him 180 degrees away from you.
What's the maximum distance from the center of the lake where you can still force the demon to be 180 degrees away from you? That happens when your maximum angular velocities match, which is at a distance 1/D.
After that, you still have to be able to make it to shore. If you were going on a straight shot, your speed would have to be great enough so that the time for you to get to shore is less than the time for the demon to run halfway around the lake. Algebraically,
(1 - 1/D) < Pi/D
D < 1 + Pi
The new strategy takes us from D < Pi to D < 1+Pi (slightly greater than 4), but is there something even better? Maybe it's worth your time to curve away from the demon despite the fact you can't keep him a full 180 degrees away from you.
A moment's thought will tell you undoubtedly yes - you can do better than moving out to the cutoff circle and then sprinting straight for shore. Suppose you are making that beeline for shore. The demon has picked a direction and is running towards your expected landing spot. If you turn your heading a very slight amount away from his side of the lake, you now have two components to your velocity - a "radial" component towards the edge of the lake and a "circumferential" component around in a circle. By the Pythagorean theorem, the squares of these speeds add up to the maximum speed of your boat. So if the component of circumferential speed is small, the change in the radial speed is second-order. Explicitly:
Sr2 + Sc2 = 1
Sr = (1 - Sc2)1/2
using the binomial theorem, for small Sc, this is
Sr = 1 - 1/2*Sc2
So you can pay a very small price to your radial velocity in return for some circumferential velocity. Losing radial velocity means it takes you longer to get to shore, while gaining circumferential velocity means it takes the demon longer to get to your landing spot. There's a positive effect to veering off course, and a negative effect. But since you can make the ratio of the negative effect to the positive effect arbitrarily small, it'll always be worth your while to veer away from a straight shot to shore at least a little bit, assuming your goal is to land with the demon as far away from you as possible.
Let's go back to the beginning and try a more quantitative approach.
If we want to escape the demon, we should always go at full speed. The demon's strategy is simple - he also goes at full speed in whatever direction takes him closer to you. If both directions are equal (because you're 180 degrees apart), he picks one at random. So the only thing we have to choose is our bearing, based on our current location and the demon's current location. What should the criterion be? I don't have a proof this is optimal, but if your goal is to land on shore as far from the demon as possible, let's make the criterion:
Choose the heading that maximizes the quantity:
(dI/dt) + (dr/dt*I)/(1-r)
Where "I" indicates the distance from the demon's position to the "intercept point", the point on the shore closest to your boat, and "r" is your distance from the center of the lake.
I derived this criterion with the following reasoning:
Imagine you were going to make a beeline to shore from wherever you currently are. If we divide the demon's distance to the intercept point "I" by his speed "D", we get the demon's expected time to intercept, I/D. On the other hand, your expected time to get there is just your distance from shore, 1-r, because your speed is 1. Finally, if we divide those two times by each other, we get a ratio I/(D*(1-r)). If that ratio is bigger than one, you've made it - you could escape with a bee-line trajectory now. Unfortunately, if D>Pi, that ratio at the beginning of the problem is less than one. But by choosing a clever trajectory, we can try to push that ratio up to one, and then escape. So at every moment, we're going to choose the heading so that this ratio is as high as we can get it a short time "dt" from now. To do that, just take the derivative of the ratio with respect to time and maximize it.
If you take the derivative, you'll noticed I dropped the constant "1/(D*(1-r))". This yields the condition above. As long as the derivative of that ratio is positive, we'll assume you still have a chance. Once you can't push the ratio any higher he's got you, since if you were going to escape, the ratio would go to infinity right before you got away, and if he's going to catch you, the ratio goes to zero.
Choose "@" to be the angle between your heading and the heading straight for shore. I'll let you work through the calculus for yourself should you so desire. The goal is to get "@" as a function of "I" and "r". That is, choose the best course whatever the current situation is. I found:
tan(@) = (1-r)/(I*r)
Reality check: I expect that as you near the shore, you should aim more and more towards it. As r->1, @->0.
I have to be careful with this formula - it only applies when the demon is NOT directly opposite you. If he's directly opposite you, then angling your boat brings him closer no matter which way you turn - a factor not accounted for in my calculation. So this formula only applies once the boat is already past the cutoff circle and racing for shore.
Now we've worked out a strategy, all that's left is integration. Unfortunately, the integration isn't very easy. We'll start things off by introducing a polar coordinate system (r,@). The center of the lake is (0,0). The demon starts out at (1,0), and the boat, having already completed the first stage of its maneuvers, begins at (1/D,Pi).
Let's say the demon chooses to run up towards the top of the circle (increasing @). Then his position as a function of time is (1,D*t).
Your position is trickier. It depends on your bearing, which depends on both your own position again and the demon's position. If you write out these equations, you'll see that they're pretty hopelessly coupled. I get
dr/dt = I*r/((1-r)^2 + (I*r)^2)^1/2
d@/dt = (1-r)/(r*((1-r)^2 + (I*r)^2)^1/2)
where I = @ - D*t, and "@" and "r" are your polar coordinates as functions of time.
So from there, I'm basically analytically screwed. If you'd like to do the numerical analysis and figure something out, please let me know what you find.
The sad part is, even doing the integration doesn't actually find an upper bound for D. It only finds an upper bound assuming my particular strategy is the best possible strategy. Just because it seems like a good one in my head doesn't mean there isn't one that's better, and I honestly have no idea how to go about proving either:
A) such-and-such a strategy is optimal for escaping the demon
B) no strategy can do better than such-and-such
Moral: These toy problems, though simple and well-defined, can be tougher than they look when you actually start to bite into them. I was originally just attracted to the little trick of realizing you could force the demon away from you by making small circles about radii close to the center of the pond. But after I got that I naturally wanted to go a step further. Turned out the next step was biting off more than I could chew.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment