Catch the invisible and omniscient thief

Question

The thief has stolen two powerful artifacts: the Cloak of Invisibility and the Glasses of the Oracle. Now they're equipped with both. The cop at the bottom, not knowing where the thief is, is trying to catch them.

The cop and the thief are points moving on the grid. Cop speed $S_c=1$, thief speed $S_t\lt 1$. The cop catches the thief if both points coincide.

Does the cop have a strategy that guarantees catching the thief in finite time?

---

Hint

For a change of perspective, think of it this way: the roads are covered by weeds, you're moving at speed 1 with a lawnmower to get rid of them. Once mown, the weeds never grow back, but unmown weeds will spread at speed $S_t$ in every direction along the road. What's the maximum $S_t$ such that you can accomplish your mission?

Answer 1

I have to remove my post about the idea of escaping the cop by hanging around an intesection. Despite concluding that it is in fact not valid, people still refer to it as valid

Instead, as explained by ralphmerridew, the thief cannot escape the cop by hanging around a corner.

Answer 2

Just to show that dodging around the intersection isn't enough, consider the simpler city when there is just one intersection, four roads that go a unit distance away from it, and $S_c > 7*S_t$.

Let $r = 6*S_t / (S_c - S_t)$. Since $S_c > 7*S_t$, $r < 1$.

1. Start at the center.
2. In round $k$, starting from round 0: go west $r^k$, return to center, north $r^k$, return to center, east $r^k$, return, south $r^k$, return to center.

• If the thief is ever on the same road as the cop, he will be caught that round:
  -- The cop has gone at most $6*r^{k-1} + r^k$ from when he last left that road until he turns back.
  -- $6*r^{k-1} + r^k = r^{k-1} * (6 + r)$
  -- $ = r^{k-1} (6 + r) * (S_c - S_t) / (S_c - S_t)$
  -- $ = r^{k-1} (6*(S_c - S_t) + r*(S_c - S_t)) / (S_c - S_t)$
  -- $ = r^{k-1} (6*S_c - 6*S_t + 6*S_t) / (S_c - S_t)$
  -- $ = r^{k-1} ((6*S_c) / (S_c - S_t))$
  -- $ = r^{k-1} (r * S_c / S_t)$
  -- $ = r^k * (S_c / S_t)$ -- During that time, the thief can only go $(r^k * S_c / S_t) * (S_t / S_c) = r^k$ away from the center.

• On the other hand, if the thief keeps dodging around the center, the lengths of the rounds decrease geometrically, so it ends in finite time.

I'm not sure if it's possible to expand that strategy to win on the full city, though.

Answer 3

When $S_c<2S_t$ thief can escape by moving around a single intersection.

There have been some incorrect answers that this strategy is always possible regardless of $S_c$, but @ralphmerridew shows a correct proof that when $S_c>7S_t$ then actually cop will win when playing on one intersection (i.e. 5 vertices, 1 of which is connected to all the remaining ones).

So let us begin. For simplicity assume $S_c=1$. I will work in the setting of lawnmower and weed, see the spoiler in the original post for an explanation of this (but I will use the word cop since lawnmower is awfully long). Let us call 4 non-central vertices endpoints and call them $A,B,C,D$ and call midpoints of edges $A',B',C',D'$. Finally, let us denote edges by $a,b,c,d$ and denote center by $S$. I will show that it is essentially impossible for the cop to achieve the situation when he is in the center and more than 1 endpoint is clear or more than 2 half branches are clear.

We can give the cop a handicap and assume that the only infected points are $A$, $A'$, $B$, $B'$, $C$ - we will show that it cannot get essentially better than this when the cop returns to the center. The cop can hang around the center and gain nothing, at some point he will need to do an excursion to $A'$, $B'$ or $C$ to kill weed at those vertices. Assume the first excursion will go to $A$ (i.e. cop leaves $S$ and doesn't come back to $S$ until $A$ is cleared). This takes him the time of at least 2 units of time and this is sufficient to recover weed on whole $b$ and $c$. In fact, weed from $B'$ will even have time to reach $D'$ by the time cop is back in $S$. So, when the cop finally returns to $S$, the situation is as follows (or worse): $a$ is clear, $b$ and $c$ are covered with weed, $D'D$ is clear, but $SD'$ is covered with weed. Note that this state is equivalent to the state when also $D$ is infected since the cop is not fast enough to reach the frontier of weed on $d$. That is, to have $d$ cleared there is no other way than to mown entire $d$ from scratch, so we can assume without loss of generality that $D$ is in fact infected. Hence the situation of the cop is strictly worse than at the beginning, so the excursion to $A$ was not a good idea.

Hence assume cop does excursion to $C'$ instead (i.e. leaves $S$ and returns to $S$ no sooner than $C'$ is clear. But this gives enough time for weed to spread from $D$ to $D'$ and hence the situation is identical to where we started from. Thus, cop will never clear the whole weed.

Fun fact (partially related to the puzzle). What if the thief has infinite speed, but there is more than one cop (cops communicate with each other and work together)?

We need at least 5 cops - since treewidth of our graph is 4. This is a surprisingly important question in general mathematics.

Answer 4

As Florian F established, if the thief is able to reach the center of an intersection that has three or more edges, the cop cannot ever catch the thief as the thief can always dance around the center, always stepping just off the center to allow the cop to pass, then returning to center and jumping off again only to let the cop pass if the cop returns.

If the thief starts in the opposite corner, the cop would have to have a speed at least 7 times greater than the thief so that the cop could completely clear out the entire length of the corner branch before the thief can reach an intersection. That is, with the intersections of the graph labelled with cartesian coordinates with (0,0) being in the bottom left, if the thief starts at (0,3) and the cop starts at (3,0). The cop could take the path (3,0) -> (2,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3). This way the cop would catch the thief before the thief can reach an intersection no matter whether the thief started heading towards (0,2) or (1,3) initially.

If the thief starts in a corner, but the cop doesn't know which one, the cop would need a speed of at least 10 times as fast as the thief to clear each of the corner areas before the thief can make it to an intersection.

If the thief starts in some arbitrary and unknown part of the grid. The cop would need to completely cover every edge of the city (performing a route inspection) in less time than it takes the thief to reach the nearest intersection that has 3 or more edges. The shortest route inspection I can find which clears the corners has a path length of 26. So, if we take $d_i$ to be the distance the thief starts from the nearest intersection with 3 or more edges, the cop needs to be fast enough to cover a distance of 26 in the same amount of time it takes the thief to cover a distance of $d_i$. So, $S_c >= 26*S_t / d_i$

Answer 5

The cop cannot catch the thief.

Suppose the thief stands at a 4-way intersection. Whenever the cop approaches, the thief just needs to step an arbitrarily small distance onto one of the roads the cop isn't using. Because of the oracle, the thief knows exactly when the cop will arrive back at either the intersection, or the thief's new position. The thief just needs to make sure he's back at the intersection before that occurs, and can easily do so by stepping a small enough distance off the intersection in the first place - the thief can always return to the intersection before the cop does, because the thief knows in advance exactly how long he has to get back. No matter what finite time the cop takes to return to the intersection, the thief can get there slightly faster just by moving a shorter distance.

The thief can successfully evade forever by moving a total distance arbitrarily close to 0, so the ratio of the speed of the cop and thief is irrelevant. No matter how fast the cop moves, he cannot make the thief "stationary", as the thief can change what road he's on in arbitrarily little time. The thief could only ever be caught on one of the roads and never the intersection, but the thief can always get to the intersection in arbitrarily little time, and can in fact stay at the intersection arbitrarily close to 100% of the time.

EDIT: I no longer think this is correct. Although the cop and thief can remain on different edges, that may not imply they are separated by non-zero distance. After all, the edges themselves are distinct, yet are separated by exactly 0 distance by the intersection point. I'm not exactly sure how to think about this - two edges on opposite sides of a vertex don't touch because they are separated by the vertex itself, although I can't reconcile that with the notion that the edges are separated by exactly zero distance, the width of the vertex itself. The thief can always keep the vertex between him and the cop, but I suppose will still be caught because the vertex had no width.

Answer 6

Cop CAN catch the thief ... but only if he is MUCH faster - 20.5 times faster.

Lets invert numbers and say thief speed and set to 1, and v is cop speed. Easier for me that way. Vertices are labeled A1-D4, roads are labeled BC3 meaning road from B3 to C3 and B12 meaning road from B1 to B2. There are 16 vertices and 24 roads in total.

Let's start with vertex D4 where the cop starts. If the cop has speed 4, it is trivial to show that by going from C4 through D4 to D3 and back, thief can never reach D4 again. So, this patrol route at the cop speed 4 or greater is sufficient to make D4 safe forever. Now, we want to add D3 to the mix. Securing vertices is explained later, the first part is for patrol only - we want to know only how long it takes to ensure thief cannot ever reach D3 again. Securing means that the thief starts at D2, C3 or C4 (or further out) at any time of cop patrol (he might get closer during the patrol though). Required speed for cop's patrol is simple to calculate. Cop going the route 2xCD4, D34, 2xD23, 2xCD3, D34 leaves the cop back at D4 with full knowledge that if he manages to keep repeating that route with speed of at least 8 (the number of road travels), thief won't ever get to D3 or D4 again. Suppose thief started from D2 just behind cop's back - by the time thief would manage to reach D3, cop is already walking on D23 road (in case of speed 8 he just reached D3 to start on that route at the same time as thief).

OK, where now?

Is it better to add D2 or C4 to secured pieces? I don't know. We can try pushing thief up first, then left, or both at the same pace. But initial greedy algorithm might not be good. Let's assume we have secured the whole C and D, and are trying to prevent thief from ever going back there. It is fairly simple to extend the above movement to show speed of 14 is required to go 2xBC1, C12, 2xBC2 ... then return C34, C23, C12. There is no need to ever walk on roads CD or D, thief cannot be down there. Then we obviously add B4 to the stable of safe parts. Adding B4 among safe spots allows for patrol in same time, just going from C3 to B3 then B4 then up to A4 then back again. Same for adding other parts.

All in all,

This strategy of slowly expanding safe spaces guarantees full coverage of all the secured part with the speed of 14.

However,

This is only for patrol. Cop needs some time allocated to secure some vertices. It is trivial to secure D1 and A4 - mere patrol covers that already. It is annoying to secure B2, B3, C2, C3. Those on the edge are in between these two, so the worst case is securing the ones in the center. Suppose we want to secure B3 now. We know that C3 and B4 are safe, B2 and A3 aren't.

How much more time we need for that?

While we know 2 of these vertices are safe, thief might still duck on that road briefly, only to return to the center. Say we just reached B3 from C3 during regular patrol. We first travel to B4. Then return to B3. Thief might have managed at most few steps towards C3 (at most 2/v), so we go first towards C3 by the sufficient amount to catch the thief, then back to B3, then B4 etc, until we know thief cannot be found on the roads BC3 or B34.

Then

We secure roads B23 and AB3. We first start with those tiny little steps in ALL 4 directions - go up towards A3 by infinitely small amount, then back to B3, then repeat for B2, B4, C3, increase the infinitely small amount a little bit etc. So, we know thief is not directly next to C3 now - our infinitely small steps would have caught him. We also know he isn't on the roads BC3 or B34, we checked those two roads before. So, we go on the road AB3 - just far enough to get back to B3 before thief if thief is hiding on the road B23. Then we go on the road B23, this time we can go further, etc, until we manage to reach B2 and A3 spots. When we reached those two, B3 is secured - thief cannot get to the B3 again.

How much time did that take?

Well ... the initial road securing took 2 extra travels on the road B34 (there and back; remember we reached B3 from C3 so that road is safe), then 4/v (2x 2/v) travels towards C3, then 2x 4/v^2 towards B4 etc, continue with the infinite sum ... As v is large (we know it has to be at least 16 - 14 + those 2 extra travels), this drops towards 0 rapidly - the whole infinite sum is less than 1/2.

Then

Securing the other two roads is essentially 4 extra travels (2x B23 + 2x AB3) plus the same infinite sum (except we go from the center out, but the sum is the same), plus infinitely many steps with infinitely small time securing the immediate vicinity of C3. Seeing need for 20 speed without the infinite sum parts, term 4/v is mere 1/5 and the next term is 8/400 = 0.02, so we can safely claim cop speed of 20.5 is sufficient to catch the thief. 14 for patrol, 6.5 for securing.

Adding all together,

Strategy lets the cop catch the thief if his speed is approximately 20.5 times higher than the thief's. Note that this might not be the most optimal strategy, but I doubt any strategy where speed is below 20 is feasible.

Note

That speed of 20.5 lets you ever increase amount of space covered. During any patrol cop's coverage increases by at least 1 square, therefore cop will take at most 20.5 * 16 roads to catch the thief. Most likely way fewer because it is easier to secure edges and corners; but I cannot be bothered to search for the minimum time needed.

Answer 7

I believe the answer

depending on the value of $S_t$

if $S_t$

is small enough, the cop will catch him by covering all area strategy. For example if the $S_t$ is small enough not able to move to the next corner while the cop covers all area with the $S_c$.

if $S_t$

is big enough, thief will always find a way to run away from the cope with the items he has.

I believe the more original question would be

What should be the maximum value of $S_t$ where the cop cannot catch the thief whatever the strategy the cop follows?

Answer 8

I think the answer is

No

For this reason:

Just consider the 4 corners of the map. Because the thief knows where the cop will go, he will know at all times what the next 2 corners are the cop will visit. The thief will travel to any of the other 2 corners and waits there until the cop reaches the 2nd corner. And then repeats this strategy. Now I'm not sure how to prove it, but I'm convinced that the thief can always travel to such a corner so that: 1) he reaches it before the cop reaches 2 other corners 2) he can avoid running into the cop. But I would love to see a counter example

Answer 9

No.

You need to constrain the thief's speed to a smaller domain or proving failure is trivial. Suppose there exist only four points on the grid, the thief's position is known to the cop, and the cop starts one unit away from the thief. Then the time to catch the thief is $1/(S_c-S_t)$.

$\lim \limits_{S_t \to S_c^-} S_t \in \{ S_t : S_t \lt S_c \}$

$\lim \limits_{S_t \to S_c^-} \frac {1}{S_c-S_t} \to \infty$