19
$\begingroup$

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.

A 4x4 grid of points, where each point is connected by a line to the points horizontally and vertically adjacent, with the Cop on the point at the lower right corner of the grid

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?

$\endgroup$
14
  • 1
    $\begingroup$ Can the thief reverse direction during the traversal of an edge, or only when at one of the vertices? $\endgroup$ Apr 21 at 13:55
  • 3
    $\begingroup$ @JaapScherphuis No restriction. He can reverse anywhere. $\endgroup$
    – Eric
    Apr 21 at 13:58
  • 4
    $\begingroup$ @IvoBeckers No, Invisibility of the thief IS the pith of the puzzle! In fact, I'll soon edit the puzzle to make it more interesting: not only is the thief invisible throughout (so the cop doesn't even know where he is to start with), but he's also prescient (i.e. perfectly predicts every future movement of the cop). $\endgroup$
    – Eric
    Apr 22 at 6:23
  • 1
    $\begingroup$ Does the cop know the speed of the thief or does it not matter? $\endgroup$
    – hkBst
    Apr 22 at 10:24
  • 1
    $\begingroup$ @hkBst Good question. He does. $\endgroup$
    – Eric
    Apr 22 at 10:29

9 Answers 9

6
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ I've edited the question to make it even more interesting. $\endgroup$
    – Eric
    Apr 22 at 7:07
  • $\begingroup$ I think your analysis is correct after all. Even without the Oracle, the cop can only catch the thief probabilistically, not for certain in finite time. $\endgroup$
    – Eric
    Apr 22 at 16:03
  • 2
    $\begingroup$ I don't think ralphmerridew actually disproved your proposed strategy for the thief. I think you've correctly shown that if the thief reaches an intersection of 3 or more edges, the cop has lost and will never catch the thief no matter how slow the thief is. Therefore, the cop must be sufficiently fast to catch the thief before the thief can reach an intersection of 3 or more edges. $\endgroup$ Apr 22 at 16:13
  • 1
    $\begingroup$ @Shufflepants Yes ralphmerridew did disprove my strategy. It is possible to visit the branches in an infinite sequence of decreasing incusions that forces a (slow) thief to end up in the center at the same time as the cop. $\endgroup$
    – Florian F
    Apr 22 at 22:25
  • 1
    $\begingroup$ @Shufflepants after $\frac{1}{1-r}$ distance is travelled by the cop, which happens at time $\frac{1}{(1-r)S_c}$, the super-task ends, with the thief being caught at the intersection. $\endgroup$
    – justhalf
    Apr 24 at 8:59
5
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ More weirdly, you can start from 0 and increase the excursions with r>1. You can prove by continuity that for the thief to be still near the intersection, he must have been at the intersection with you. You already caught him. $\endgroup$
    – Florian F
    Apr 22 at 6:24
  • 2
    $\begingroup$ Well, $S_c > 7S_t$ might be a big advantage for the cop, but being invisible is gigantic advantage for the thief. It balances out. puzzling.stackexchange.com/questions/36565/… required $S_c > 2*S_t$ in a smaller town where he could see the thief. $\endgroup$ Apr 22 at 11:14
  • 3
    $\begingroup$ Every round, the cop completes his circuit of some finite distance in some finite time. If the thief uses the same strategy going north first and moves just 1/7th the distance the cop does down each road, he completes his circuit in the exact same amount of time as the cop and always stays one road ahead of the cop. If he moves just slightly less than 1/7th the distance on the first road, he'll avoid meeting the cop at the intersection too. By the time the cop goes north, the thief is going east, by the time the cop goes east the thief is going south, etc... $\endgroup$ Apr 22 at 15:18
  • 4
    $\begingroup$ Because the rounds get shorter and shorter, it's possible for the cop to do infinitely many rounds in finite time. After the cop completes round $k$, the thief cannot be more than $r^k$ from the center. After all rounds, the thief can not be any positive distance from the center; he would have been captured in a previous round if he had. The thief can only be at the origin, which is where the cop is. Book 'em, Danno. $\endgroup$ Apr 22 at 17:31
  • 2
    $\begingroup$ @Shufflepants the cop's path It is a perfectly well-defined function. It is not differentiable, though. So the direction of the cop at the end is undefined. But that doesn't matter. $\endgroup$
    – Florian F
    Apr 23 at 9:31
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
1
  • 2
    $\begingroup$ OBJECTION! I have considered the idea but ralphmerridew has shown it can be defeated. Please don't cite me for what I do not say. $\endgroup$
    – Florian F
    Apr 24 at 15:00
2
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ @Eric Indeed. Even without the Oracle, it's possible that the thief does exactly what he would have done if he had it, by chance alone. The Oracle doesn't allow any new moves for the thief that can't be done without it. I would imagine that without the Oracle the thief would likely eventually be caught, although if it's possible for the thief to evade with the Oracle, it's still possible for him to evade without it. $\endgroup$ Apr 22 at 16:03
  • 1
    $\begingroup$ Yes, it's easy to prove without the Oracle, the probability that the thief gets caught goes to 1 as time approaches to infinity, if the cop just chooses random direction at each junction. $\endgroup$
    – Eric
    Apr 22 at 16:13
  • 1
    $\begingroup$ @justhalf I am intrigued by that answer and think it may be correct. I think I've shown here that the thief can always be on a different edge than the cop, although ralph shows that the distance along the edge from the intersection can be forced to zero in finite time. Qualitatively the cop and thief can be on different edges, but I'm no longer sure that's a useful description when the distance from the intersection goes to zero (is that "on an edge"?). We seem to wind up with Zeno's paradox, where there's no identifiable round where the two meet, yet they still do after finite time. $\endgroup$ Apr 22 at 19:33
  • 2
    $\begingroup$ Yep, agree with you here. This happens a lot in this kind of problem. The last time I encountered this "paradox" is on this question: puzzling.stackexchange.com/questions/111335/… $\endgroup$
    – justhalf
    Apr 22 at 19:36
  • 1
    $\begingroup$ Indeed, by justhalf's arugment this nice strategy actually doesn't work... Both points may converge to a single point in finite time. The thief has to have more tricks up his sleeves. $\endgroup$
    – Eric
    Apr 23 at 11:26
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Nice attempt, this is how I thought about it as well. $\endgroup$
    – justhalf
    Apr 22 at 19:34
  • $\begingroup$ How large must the "immediate vicinity" be? The thief is omniscient, so he could be still be around somewhere not far away from the vertex. How do you deal with that? $\endgroup$
    – Eric
    Apr 24 at 1:14
  • $\begingroup$ @Eric Well, mathy way of handling it would be to pick any small-ish number like 0.01 away from the corner, then do the iteration with that distance going to 0 in steps where thief starting from beyond 0.01 couldn't have reached the corner. (I find it somewhat cleaner to do the inverse and go from the center, but obviously you can formalize the "go from outside towards center" much better). Zeno paradox is only a limitation of some people not realizing infinite series can converge to a finite number. $\endgroup$ Apr 24 at 18:26
1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ "What should be the maximum value of St where..." I believe you meant to say minimum value. Why can't that value be 1? $\endgroup$
    – Eric
    Apr 22 at 9:52
  • 2
    $\begingroup$ But the thief doesn't have to go to the "next corner", he can stay an arbitrarily small distance from a 4-way intersection. No matter how fast the cop moves relative to the thief, the thief can change roads before the cop gets there. This strategy seems to be to sweep all roads fast enough that the thief is "stationary", but the thief can change what road he's on in arbitrarily little time, so it seems to me there is no speed for the cop which makes the thief unable to evade. $\endgroup$ Apr 22 at 15:11
  • 2
    $\begingroup$ @JaapScherphuis There is no "next intersection", the thief can turn around anywhere on the edge and return to the same intersection. As the cop explores the 1st edge, the thief can be on the 2nd, but by the time the cop starts to explore the 2nd the thief can be on the 3rd, and so on. If the cop moves at 8x the speed, the thief just needs to move 1/8th the distance, and will move from edge to edge at the same rate as the cop. No matter how quickly the cop can walk all the edges, the thief can move between edges faster than that by staying close enough to the intersection. $\endgroup$ Apr 22 at 19:01
  • $\begingroup$ I guess this is the distinction between finite number of times traversing the intersection vs infinite number of times. As ralph's showed, if the cop moves in the way they described, after $\frac{1}{1-r}$ distance is traversed by the cop using the strategy described, the thief would have already been caught (and the cop would have passed the intersection infinitely many times; no, not just a very large number, but truly infinite). $\endgroup$
    – justhalf
    Apr 22 at 19:27
0
$\begingroup$

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

$\endgroup$
13
  • 1
    $\begingroup$ Well, counter example is easy since we can specify the thief to have a very slow speed, for example (1/3) x cop speed. If the cop is on the corner next to the thief, then if the cop's next corner is to go to the corner the thief currently is, the thief can't outrun the cop who simply goes straight to the corner and turn. The thief will be caught at the middle of the side. $\endgroup$
    – justhalf
    Apr 22 at 8:04
  • $\begingroup$ @justhalf you don't get to specify the speed of thief. the thief's speed could very well be 0.9999999 the speed of the cop. If you could specify it you might as well say: The thief's speed is 0.000000000001 the speed of the cop and the cop just walks all the streets once $\endgroup$ Apr 22 at 8:06
  • $\begingroup$ Well, I can, because your solution doesn't specify that it works only for thief speed greater than x, for some x. So it must work for any thief speed. You can tighten your answer by specifying that when thief speed is less than x1, they will be caught [in this way], if it's greater, they may not be caught by [this way], similar to ralph's partial answer. For example, Florian's acknowledged that their strategy is countered by ralph's example, even though ralph specifies the thief speed. $\endgroup$
    – justhalf
    Apr 22 at 8:10
  • $\begingroup$ @justhalf that's not how it works. It's the cop's job to find a strategy that works for any speed <1. Me providing a strategy for the thief a speed of my choice, like 0.999999, is enough to disprove the cop being able to catch him. And ralph doesn't even specify any speeds $\endgroup$ Apr 22 at 8:12
  • 2
    $\begingroup$ @Eric if I'm right about this, maybe a very interesting question would be: what's the minimal thief speed required for outrunning the cop? $\endgroup$ Apr 22 at 8:39
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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