45
$\begingroup$

A fugitive is surrounded by $N$ police officers, with the nearest one at distance $1$ away. The fugitive and the officers move alternatively.

  • In a fugitive move, the fugitive can travel no more than a distance of $\delta$
  • In an officer move, the sum of distances travelled by all officers can be no more than $\delta$

Is it true that for $\forall N$, $\exists \delta$ such that the fugitive can escape regardless of the officers' initial distribution?

If distance between the fugitive and an officer is $0$ in finite moves, the fugitive is caught, otherwise they escape. I strongly suspect the fugitive can escape if $\delta$ is small enough, but am unable to give a proof. I created this problem myself and know no other existing sources.


Addressing issues in the comments:

  • A natural strategy for the officers is to stay on a circle centered round the fugitive, and somehow try to gradually shrink it while preventing the fugitive from escaping out of it, as suggested by Will. But it seems this strategy wouldn't work as expected, as pointed out by usul.

  • TimothyChow mentioned the angel problem and fox games, both of which are games played on 2D lattice. I'm not sure ideas in lattice games would help, but let's see if any progress could be made if I "reformulate" the game in that fashion: On an infinite chessboard there's a single white king and $N$ black kings. The nearest black king must be $D$ moves away from the white king. Given $N$, white dictates the value of $D$, then black places their kings. Can white always force a draw without capturing any black kings?(Let's ignore niceties in chess rules such as stalemate, etc.) For that purpose you can also replace the kings with power-one rooks (which can move only one square in four cardinal directions). Hopefully an answer for the game could shed some light on the original game, though I have no ready answer in mind so far.

$\endgroup$
43
  • 8
    $\begingroup$ @Eric Have you analyzed the naive strategy where the police officers are equally spaced around a circle and move directly toward the origin unless they can capture the fugitive immediately? Posting that analysis would improve your question, I think. $\endgroup$ Apr 11 at 18:10
  • 4
    $\begingroup$ The problem seems vaguely reminiscent of the Angel problem but it's not clear to me whether any of the ideas carry over. It can also be thought of as a type of fox game but I don't know of any general theorems about fox games that would be relevant here. $\endgroup$ Apr 12 at 1:58
  • 3
    $\begingroup$ @მამუკაჯიბლაძე mathoverflow.net/questions/358129/the-lion-and-the-zebras you must have meant this one $\endgroup$
    – Eric
    Apr 12 at 13:14
  • 6
    $\begingroup$ Okay, I typed a whole answer until I noticed that I misread the rules... So for posterity: If every policeman could move by $\delta$ each turn, the fugitive gets caught if and only if he starts in the interior of the convex hull of the policemen. The strategy for the "if" is for the policemen to always keep their absolute direction towards him the same. The strategy for the "only if" is to just move away perpendicular from the hull and of course also works for the correct problem. $\endgroup$
    – mlk
    Apr 12 at 15:56
  • 3
    $\begingroup$ In the power-one rook version, if two officer rooks can move per turn, then 4 officers can always capture the fugitive. $\endgroup$ Apr 17 at 20:25
14
$\begingroup$

If any officer can move more than $\delta$, then that officer can simply chase down the fugitive. Thus, I propose modifying the question to allow each officer to move at most distance $\delta$, but they all pull from a given pool of movement of size $c\delta$. Then we can ask what values of $c$ guarantee the capture of the fugitive. We can squeeze $c$ from two directions:

  1. An lower bound $l$ for the officers such that they can always capture the fugitive if $c\gt l$.
  2. An upper bound $u$ for the fugitive such that they can escape if $c\lt u$.

I claim that $l=2$ works, and we only need three officers to reach this bound. To see this, pick an equilateral triangle containing the fugitive, and place one of the three officers on each of the three edges of the equilateral triangle - specifically, on the orthogonal projection of the fugitive's location to that edge.

After each fugitive's move, the officers can move until they are each still at the orthogonal projection of the fugitive's location to their edge. This takes $$\delta ( | \cos \theta| + |\cos (\theta+ 2\pi)| + \cos (\theta + 4\pi)| ) \leq 2 \delta $$ movement, with the inequality because $\cos \theta + \cos(\theta + 2\pi/3) + \cos (\theta + 4\pi/3) =0$ so if one is positive and two are negative, the positive term is at most $1$ and the sum of the two negative terms are at most $1$, and similarly with one negative and two positive. Equality is attained for $\theta = 0 , \pi/3, 2\pi/3, \pi, 4\pi/3, 5\pi/3$, i.e. for moves parallel to an edge.

Because we keep the officers on the orthogonal projections, the fugitive can never escape this triangle, as then the fugitive's orthogonal projection would equal their location so their path would cross an officer. Since $c>2$, we have a little bit of extra movement, which we can use to shrink the triangle each turn.

The race is still on to improve this constant!

$\endgroup$
23
  • $\begingroup$ Very nice! Any thoughts on modifying this scheme with 6 officers / a hexagon? $\endgroup$
    – usul
    Apr 19 at 16:34
  • 5
    $\begingroup$ @usul I'm pretty sure 3 officers on the 3 sides of an equilateral triangle, each one staying on the orthogonal projection of the fugitive to their side, can handle any $c>2$, since $\max ( | \cos (\theta) | + |\cos(\theta+ 2\pi/3)| + |\cos(\theta+ 4\pi/3)|| ) =2$. $\endgroup$
    – Will Sawin
    Apr 20 at 2:52
  • 2
    $\begingroup$ @PaceNielsen I edited, but I don't think I can make it community wiki. I don't see how to do $c=2$ here yet. The directions where the bound is sharp are those parallel to an edge. As soon as any of the officers lags a little, if the fugitive keeps moving in these directions, the officers have to use their full movement to follow and so will not be able to reduce the amount of lag. $\endgroup$
    – Will Sawin
    Apr 20 at 13:21
  • 2
    $\begingroup$ I think you're right. I forgot that they're not using their full movement before reaching the corner. Maybe the other direction is also worth exploring: the lower bound of $c$, i.e., finding some $c\lt 1$ such that the fugitive can escape. $\endgroup$
    – Eric
    Apr 20 at 16:28
  • 1
    $\begingroup$ You are right^^, but then they have to shrink it wisely... if they shrink it to much, F can escape in one move out of the triangle $\endgroup$
    – jcdornano
    Apr 23 at 14:54
1
$\begingroup$

This is the answer : https://math.stackexchange.com/questions/4147724/exemple-of-chassing-puzzles-idea-of-extending-from-the-way-to-solve-create-each/4147833#4147833

Just go to the answer of the question in the link, no need to read the question (that is related to some generalization of the puzzle) to understand the proof.

$\endgroup$
1
  • $\begingroup$ I think it is complete and correct. $\endgroup$
    – jcdornano
    May 24 at 10:33

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.