Puzzle: escaping a thief

There’s an interesting article at Fast Company that shows how games can help with strategic decision making. The US Navy is doing something very fascinating. It is launching an online multi-player game as a way to learn innovative tactics and strategies to combat Somali pirates. Time will tell if the game will yield viable solutions, but I give credit for them just implementing this idea.

In honor of the U.S. Navy using games to hunt pirates, I thought it would be appropriate to share one of my favorite puzzles about pursuit. This is a classic chase game which is a lot harder to solve than it sounds.

The puzzle

You are in a boat exactly at the center of a perfectly circular lake. On the shore, there is a thief who wants to take you hostage.

You can run faster than the thief, if you make it to shore. But the thief can run 4 times as fast as you can row. The thief cannot swim and doesn’t have a boat.

Can you escape the thief?

If you figured it out, feel free to leave a comment on how long it too you.

I will post my solution during the weekend…

Update: link to solution posted in the comments. See this or this.

Bonus: Suppose the thief can run k times as fast as you can row. For which values of k can you escape?



Share this post:

| More

Previous post:

Next post:



  • anomdebus

    There is a donut shaped area in the lake that is defined by:
    a line after which, if you are opposite of the center point, you can beat the thief to the shore
    a line before which, your angular speed is faster than the thief around the shore.

    You need just row to this area and then row within that area (circularly) until you are opposite the center point from the thief, then row to the shore.

    The bonus is where these two lines converge. The inner line is closer to the shore the greater the speed multiplier, and the outer line gets closer to the center point.

    The general point took me about 5 minutes. I started with a zig-zagging idea, which still technically works, but you need to know at what point to make to shore. Now that I think of it, the zig-zagging would probably be easier to row than a circle.

    I have not yet worked out the math, though: too early. I have spent probably 15 minutes on that, but I just got up. I would guess, you need to be closer than pi/speed from the shore to make it and he outer limit is the circle defined by 1/speed from the center to match speed. Maximum speed is pi+1.

  • Phanton

    Took about 15 minutes. Anomdebus has the right idea, using polar coordinates makes life easier. I got that you could escape if the thief was running slower than \sqrt{1+(\pi+1)^2} which is approximately 4.26.

  • miatachris

    To me, it seems that the rower’s distance is the radius of the circle, and the distance the runner must cover is half of the circumference of the circle because the rower would start to row along the diameter line that includes the runner’s starting point to maximize the runner’s distance. Using the formulas for circumference of a circle and distance= rate (time) I chose 10 to be the runner’s distance and then worked the equations. The runner beats the rower easily so the thief cannot be escaped. (1.01 time for the rower > 0.79 time for the runner).

    Rower’s distance = radius of circle = A
    Runner’s distance = 1/2 circumference of circle = B

    C = 2 (pi) (radius)
    2B = 2 (pi) (A)
    B = (pi) A

    rowing distance = rowing rate (time)
    running distance = running rate (time)

    running rate = rowing rate (4)

    A = B / Pi
    if B = 10 then A = 3.18

    rowing time = 3.18 / pi
    rowing time = 1.01

    running time = B / 4 (pi)
    running time = 0.79

    Rowing time > running time so rower loses.

  • miatachris

    Sorry — it took me about an hour.

  • miatachris

    All values of k less than pi lead to the rower escaping.

  • http://vpsgraphics.com Paul Smith

    If on a lake of radius 1: Row from the center to a point on a circle of radius 1/4, all the while keeping the thief opposite the center. Once you have the remaining 3/4 of the radius to go, head straight to the nearest point of shore. The moment you arrive, the thief will be (pi-3) away.
    All values of k <(pi+1) will result in escape.
    Took seconds to think out the concept, a couple minutes to think through the math, a several more to type this out. Haven't written this out to check any if it, as I'm travelling, but I think it's right (or at least close).

  • Pelli

    Seeing as everyone is posting their solution, I might as well post mine. The idea was pretty straightforward to find, but it did take half an hour or so to get right.

    Start by rowing to the maximal radius r = R/k (where R is the radius of the lake) where you can still position yourself diametrically opposite to the thief.

    Then, I parametrised the path as distance r from the centre as function of angle theta to the thief, and found an expression for dr/dtheta in terms of the angle alpha between the direction I row along and the radius from the centre. Maximising dr/dtheta gives sin(alpha) = R/(kr).

    Plugging this back into the expression for dr/dtheta and integrating, I found that the change in angle theta when moving optimally from r=R/k to r=R was (x – arctan(x)) where x = sqrt(k^2-1). This must be less than pi, and equating gives the maximal x = 4.49341… and hence k = 4.60334…

    The optimal path can be described as follows: Imagine a helping friend standing in the centre of the lake, always turning to face you. Let him hold out his arm with length R/k horizontally to the side where the thief is. Always row straight away from the end of his arm (so if you’re in a standard rowing boat, row so that you always look straight at the end of his arm).

  • Eyal

    Paul and anomdebus, I think that I can do better.

    I’m not much for drawing but look at this: http://i.imgur.com/irxHb.jpg

    Assume that the thief has speed k=(pi+1) and I have speed 1. I row within distance 1/(1+pi) from the center so, radially, I’m faster than him. I maneuver until my distance from the center is 1/(pi+1) and he is farthest from me. In the drawing, I’m at S and he’s at T, lake’s center between us.

    Now, I head due north. Assume that he picks clockwise. I continue north until he has run pi/8. Now I’m at S’ and he’s at T’. From here, I row toward S”.

    My distance to S” is now about 0.70123 and his distance around from T’ is pi in either direction. 0.70123*k is just 2.904, which means that I’ll arrive at the shore with time to spare! This seems to disprove k<pi+1.

    My intuition is that the best strategy is one of:

    1) Row directly away from him.

    2) Row toward the point farthest from him.

    The idea took about 15 minutes but drawing and calculating took another 20 minutes. (Please, someone check my geometry/math!)

  • Kevin

    It seems to me that you always want to be moving toward the end of the diameter line that is opposite of wherever the thief is. This would result in a spiral-shaped path to freedom.

  • Ewan

    Kevin posted just as I got here, but I think he’s right: your plan to maximise the speed of thief from whom you can escape is to row in a spiral: start out directly away from thief, then spiral in a direction determined by the direction he/she chooses to run.

    Which is great, but I don’t have a formula for spiral length to hand :) .

  • Shuibing Wen

    Since the thief is k-times speed,when the distance between you and the centre of the lake is less than R/k,your angular velocity is faster than the thief,so you can make yourself ,the thief and the centre of the lake in the same line,so you are far away from the thief.When the distance between you and the centre of the lake is larger than R/k, your angular velocity is less than the thief,so the only way for you is go along from the direction the centre of the lake to you,you will take (1-1/k)R/v to swim to the shore,and the thief will take Pi*R/k/v to get you,so if (1-1/k)R/v <=Pi*R/k/v,that is k<=Pi+1,you can run away from the thief.

  • Phanton

    I worked out a new solution: There is a small circle where your angular velocity relative to the centre is greater or equal to the thief’s. You can easily get to the edge of the circle and be collinear with the centre of the circle and the thief.

    If the thief is traveling at 4 times your speed then you can simply travel to shore along the line that made you and the thief collinear. A few calculations will show that the distance the thief has to travel to catch you is larger than 4 times the length of distance you have to travel and so you will get there first.

    To find the maximum speed the thief can travel is a bit trickier. To do this you must continue along that collinear line at an infinitesimal distance until the thief chooses a direction to catch you (clockwise or anticlockwise). Once the thief has chosen a direction, he is best off sticking to that direction since if he changes his mind, he will have to travel back and will meet the point such that you, him and the centre are collinear and so you will be at square one except closer to land than you were before.

    Now suppose that the thief choose a direction, then you travel perpendicular to the collinear line in the direction opposite to the thief until you reach the shore. I needed to compute my answer numerically and got k to be approximately 4.355.

    The first part is reasonably quick, the second part took me about an hour.

  • Eyal

    How did Pelli get that optimal path? The solution sounds good but I don’t see the derivation.

  • Pelli

    Here is how to find the optimal path:

    Rescale so that the lake has radius r, your velocity is 1 and the thief’s velocity is k.

    In a small time dt, you move a distance dt. Suppose this is at angle alpha to the radius from the centre. Then your radius changes by dr = cos(alpha)*dt whereas the angle between you and the thief changes by (sin(alpha)/r – k)*dt, where the k is due to the thief running toward you.

    Hence dr/dtheta = cos(alpha)/(sin(alpha)/r – k). Differentiate with respect to alpha to find the optimal sin(alpha) = 1/(kr) .

    Plug that back into dr/dtheta to find dtheta = (…)*dr and integrate r from 0 to 1.

  • Pelli

    Sorry, the lake has radius 1. r is your distance to the centre.

  • Eyal

    I got it now Pelli, thanks. Very nice figuring out dr/dtheta and taking a partial derivative to find the max. I did the second half of the calculation a little differently, though.

    After finding the optimal value of alpha to be at sin(alpha)=1/kr I realized that at the start, r is 1/k anyway so alpha 90 degrees. The boat travels the chord at radius R/k!

    Because the boat is travelling away from the center it is never within the R/k circle. Thus, the thief is always closing in on the boat and has no reason to turn around. (If he did, just turn the boat around 180 degrees and the strategy runs in reverse.)

    The thief can only catch the boat if his path takes less time than the boat’s. The boat’s path is half the length of the aforementioned chord:

    sqrt(R*R-R*R/k/k)

    The thief’s path is:

    R*pi+R*arccos(R/k/R)

    Now solve:

    k*sqrt(R*R-R*R/k/k) = R*pi + R*arccos(R/k/R) =>
    k*sqrt(1-1/k/k) = pi + arccos(1/k)

    http://www.wolframalpha.com/input/?i=k*sqrt%281-1%2Fk%2Fk%29+%3D+pi+%2B+arccos%281%2Fk%29

    4.6033…, same answer as you.

  • Pelli

    Eyal, very nice! I had my right triangle the wrong way round, so my description of the optimal path is wrong. It is really a straight line, tangent to the “starting circle”. (Is this what anomdebus and Phanton meant?)

    I suppose we can argue that the optimal strategy involves just rowing in a straight line from the starting circle, because given any strategy that reaches a point X successfully, we can do at least as well by rowing directly to point X. (We cannot row fast enough to “deceive” the thief in any way after leaving the starting circle, so we might as well row directly towards our goal).

    Is there a better way than to generalise Eyal’s calculation to show that the tangent to the starting circle is the optimal line?

  • William

    There are 2 radii that we are concerned with. The first is the radius within which you can keep up with the thief, while staying opposite the center of the lake from him. This circle will be 1/4 the circumference of the lake, and thus 1/4 the radius:

    r1 = R/4

    The second is the radius at which you can make a straight line to the shore to beat the thief. The thief must run halfway around the lake, or pi*R. So the maximum distance you can be from the shore must be 1/4 that, or pi*R/4. Thus:

    r2 = R – pi*R/4

    As long as this radius is within the reach of the limits of r1, you can escape.

    r2 < r1
    R – pi*R/4 < R/4
    R < (pi+1)*R/4
    4 < (4.14)

    So you can escape if the thief is 4x faster.

    To generalize for a thief that is k times faster:

    R – pi*R/k < R/k
    R < (pi+1)*R/k
    k escape

  • Neeraj Goyal

    Yes..you can easily escape if thief can run only 4 time faster than you.

    unless thief can run more than 7.857143….times faster than you, you can easily escape

  • Michael

    My original idea was that the thief could catch me if he could run at least pi times as fast as I could row.

    Then I contemplated that perhaps if I continually changed my direction so I was rowing away from the thief along the line from the thief through the center of the lake he might not catch me. However I didn’t feel like doing the calculus necessary to solve the equation describing this motion.

    Can the thief’s knowledge of my escape route change his strategy in his favor? But if she does this then I can change my strategy, so we are back to the original problem.

    Next it occurred to me that the puzzle assumes that both I and the thief will always make the optimal move. But this need not be the case. For instance, the optimal path assumes constant visual constant between myself and the thief. Therefore, one solution would be to wait until dark, then quietly row away from the thief in a random direction. The thief will not know where I am and once I reach the shore I will run away from the lake.

    Conversely, if there are trees or other barriers near the shore, the thief could follow me without being seen. I would have to assume the thief was making the optimal approach but could be tricked and the thief could catch me.

    Maybe this contest is held where there is artificial lighting and it never gets dark, and we can both see each other at all times. I can still escape no matter how much faster the thief can ran than I can row, so long as I can run faster than him by a non-negligible amount, assuming I have a boat with a non-zero length or width.
    Finally, another thought occurred to me. To avoid capture I simply rowing directly towards the thief. When I get close enough to the shore that my speed parallel to the thief while jumping towards the short is greater than the thief’s speed, I accelerate to my running speed away from the thief and jump. I the thief jumps first he must land on the boat and I can still run faster than him and jump away from him. In fact, if the boat is big enough I can probably let the boat hit the shore, and forgo any jumping at all, as the thief either has to approach me (in which case I can get away because I am faster) or wait for me to disembark (in which case I can still get away because I can choose my direction away from him and can run faster).

    Total thinking time: about 10 minutes.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Thanks all for the comments and solution methods. Both Pelli and Eyal came across the correct solution for the generalized case.

    The basic idea is as follows. If you row directly for the shore from the center, opposite of where the thief is, you will have to cover the distance of the radius. The thief has to run around the lake, which is a semicircle with distance (pi) x (radius). That means the thief has to cover roughly three times as much distance, but since he is four times as fast, he can cover it.

    The trick is you can row a little bit further out before you make your dash for the shore. If you were to row at a concentric circle with radius r/4, then you will make one round with a distance of r*(pi)/2. The thief would have to go around the lake with a distance of 2*(pi)*r. As you will be traveling around a circle with 1/4 the distance against a thief who moves 4 times as fast, the two of you will be exactly keeping up with each other.

    For any circle slightly closer to the shore, you will be able to row around faster than the thief can keep up, and you’ll surely be able to beat him.

    For the generalized case, you want to find the circle where the radius is (1/k) times as large as the total lake. Then you travel along the tangent line to dash to the shore.

    There is a nice writeup of the math equation here with a nice java illustration to see how it works.: http://openmap.bbn.com/~tomlinso/chaser/chaser.html

    As stated on that website,

    “The threshhold value of K is 4.60333885 (to 8 decimal places). This is the solution to: sqrt(1-1/k^2) = (pi + acos(1/k))/k.”

  • Brenda Pawelek

    I would stay in my boat, safe from the potential kidnapper. When he falls asleep, row to the opposite shire and run away!

  • John B

    There’s other options. You’ve got oars – big long sticks. Lots of things can be done with sticks. You are not necessarily limited to using the boat – how fast do you swim? Etc.

    While the above is certainly a wonderful math problem, it’s also a fun challenge to think about, outside the box. How can you use and/or abuse those rules to win?

  • Payam

    Okay, I think there is a problem with the solution that is given in the website:

    “… After you cross the R/K circle and are following the tangent to the shore, if the goblin reverses direction, you simply turn onto the chord centered on your position and head away from the goblin; you will reach the shore with an even greater margin.”

    Yes, but the thief can reverse his direction again, which directs you to raw back toward the R/K tangent point, and the thief to run toward the opposite point again. Thus if reversals continue, you can never reach the shore. I think the author of the page didn’t consider this possibility.

    So far only the very first solution, proposed by anemdebus, i.e. reaching the R/K circle with the thief on the other side, and then rowing along the radius toward the shore, is the one that guarantees freedom in a finite amount of time — no matter what intelligent the chaser is. Of course the maximum escape k for this strategy would be just pi+1 ~= 4.1415…

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    There is also an explanation from a 2001 IBM Research puzzle:

    http://domino.watson.ibm.com/Comm/wwwr_ponder.nsf/solutions/May2001.html

    The answer is k=4.6033388

  • Pingback: Using logic to solve a test question - Mind Your Decisions

  • U.S. Government = Terrorists

    Western countries dump their nuclear waste in Somalian waters; those “pirates” are defending their life and liberty.





Previous post:

Next post:

Other posts you may enjoy reading:

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress