7
$\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 d.
  • In an officer move, the sum of distances travelled by all officers can be no more than d.

The fugitive is caught if their distance to some officer is 0 in finite moves, otherwise they escape.

Question: Given N, is there always some $d \gt 0$ for which the fugitive can escape, regardless of the officers' initial distribution?


Related: One king vs many. Can white force a draw? (discrete version dual problem)

$\endgroup$
6
  • $\begingroup$ Can the officers occupy the same area as each other (distance of 0)? Can all the officers start a distance of 1 away, or only one? $\endgroup$
    – bobble
    Apr 14, 2021 at 3:44
  • $\begingroup$ @bobble They can occupy the same spot. All of them can start at distance 1 away. $\endgroup$
    – Eric
    Apr 14, 2021 at 3:50
  • 2
    $\begingroup$ I'm having trouble parsing the quantifiers on your question here - is it "Given some fixed N, is there a single d that works for every distribution of N officers", or "can you find a d for any particular distribution of officers"? (Also, I assume that d is required to be positive?) $\endgroup$
    – Deusovi
    Apr 14, 2021 at 4:20
  • $\begingroup$ @Deusovi It's the former, and of course d is positive. $\endgroup$
    – Eric
    Apr 14, 2021 at 5:07
  • $\begingroup$ I assume all players are on a continuous plane and not on some sort of grid/lattice ? $\endgroup$
    – JimN
    Apr 14, 2021 at 10:52

2 Answers 2

2
$\begingroup$

Partial answer (a crude upper bound):

for sufficiently large $N$ (at least, it works for magnitudes of about $20$), if such $d$ exists, it must be $$d<\frac{2}{\sqrt3}\sin\frac\pi N$$

Because

Assume that the officers stand on the unit circle in the vertices of a regular $N$-gon inscribed into that circle. The distance between the officers than will be $2 \sin\frac\pi N$, the side length of such a polygon.
On the other side, if the distance between officers is $d\sqrt3$ or less (i.e. when $d$ is too large), then the common chord of the 2 circles with radii $d$ centered on the adjacent officers will have length of $d$ or greater, so the fugitive cannot pass inbetween these officers to cross the boundary. So, $2\sin\frac\pi N > d\sqrt3$, and we have the bound for $d$ written above.
OF course, the $d>1$ case won't work for sufficiently large value of $N$, since after making the first move, the fugitive will be at a distance of $d-1$ from the circle, and $d-1+\varepsilon$ from the closest officer, where $\varepsilon$ is much less then 1 for large $N$, so the fugitive will be caught next move.

$\endgroup$
0
$\begingroup$

No, the fugitive cannot escape with large N

Assume an arbitrarily large number of officers surrounding the fugitive, all standing 1 unit away from the fugitive on the perimeter of the unit circle centered on the fugitive. The fugitive cannot end his move within distance d of any officer, or that officer can catch him next turn.

In the limit of an infinite number of officers, the "disallowed" region for the fugitive is an annulus with width 2d. The fugitive cannot cross a width of 2d in a single move if his maximum move length is d. If d > 1, the "disallowed" region is a circle of radius d+1, which also cannot be escaped with a single move of length d.

NOTE: This reasoning is incorrect, as you can always pick d smaller than half the distance between officers, so that the "disallowed" region is just a series of circles and not an annulus. There can always be a viable escape path in the initial configuration, so long as d is small enough.

$\endgroup$
3
  • 2
    $\begingroup$ The value of $d$ can depend on $N$. If $d$ is small enough (much less than the spacing between officers), this strategy may not work, as far a I can see. However, it does not mean that the officers can act in some other way (they can move too etc.) $\endgroup$
    – trolley813
    Apr 14, 2021 at 16:44
  • 1
    $\begingroup$ @trolley813 Hmm, very good point. Regardless of N, you can always make the "disallowed" region not an annulus by picking small enough d, so that premise is incorrect. There can always be a "hole" to escape in the initial configuration. $\endgroup$ Apr 14, 2021 at 16:59
  • 1
    $\begingroup$ But at least, this strategy provides an upper bound (I'm writing my own answer about it). $\endgroup$
    – trolley813
    Apr 14, 2021 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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