80
$\begingroup$

The fugitive is at the origin. They move at a speed of 1. There's a guard at every integer coordinate except the origin. A guard's speed is 1/100. The fugitive and the guards move simultaneously and continuously. At any moment, the guards only move towards the current position of the fugitive, i.e. a guard's trajectory is a pursuit curve. If they're within 1/100 distance from a guard, the fugitive is caught. The game is played on $\mathbb{R}^2$.

enter image description here

Can the fugitive avoid capture forever?


What I know:

  1. The distance between two guards is always non-increasing, but the farther away from the fugitive, the slower that distance decreases.

  2. If the fugitive runs along a straight line, they will always be caught by some far away guard. For example, if the fugitive starts at $(0.5, 0)$ and runs due north, they will be caught by a guard at about $(0, \frac{50^{100}}{4})$. Consult radiodrome for calculation.

  3. If there're just 2 guards at distance 1 from each other, then the fugitive can always find a path to safely pass between them. This is true regardless of the pair's distance and relative positions to the fugitive.

  4. The fugitive can escape if they're just "enclosed" by guards who're at distance 1 from each other:

enter image description here

The shape of the fence doesn't have to be rectangular. Circles or other shapes don't prevent escape either, regardless of the size.


3 and 4 are nontrivial, but can be proved by geometry argument alone without calculus. To avoid unnecessarily clustering the question, further details are given as an answer below for those who're interested, hopefully instrumental in solving the original problem.

$\endgroup$
29
  • 2
    $\begingroup$ @Stacker: Sure they'll "close in." But what's to stop the fugitive from escaping and leaving the close guards behind, always getting to a new region where the guards are still widely separated? My guess is that there is some speed where the fugitive can always escape. I wonder what that minimum speed is. $\endgroup$ May 5 at 3:25
  • 3
    $\begingroup$ Closely related by same poster: puzzling.stackexchange.com/questions/109739/… $\endgroup$ May 5 at 3:46
  • 2
    $\begingroup$ My first intuition would be to try some "zig-zag" or "spiral-out" strategies. Otherwise, maybe a simpler problem could lead to some ideas. E.g. if we reduce the number of guards to a finite number and place every guard around a circle, then see Escaping from a circle of fat lions.. $\endgroup$
    – Vepir
    May 5 at 18:09
  • 2
    $\begingroup$ Is being able to escape from an arbitrarily large number of pursuers fine, or must it be infinite? $\endgroup$ May 5 at 20:36
  • 11
    $\begingroup$ ideas $\endgroup$
    – martin
    May 20 at 5:13
11
$\begingroup$

As requested in the comments above, here is the mathematica code that generated this:

Might provide some insight. I used a discrete analog to the pursuit curve whereby for every quarter of a unit step the pursuers make (or whatever ratio you choose), the escapee makes a unit step to a point on the circumference of the unit circle around the escapee that maximises the gap between itself and its pursuers. Code modified from here.

Obviously the pursuer density increases with time. Whereas a straight line escape route plot of the distance between the escapee and it's pursuers is strictly decreasing

a plot of the distance between the escapee and it's pursuers for the local evasion strategy is, at first glance, not:

However, this is most likely misleading, since this discrete analog hides the continuous path that will at some point, no doubt pass within the restricted parameters:

$\endgroup$
4
  • 2
    $\begingroup$ This is so cool. $\endgroup$
    – K.defaoite
    May 26 at 21:27
  • $\begingroup$ +1 for the insight. About accuracy, the simulation might be improved by using an adaptive step proportional to the distance to the closest pursuer. Ideally, it would also take into account the local curvature of the paths, not just the distance, but that can become complicated fast. $\endgroup$
    – dxiv
    May 26 at 21:46
  • $\begingroup$ @dxiv I did try an adaptive step, but that would imply a change in escapee speed, wouldn't it? If the escapee is allowed to accelerate, he will certainly escape. Re the accuracy, yes, this discrete analog is just a sketch really. $\endgroup$
    – martin
    May 27 at 4:22
  • $\begingroup$ @martin As long as all points use the same discretization step, the relative speeds would not change, and the outcome would not change. What would change, indeed, is the animation speed, which would appear to slow down and show more detail when points get close, or turn abruptly. P.S. Thanks for the pointer, unfortunately I won't have a chance to really play with it in the immediate future. $\endgroup$
    – dxiv
    May 27 at 4:43
1
$\begingroup$

Proofs for points 3 and 4 in the question.

Proof for point 3

Let's denote the two guards and the fugitive by $G_1$, $G_2$ and $F$, respectively. If $\angle FG_1G_2\leq\pi/4$ at time $0$, then slipping through is possible because:

enter image description here

If $F$ travels to $G_1$ along the y axis, $G_2$ will always be within the eye-shaped intersection of the two circles before $F$ reaches $G_3$, because distance between any pair of guards is non-increasing. So the distance between $G_1$ and $G_2$ will be greater than $\sqrt2-1$ when $F$ reaches $G_3$. For a safety radius of 1/100 and speed ratio of 100, the fugitive can easily slip through between $G_1$ and $G_2$.

What about $\angle FG_1G_2\gt\pi/4$? Let's consider the extreme case where $\angle FG_1G_2=\pi/2$ at time $0$. Suppose $G_1(0)=(0,n)$ and $G_2(0)=(1,n)$. Notice if the fugitive runs leftward, the segment $G_1G_2$ will tilt counterclockwise, as illustrated below:

enter image description here

So if the fugitive runs clockwise along the arc of the circle of radius n centering at $G_1(0)$, $\angle FG_2G_1$ will be less than $\pi/4$ when the fugitive has traveled a distance of $n\pi/4\approx n$. Since the speed ratio is 100, the pair have traveled at most about $n/100$ and are still about $99n/100$ away, which means the distance between $G_1$ and $G_2$ has shrunk at most about 1% at this time. Now the fugitive can run straight for $G_2$ and slip through the pair as explained in the first paragraph.

In fact, there's even a better strategy! Notice $F$, $G_1$ and $G_2$ will be collinear sometime before the fugitive has traveled a distance of $n\pi/2\approx 2n$. By this time the pair of guards have traveled at most $n/50$ and are still about $49n/50$ away, which means distance between $G_1$ and $G_2$ has shrunk at most 2%. Since the triple are collinear, the gap between guards will remain constant at about 0.98 if the fugitive runs straight towards them. That's more than enough space for the fugitive to slip through at a leisurely pace. $\blacksquare$

Proof for point 4

Let's assume guards surround the fugitive with a circle of radius $R$. The fugitive moves straight toward some guard. When they're close to the guard, say at distance 1 away, the fugitive swerves to the right and passes every guard tangentially while keeping at about distance 1 away, as schematically illustrated below

enter image description here

Now, as the fugitive makes their clockwise movement, the distance between a pair of guards closest to them has to be no more than about 0.04 lest the target escapes. Since the distance between guards are non-increasing, when the fugitive finishes a full round, the distance between any two adjacent guards is no more than 0.04. But this is impossible given that the fugitive has moved no more than $R+2\pi R \approx 7R$. Because given the speed radio of 1:100, each guard has moved no more than $\frac{7}{100}R$. This means each guard is still at least $\frac{93}{100}R$ away from the origin. Hence the average distance between two adjacent guards is at least $\frac{93}{100}$. A contradiction. $\blacksquare$

$\endgroup$
0
$\begingroup$

I think the fugitive can evade capture indefinitely. Here are my thoughts, which perhaps can be refined by someone else.

Consider a variation of the problem: the fugitive begins at (0,0) but there are approx $2\pi R$ guards uniformly-spaced around a circle centred at the origin of radius $R$, so that adjacent guards are spaced apart by ~1 unit. Also suppose that guards move toward the origin rather than toward the fugitive. (As a commenter observes, this is already basically the case for very distant guards.)

Suppose the fugitive runs at 100 units/s in a straight line. Then the prisoner intersects the circle of guards after approx $R/100$ seconds, at which point the circle of guards has approximate radius $\frac{99}{100} R$. The gap between adjacent guards is now 99/100 units, allowing the fugitive to easily slip through. Notice this quantity is independent of the initial radius $R$.

Now suppose there are circles of guards of radius 1, 2, 3, ... and on each circle, adjacent guards are separated by 1 unit. The distance between a pair of guards on different concentric circles is always at least 1, the fugitive can move freely in the gaps between concentric circles. Moreover, since the fugitive can slip past a circle of arbitrary radius, the fugitive can slip past all the circles and evade capture.

This concentric circle setup is interesting because the guards are initially distributed with roughly the same distribution and density as in the original problem. It is also still the case that at each point in time, the density of guards around the fugitive's position is increasing. But the fugitive has an easy escape strategy, and in fact, at no point in time is the fugitive even close to being caught.

It seems to me that arranging guards on concentric circles is essentially the same as arranging them on lattice points, since there's nothing special about integer coordinates. I also conjecture the analysis above doesn't meaningfully change if the guards move towards the prisoner rather than towards the origin.

The key idea in this problem is that the fugitive will be caught iff they become surrounded by a critical-density cloud of guards (i.e. a cloud of guards with more than one guard per ~0.01 square units). But the guards begin at a low density distribution, and they all move as one towards the fugitive, so their density increases very slowly; indeed, their density increases more slowly the further away they are from the fugitive. So the fugitive can always pass them before they've had time to accumulate sufficient density.

$\endgroup$
9
  • 2
    $\begingroup$ I think there is a weak point in the argument, and that's the assumption that chasing the origin instead of the fugitive doesn't change the outcome. At first sight, the argument would unwind the same if the guards were placed on the $x = \pm 1/2$ verticals and the fugitive ran straight up along the $y$ axis. But in that case the fugitive would be eventually caught if the guards chased him, not the origin, and this would happen regardless of the relative speeds and sizes. $\endgroup$
    – dxiv
    May 7 at 7:28
  • $\begingroup$ @dxiv Let's say guards are evenly spaced on a very large circle centered at the origin. The radius of the circle is such that if the fugitive dash in a straight line between 2 guards, he will barely get caught, i.e. closest distance to a guard is 1/100. Can he do better than this by going along some other curve? You see in your 𝑥=±1/2 example, when guards to the north is about to catch him, the fugitive can just turn left or right and continue escaping for a distance comparable to his northward dash, and then zig-zag again... $\endgroup$
    – Eric
    May 7 at 8:32
  • $\begingroup$ The difficulty in the escape as I see it is that if the a guard would be able to catch the fugitive along the $y$ axis, then you have quite a long line of guards already too close to slip through, so you really do need to run east or west for a similar distance before you might find a gap. But while you do that the guards to the north and south of this line are closing in on your new $y$ coordinate. Can you find a gap in the line to your north before the guards to the south block your path? $\endgroup$
    – David K
    May 7 at 12:10
  • $\begingroup$ @DavidK Yes, you can. The "closing in" effect is only prominent along the north-south direction. Play the simulation mentioned in the post and you'll see. $\endgroup$
    – Eric
    May 7 at 14:07
  • $\begingroup$ @Eric My comment was only meant to point out that the straight line escape does not work as proposed, and the reason why it cannot work. $\endgroup$
    – dxiv
    May 7 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.