45

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.

Eric
  • 2,601
  • Is movement restricted to $R^2$? Or something else? – Bill Bradley Apr 11 '21 at 14:04
  • 1
    @BillBradley Yes, it's R2. – Eric Apr 11 '21 at 14:06
  • 8
    @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. – Timothy Chow Apr 11 '21 at 18:10
  • 2
    @TimothyChow The analysis is trivial (almost) because the fugitive can just move along a spoke that divides two adjacent policemen spokes. If say $\delta=1/(2N)$ and the fugitive takes $N$ moves and stays there, they're safe. (speed of an officer is only $\delta /N$ if all of them choose to move an equal distance toward the origin in each turn) – Eric Apr 12 '21 at 00:53
  • 4
    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. – Timothy Chow Apr 12 '21 at 01:58
  • @TimothyChow I've seen somewhere a "dual" game - many sheep that try to escape a single wolf. Cannot even figure out whether it is equivalent, more difficult or less difficult... – მამუკა ჯიბლაძე Apr 12 '21 at 11:59
  • 3
    @მამუკაჯიბლაძე https://mathoverflow.net/questions/358129/the-lion-and-the-zebras you must have meant this one – Eric Apr 12 '21 at 13:14
  • Exactly, thanks! I wonder if this one can be answered by somehow reversing that one or something... – მამუკა ჯიბლაძე Apr 12 '21 at 13:19
  • @მამუკაჯიბლაძე I think they're very different games, so probably not. – Eric Apr 12 '21 at 13:25
  • 6
    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. – mlk Apr 12 '21 at 15:56
  • 1
    @mik Can you explain what it means "for the policemen to always keep their absolute direction towards him the same"? – Eric Apr 12 '21 at 16:13
  • 2
    Absolute in the sense of compass direction. Draw a line through a policeman and the previous position of the fugitive. Now that policeman moves to the point on the parallel line through the new position of the fugitive that is reachable and closest to that new position, thus ending up in the same direction. If all of them do that, none of them will be further away, but at least one of them will be closer by an amount that can be bounded from below depending on the directions. – mlk Apr 12 '21 at 16:30
  • Here's a strategy for the officers that I think should ensure they capture the fugitive when $N$ is big and $\delta$ is small, although I have not proved that it works. Place the $N$ officers evenly around the unit circle. Throughout the chase, the officers always remain on a circle centered at the origin, though this circle may (and should) shrink as time goes on. If the fugitive is at least $2/N$ from the circle containing the officers, then all officers move toward the origin by $\delta/N$. (continued) – Will Brian Apr 15 '21 at 12:54
  • If the fugitive is within $2/N$ of the circle containing the officers, then only one officer moves: the officer closest to the fugitive remains on the circle containing all the other officers, and otherwise moves to match the fugitive's motion up to some small error $\eta < \delta$ (i.e., the fugitive, officer, and origin should remain approximately colinear). The small error does not allow the fugitive to escape, but it does allow some leftover motion for the officers on each turn where the fugitive is near the edge. They use this leftover bit to shrink their circle slightly. – Will Brian Apr 15 '21 at 12:57
  • 1
    @mlk You can settle for a weaker "if" by just allowing 3 officers to move by $\delta$ each turn, because if the fugitive is in a convex hull, they're in a triangle too. I really wonder if allowing 2 officers to move is enough. (of course, if one officer is enough, the original result is proved) – Eric Apr 15 '21 at 13:03
  • 1
    @Eric Allowing 2 to move will at least require a different strategy, since their convex hull has no interior. 2 on their own will always loose. Even starting on their connecting line, the fugitive can run perpendicular to it and the best they can do is catch up without getting closer. So you'd somehow need to involve a third stationary policeman as well. This way, they can always keep the fugitive inside their convex hull, but getting it to shrink might be hard. – mlk Apr 15 '21 at 13:43
  • @WillBrian I don't quite follow this strategy. 1. Why N/2? 2. If $\delta$ is really small, how can the officer match the fugitive's motion, since they will be many moves away to the fugitive's left or right side? 3. How can a small error prevent the fugitive from escaping out of the circle? Are you assuming fixed $\delta$, instead of thinking of it as a function of $N$? – Eric Apr 15 '21 at 14:45
  • 1
    @Eric: 3. I'm thinking of $\delta$ as being small relative to $1/N$ (something like $1/10N$ or smaller). 1-2. Maybe $2/N$ is too small -- let's change that to $10/N$. Let's say the fugitive is approaching the ring of officers for the first time, so they're spaced evenly along the circle at intervals of $< 2\pi/N$. The fugitive moves to within $10/N$ of the officers, and the closest officer makes a line with the fugitive that's not too far off from normal to the circle (certainly $< \pi/4$). The officer just needs to move in a way that maintains or tightens this angle, and this prevents escape. – Will Brian Apr 15 '21 at 16:42
  • 1
    @WillBrian I think the fugitive F can escape: walk directly at some officer X until you are very close, then turn aside and walk out of the convex hull. Some details: As the fugitive walks, the adjacent officer Y on, say, the left, stays relatively far away. Let Z be the midpoint between X and Y. The angle FXZ stays at about $\pi/N$. But the angle XFZ is growing toward $\pi/2 - \pi/N$. Once the fugitive is close enough that the angle XFZ is greater than FXZ, the fugitive simply turns toward Z and leaves. He is closer to Z than any of the officers. – usul Apr 15 '21 at 18:03
  • Correction: angle FXZ stays at about $\tfrac{\pi}{2} - \tfrac{\pi}{N}$ (I think), while XFZ grows toward $\tfrac{\pi}{2} + \tfrac{\pi}{N}$. Apologies. – usul Apr 15 '21 at 19:02
  • @usul: The way I'm imagining it, X is moving closer to the point Z as F moves towards the circle containing the officers. This should prevent the angle XFZ from ever getting too close to $\pi/2$. – Will Brian Apr 15 '21 at 21:23
  • 2
    @WillBrian let us (and others!) continue in chat, try here: https://chat.stackexchange.com/rooms/123038/fugitive-game – usul Apr 15 '21 at 21:30
  • @WillBrian The point is the fugitive can turn either left or right. This illustration should make the point clear: https://puzzling.stackexchange.com/a/12690/68538 – Eric Apr 17 '21 at 02:36
  • You wrote: "For that purpose you can also replace the kings with power-one rooks (which can move only one square in four cardinal directions)." In fact the king version and the short-legged rook version are not the same, and neither looks trivial. – Alessandro Della Corte Apr 17 '21 at 17:22
  • @usul: OK, I finally see what you mean -- thanks for the picture -- and I think you're right. The strategy I outlined won't quite work. Still, it seems like a near miss. It seems like it would work if the officers could move just a tiny bit more on every turn. Which I suppose just makes the question, as phrased, all the more interesting. – Will Brian Apr 17 '21 at 18:17
  • 3
    In the power-one rook version, if two officer rooks can move per turn, then 4 officers can always capture the fugitive. – Pace Nielsen Apr 17 '21 at 20:25
  • 1
    @WillBrian If officers could move any tiny bit more, you only need one officer to catch the fugitive, without any fancy formations. – Eric Apr 18 '21 at 04:04
  • 1
    @mlk I think the "if" part of your proof is seriously flawed. For example, if the fugitive is close to the boundary of the hull, your method won't work. Even if the fugitive starts at the center of the hull, there's no guarantee. Let's say $\delta$ is very small, then officers are in fact tracing a pursuit curve (https://en.wikipedia.org/wiki/Pursuit_curve). For 3 officers on the vertices of an equilateral triangle, the fugitive escapes by walking along the normal to the line connecting 2 officers. For more officers, their movements can probably be manipulated to create a gap, too. – Eric Apr 19 '21 at 09:04
  • @Eric Maybe you are misunderstanding the proof. They aren't moving straight towards the fugitive, but try to keep the same heading first and only then spend any excess mobility in moving towards the fugitive. If the fugitive always moves in the same direction, this will result in straight lines for the officers as well, not pursuit curves. – mlk Apr 21 '21 at 08:00
  • @mlk Yes but when $\delta$ is very small, this doesn't matter much, and they're the same in the limit, right? The fugitive escapes the equilateral triangle in my previous comment, if $\delta$ is sufficiently small. – Eric Apr 21 '21 at 08:20
  • 1
    Is it équivalent to the problem with continuous (ans Lipzichian) and simultaneouss moves that satisfy the correct conditions for speed (condition on the sum of the norm of speeds)? – jcdornano Apr 21 '21 at 11:32
  • @Eric No, the direction is the same as the fugitive for all officers "behind" (wrt. to the direction he's moving) the fugitive. For all that are in front of the fugitive (and there is always at least one if the convex hull condition is met) the line each is moving on and the line the fugitive is moving on form the sides of an isosceles triangle, independent of $\delta$. Thus in particular they will meet if they continue in the same direction. – mlk Apr 21 '21 at 11:59
  • @mlk You're right. – Eric Apr 21 '21 at 14:58
  • When I say "Is it équivalent to the problem with continuous (ans Lipzichian) and simultaneouss moves that satisfy the correct conditions for speed (condition on the sum of the norm of speeds)?" I mean instead of dictating $\delta$, the fugitive dictate a neighbourhood around him that if a ploceman gets inside, policemen win – jcdornano Apr 21 '21 at 18:35
  • Imagine officer and fugitive are charged particules, all the same sign and intensity. Then what would give the strattegy for the fugitive to move according to his natural motion over repulsion forces? (I had this idea by trying to ponderate each officer according to a fonction of the inverse of its distance to fugitive and rake the barycentral point) i did not investigate, it is just a quick idea^^ – jcdornano Apr 22 '21 at 13:21
  • Of course If the fugitive is in an unstable equilibrium he can get caught if he follows this strattegy (officer can maintain him not moving!) so let's say that in this case only he will have to move infinitesimally to take a decision. The question if yes or no this strattegy works can be asked... (the way he moves if he is in equilibrium has to be fixed... but maybe, the strattegy is working for any arbitrary move to escape equilibrium...) – jcdornano Apr 22 '21 at 13:47
  • @jcdornano No, I don't think it works like that. – Eric Apr 22 '21 at 16:19
  • I'm pretty sure this idea is a good begin... the strattegy for the fugitive would be "in some sens" to go where he will fell less "tension". The tension would be mesured by the repulsion forces and should increse with the intensity of the "total repulsion" (sum of ponctual repulsion) but also with the unstability of the neighbourhoud , so that although the addition of repulsion forces is zéro in an unstable equilibrium, the " tension " should be non zéro. A fine "tension" might be "something like" the average of the modules of repultion forces in a small circle around the fugitive. – jcdornano Apr 22 '21 at 17:08
  • 1
    I just found another MO question that seems very similar. Also there is a book Graph Searching Games and Probabilistic Methods by Bonato and Prałat that seems potentially relevant. – Timothy Chow Apr 23 '21 at 00:28
  • If $C_0$ is the edge of the convex hull of the st $O$ of officers then let's call $C_1$ the edge of the convexe hull of $O- C_{0}$ and repete the process. Then $O$ is the nested union of convex polygons. It may be a good strattegy for F to escape one polygon at a time, as soon as of it stay convexe it is an easy case , the difficulty can come if there is a break of the convexeity, but I feel that it does not seem too problematic. – jcdornano Apr 23 '21 at 23:49
  • @TimothyChow Yes, thanks for the link. I found there's a whole genre of well researched games called (infinite) cops and robbers that are isomorphic to the chess version of my game. – Eric Apr 24 '21 at 02:58
  • @Eric The book I mentioned, Graph Searching Games and Probabilistic Methods by Bonato and Prałat, has a whole chapter devoted to cops and robbers, and many other chapters devoted to related games. – Timothy Chow Apr 24 '21 at 03:54
  • Let's say F is p-winning if he's able to anounce the integer $p$ before the game began, and he's aloud to decrease the value of the maximum distance of move at most $p$ time. I'm convinced that it is always possible for the fugitive to $p$-win for some $p$. And I think it may not be to hard to deduce from this a 1- winning strattegy. I posted an answer "by mistake" this morning, because I was on my phone and I miss clicked, I will post it if I can prove the general game, not only the $p$-winning idea that was my first aim (but now I've got ideas to go futher, so I wait a bit before posing) – jcdornano Apr 25 '21 at 14:47

2 Answers2

14

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!

Eric
  • 2,601
Pace Nielsen
  • 18,047
  • 4
  • 72
  • 133
  • Very nice! Any thoughts on modifying this scheme with 6 officers / a hexagon? – usul Apr 19 '21 at 16:34
  • @usul No idea how to improve it. The idea came from thinking about the rook version. Perhaps someone who plays hexagonal games will have another idea. – Pace Nielsen Apr 19 '21 at 17:00
  • 5
    @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$. – Will Sawin Apr 20 '21 at 02:52
  • If officers lag a little behind, the fugitive can deviate from the diagonal. What are officers to do then? Are you sure they can still squeeze as much as they want over a finite period of time? – Eric Apr 20 '21 at 03:15
  • @Eric The more he goes off diagonal, then more extra movement speed they get to catch up and box him in. The larger the box, the smaller the lag, so tit only takes a tiny amount of deviation from the diagonal to catch back up. – Pace Nielsen Apr 20 '21 at 05:48
  • @WillSawin Go ahead and turn my answer into a community answer, and update it with your solution. (I bet you could get c=2 as well, throwing in a slight lagging argument.) – Pace Nielsen Apr 20 '21 at 05:51
  • Without the lag they can surely use that extra movement to shrink the box. But now they have to shrink and close the lag in time. I do think the situation is very subtle here. But even without shrinking, lagging can be problematic. For example, if $2\delta$ divides the diagonal of the starting rectangle of the officers, then any lag will prevent the officers to capture the fugitive at the diagonal corner. – Eric Apr 20 '21 at 11:53
  • @Eric this makes sense. To clarify, you agree with $c > 2\sqrt{2}$, but are questioning $c=2\sqrt{2}$? – usul Apr 20 '21 at 12:10
  • @usul Yes, the boundary cases are bound to be tricky, and lagging dicey. In fact, $2 \sqrt2$ won't work even if you place four additional officers to guard the corners. – Eric Apr 20 '21 at 12:20
  • 2
    @PaceNielsen 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. – Will Sawin Apr 20 '21 at 13:21
  • @Eric This is somewhat moot now that Will has a better constant, but it isn't as hard as you make it. First, let's agree that once they lag a bit, they no longer ever shrink the box, but work to only catch up. Second, I'll leave it to you to show that if the fugitive gets too close to one of the corners, then the two officers close-by can use all the movement speed and catch the fugitive. So, the only question is whether or not the fugitive can veer off course and avoid the corner, while also not giving the officers enough extra movement speed (because he didn't go diagonal) for them to... – Pace Nielsen Apr 20 '21 at 15:47
  • ...catch up. Any movement off diagonal gives the officers extra movement speed. So if the lag of each officer is $\epsilon$, they can choose this $\epsilon$ (depending on the box size, and depending which diagonal the fugitive chooses to follow) small enough so that the fugitive cannot leave the diagonal far enough to get away from the corner sufficiently far to avoid capture. – Pace Nielsen Apr 20 '21 at 15:52
  • @WillSawin Regarding your question: Suppose the fugitive only moves parallel to one edge. The officer on that parallel edge has to use his full movement speed just to maintain his (extremely small) lag. The other two officers have a bit more freedom, especially the one opposite his movement, but let's ignore that and suppose they also use the rest of the speed just to maintain their lag. When the fugitive gets sufficiently close to an edge the officer on that edge can just deviate and catch him. – Pace Nielsen Apr 20 '21 at 16:03
  • 2
    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. – Eric Apr 20 '21 at 16:28
  • @Eric For a lower bound, I'd start by assuming the officers are equally spaced on a perfect circle. Generic configurations sound very difficult! – usul Apr 20 '21 at 19:21
  • @usul Here's an answer (a long one, scroll to the end) that proves if $c\lt 1$ then the fugitive escapes: https://mathoverflow.net/a/328213/75935 – Eric Apr 23 '21 at 11:17
  • Pace Nielsen, strictly speaking, the strattegy you posted in your answer is winning for the fugitive ... if he never moves... – jcdornano Apr 23 '21 at 13:13
  • Same if the fugitive moves are $\epsilon^{-n}$ to move $n$ for a small enough fixed $\epsilon$ – jcdornano Apr 23 '21 at 13:59
  • @jcdornano If the fugitive doesn't move, the officers use all their speed to shrink the net. – Pace Nielsen Apr 23 '21 at 14:09
  • 1
    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 – jcdornano Apr 23 '21 at 14:54
  • I think this strattegy is not working anymore if c=2 but officers move are strictly less than $\delta$. Because if F is not moving, and the officer are shrinking the net, then F will décide to move if and only officer are at a distance that is at most $\delta$, as soon at the distance is less , F jumps out, and the cortical case is when the distance is exactly $\delta$, then he will be caught for sure if and only if one officer is cloud to move $\delta$. – jcdornano Apr 23 '21 at 15:34
  • I even think that the the fact that one officer is aloud to move exactly delta is better for them than any $c$-game for $c$ as big as we want , but with the condition that each officer moves canot be more than $\delta-\epsilon $ for any $\epsilon>0$ ... – jcdornano Apr 23 '21 at 15:42
  • Indeed, it is the case. It can ne deduced from the proof I gave un my answer. As well as the case $c<2$. – jcdornano May 26 '21 at 19:05
1

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.

jcdornano
  • 469