Skip to main content
2 of 4
added 291 characters in body
Will Sawin
  • 148.5k
  • 9
  • 324
  • 563

If any officer can move more than $\delta$, then that officer can simply chase down the fugitive. Thus, I propose modifying the question to ask: If each officer can move at most distance $\delta$, but they all pull from a given pool of movement of size $c\delta$, then how small can $c$ be such that they can always catch the fugitive?

I claim that any constant $c>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