Skip to main content
4 of 4
deleted 10 characters in body
Eric
  • 2.6k
  • 1
  • 23
  • 25

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!

Pace Nielsen
  • 18.7k
  • 4
  • 75
  • 137