1
$\begingroup$

The fugitive is at the origin. He moves at a speed of 100. You have a guard at every integer coordinate except the origin. A guard's speed is 1. The fugitive and your guards move simultaneously and continuously. If he's within 1/100 distance from a guard, the fugitive is caught and you win the game.

enter image description here

What's your strategy for catching the fugitive in the shortest amount of time?

Hint

Needless to say, you need to control your guards' movement strategically in order to catch the fugitive at all.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

A heuristic argument to see which ball park we'll likely be talking about:

To make a tight wall we need 50 guards per unit length, so if we recruit opportunistically we'll deplete a +/- 25 strip around the prospective wall with the farthest away cops arriving after 25 seconds.

The fugitive can travel 2,500 units in that time, so we can reliably and without any micro management trap them by setting up a perimeter of roughly that radius.

If we do only that and not use the cops that are also trapped within the perimeter we need another 2,500 seconds to collapse the perimeter into the centre.

But we can clearly do much better by setting up additional concentric rings at roughly 50 units distance (limited by available cops). After 25 seconds the fugitive will be trapped between two rings and have to surrender after another 50 seconds.

We can probably further improve the second phase by packing the rings a bit denser (at modest cost during phase one) such that the inner ring can expand.

Can we do much better?

Unlikely, as the fugitive can safely pass anywhere the local density is appreciably below 50. It may be possible to reduce the 2,500 radius a bit by micro management but certainly not by a large factor.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Since you trap the fugitive between walls, you don't need to make them circular. This simplifies the calculations. You can pack guards into horizontal walls every 50 units. You need 25s to build the walls and 25s to squeeze the fugitive between 2 walls. $\endgroup$
    – Florian F
    May 3, 2021 at 14:35

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.