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?

Can the thief reverse direction during the traversal of an edge, or only when at one of the vertices? — Jaap Scherphuis, Apr 21 '22 at 13:55
It appears the cop has to move much faster than the thief. Even just having a central point connected to four other points a unit distance away appears to require him to move more than 7x the speed of the thief. — ralphmerridew, Apr 21 '22 at 21:05
Just to make clear: being invisible is not part of the puzzle right? Because the cop never being able to see the thief I think would mean the thief never gets caught no matter the speeds. Actually, though it's not stated, I think we need to assume that the cop knows where the thief is at all times, right? — Ivo, Apr 22 '22 at 06:18
I think the cop not being able to see the thief is also a valid puzzle. There are some puzzles where we don't know the current location of some goals, but we can ensure that by some time T we would have already found our goal. Not sure whether it's solvable for this one, but doesn't seem unreasonable to assume so. See ralph's answer for an example — justhalf, Apr 22 '22 at 06:20
@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). — Eric, Apr 22 '22 at 06:23
Does the cop know the speed of the thief or does it not matter? — hkBst, Apr 22 '22 at 10:24
must the cop go only to connected nodes, or can the cop traverse the grid in a direct fashion? — tuskiomi, Apr 22 '22 at 17:06
Also, must both the cop and thief move at their top speed at all times, or can the cop and thief stop moving at any time. Does the cop catch the thief if they intercept each other on a path? i would assume so, because they occupy the same point, and the cop can turn around and follow the thief to whatever point they go to. — tuskiomi, Apr 22 '22 at 17:10
I think the puzzle needs to be fixed to clarify whether the thief can reverse direction at arbitrary places in zero time. The spoilered analogy suggests that the thief can do so, but I think the puzzle would be more interesting if the thief could not. — supercat, Apr 24 '22 at 06:22
I like the analogy! @supercat that would be an interesting variant, but I think this version is also equally interesting :D — justhalf, Apr 24 '22 at 08:56

Florian F · Answer 1 · 2022-04-24T15:09:34.303

6

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.

edited Apr 24 '22 at 15:09

answered Apr 21 '22 at 23:06

Florian F

29,623
4
63
138

I've edited the question to make it even more interesting. – Eric Apr 22 '22 at 07:07
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. – Eric Apr 22 '22 at 16:03
2

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. – Shufflepants Apr 22 '22 at 16:13
@Shufflepants A winning strategy would have to win for any initial condition of the thief's position. The cop's strategy must be guaranteed to win, and if there is any situation where it isn't (namely, the thief starting at an intersection), it's not a strategy guaranteed to win. Even an arbitrarily fast cop can't guarantee a capture, since he cannot guarantee that the thief starts on an edge instead of a vertex. An arbitrarily fast cop could win almost surely, but as long as it's possible for the thief to start at a vertex, it's possible he's never captured. – Nuclear Hoagie Apr 22 '22 at 16:33
1

@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. – Florian F Apr 22 '22 at 22:25
@FlorianF There is no point in that sequence where the thief is unable to avoid the cop. What's being described would be a super-task. But even then, it's not clear the thief is caught. There is no step in the sequence where the thief is caught. Only a "the distance between the cop and the thief approaches zero". The point at which the thief is supposedly caught would be the "last" step in a sequence with no last step. – Shufflepants Apr 23 '22 at 07:34
@Shufflepants In a finite time the cop reaches the intersection. Due to the continuity of the path, at that time, the thief must be closer to the intersection than any positive distance. Ergo he must be at the intersection. – Florian F Apr 23 '22 at 09:26
@FlorianF What do you mean by "incusions"? – Acccumulation Apr 24 '22 at 00:32
1

@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. – justhalf Apr 24 '22 at 08:59
Btw thanks Shufflepants for introducing me to the term "supertask". Via reading the article in Wikipedia, seems like there is no agreed-upon consensus whether supertask like this is possible. I guess we should just assume one position and answer based on that? This would mean two different conclusions in the answers (which is fine, I think). So if supertask is possible, then the thief will be caught in this way (assuming we are using this strategy) but if supertask is not possible, then caught in another way or no way at all. – justhalf Apr 24 '22 at 13:37
As for this strategy, I'm inclined to take the position that it's possible, and we simply define the position of the cop and the thief to be at the intersection at the end. These positions are defined based on the value of the limits of the position of the cop and the thief. Since the limit exists (unlike the case of Thomson's lamp), the function of cop's location is well-defined (i.e., for any time t, we can specify the cop's location), and continuous (via standard continuity proof) but not smooth. The cop and thief locations are already possible to be not smooth, so I think this is fine. – justhalf Apr 24 '22 at 13:45
The fundamental problem with this strategy is that it is inconsistent. It demands that the thief stay at an intersection to be able to dodge the cop, but it also demands that the thief move away from that intersection when the cop approaches. Once the thief moves away, they are no longer following the strategy (because they are not at an intersection), so the argument for its effectiveness no longer applies. – John Bollinger Apr 24 '22 at 14:30
@Acccumulation: incusions = incursions. Sorry for the typo. – Florian F Apr 24 '22 at 15:13

ralphmerridew · Answer 2 · 2022-04-22T01:00:40.727

5

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$.

Start at the center.
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.

edited Apr 22 '22 at 01:00

answered Apr 22 '22 at 00:25

ralphmerridew

4,282
16
27

1

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. – Florian F Apr 22 '22 at 06:24
I must admit don't really understand all the notations and the answer, but what is the point of proving this assuming $S_c > 7S_t$? You would still need to prove it for $S_c > 2S_t$ or lower as well. The thief can have an arbitrarily speed close to 1. – Ivo Apr 22 '22 at 08:29
1

Yes, $S_c>7S_t$ seems a bit extreme. In the original version of the puzzle before the edits, the thief started in the opposite corner, and with such a big speed disparity the cop could easily catch the thief before he could even reach the next vertex. – Jaap Scherphuis Apr 22 '22 at 09:26
2

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. https://puzzling.stackexchange.com/questions/36565/can-the-policeman-catch-the-thief?rq=1 required $S_c > 2*S_t$ in a smaller town where he could see the thief. – ralphmerridew Apr 22 '22 at 11:14
1

But the thief doesn't have to travel virtually any distance at all. Thief only needs to travel some ϵ off of the center down some path that the cop did not take. If the cop's next path will take it some distance d down a path, the thief can always choose some distance sufficiently smaller than d to step off and return to the center. In this case where cop's speed is 7 times as fast as the thief, as the cop approaches the center, and plans to go north next for distance d, thief can always dodge west to distance 1/(100d) as the cop reaches the center. – Shufflepants Apr 22 '22 at 15:03
3

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... – Nuclear Hoagie Apr 22 '22 at 15:18
1

This seems to show that the cop can check every road an infinite number of times in finite time, but I don't see how it shows that he catches the thief in that duration. How far the thief can move in a certain amount of time doesn't seem relevant - it seems the thief can evade the cop forever by moving a distance arbitrarily close to 0. – Nuclear Hoagie Apr 22 '22 at 15:25
4

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. – ralphmerridew Apr 22 '22 at 17:31
@ralphmerridew Clever, I think you may be right. There is no identifiable round when the cop catches the thief, as the thief can always stay one edge ahead of the cop. But if the distance from the intersection goes to zero in finite time, it doesn't really matter which edge they're on. Even though the cop and thief are always on different edges, that may not imply that they are separated by non-zero distance - the edges themselves don't touch, yet are separated by exactly 0 distance by the vertex point. – Nuclear Hoagie Apr 22 '22 at 19:48
@NuclearHoagie It does matter though. What's being described would be a super-task. What happens at the end of a super task is ill-defined. Which direction will the cop have just moved at the "end" to catch the thief? – Shufflepants Apr 23 '22 at 07:36
2

@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. – Florian F Apr 23 '22 at 09:31

score 4 · Answer 3 · answered Apr 24 '22 at 08:25

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.

Zizy Archer · Answer 4 · 2022-04-23T12:07:44.677

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.

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? — Eric, Apr 24 '22 at 01:14
@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. — Zizy Archer, Apr 24 '22 at 18:26

Nuclear Hoagie · Answer 5 · 2022-04-22T19:55:44.650

2

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.

edited Apr 22 '22 at 19:55

answered Apr 22 '22 at 15:50

Nuclear Hoagie

4,684
14
32

Interesting. So even without the Oracle, the cop can catch the thief only probabilistically, not for certain in finite time. – Eric Apr 22 '22 at 16:00
1

@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. – Nuclear Hoagie Apr 22 '22 at 16:03
1

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. – Eric Apr 22 '22 at 16:13
For your first point, I'm curious what's your though on the difference between that and ralph's answer. Because in ralph's answer, the thief can also move arbitrarily close to the intersection, but the cop will eventually catch the thief. I think what you proposes might work for any finite rounds (number of times returning to intersection), but it may not work for infinite rounds, as done in ralph's answer. In there, there are infinitely many rounds, but the total distance is still bounded, and after passing that distance, the thief would have already been caught. – justhalf Apr 22 '22 at 19:22
1

@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. – Nuclear Hoagie Apr 22 '22 at 19:33
2

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: https://puzzling.stackexchange.com/questions/111335/reunite-the-stars#comment314087_111346 – justhalf Apr 22 '22 at 19:36
1

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. – Eric Apr 23 '22 at 11:26

score 2 · Answer 6 · answered Apr 22 '22 at 16:07

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$

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. — Florian F, Apr 24 '22 at 15:00

Oray · Answer 7 · 2022-04-22T09:40:30.260

1

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?

edited Apr 22 '22 at 09:40

answered Apr 22 '22 at 09:34

Oray

30,307
6
61
215

"What should be the maximum value of St where..." I believe you meant to say minimum value. Why can't that value be 1? – Eric Apr 22 '22 at 09:52
2

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. – Nuclear Hoagie Apr 22 '22 at 15:11
2

@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. – Nuclear Hoagie Apr 22 '22 at 19:01
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). – justhalf Apr 22 '22 at 19:27

score 0 · Answer 8 · answered Apr 22 '22 at 07:23

0

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

answered Apr 22 '22 at 07:23

Ivo

11,217
3
37
58

1

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. – justhalf Apr 22 '22 at 08:04
@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 – Ivo Apr 22 '22 at 08:06
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. – justhalf Apr 22 '22 at 08:10
@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 – Ivo Apr 22 '22 at 08:12
ralphs does specify the thief speed in the same way I did: $S_c>7∗S_t$. Even in my case the thief speed is faster than their example. – justhalf Apr 22 '22 at 08:15
And about the cop strategy, yes the cop needs to find a strategy that works for any speed. And I'm showing that your strategy doesn't work for some speed. Unless you specify 0.99999 in your answer, which you didn't when I commented. – justhalf Apr 22 '22 at 08:16
@justhalf yeah you're about ralph's answer. Somehow I misunderstood what he meant. I admit I have troubles understanding the answer. In any case, showing that the cop can catch him when $S_c > 7S_t$ seems not very useful to me. Just as it's easy to prove that the cop can catch him when $S_c > 100000000S_t$. It's really irrelevant. Maybe I should have explicitly mentioned that the thief has a speed arbitrarily close to 1, but I really don't think it's necessary – Ivo Apr 22 '22 at 08:22
Well, specifying a tight bound is still useful I think. Of course it's easy to catch the thief if the thief is really slow, and it looks hard to capture when thief is fast. So specifying the boundary between what's possible or not is a helpful partial answer. (it could very well be that the answer is that the cop can catch the thief no matter the speed, I don't know the answer yet) – justhalf Apr 22 '22 at 08:26
Hmmm, I know what happens if the thief has only the Invisibility Cloak. But I'm not sure if adding the Oracle Glasses will be enough to protect the thief. A more rigorous proof is needed. Can you prove it for $S_c=0.9999$? – Eric Apr 22 '22 at 08:28
@Eric honestly I'm not sure how to write a rigorous proof for that. I'm not very experienced in that. But somehow it feels very obvious to me that the thief can be at a certain corner before the cop has traveled to 2 corners, while also avoiding him. Keep in mind that the thief would never have to travel to the corner that's diagonal of him, because he always has 2 corners to chose from – Ivo Apr 22 '22 at 08:36
2

@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? – Ivo Apr 22 '22 at 08:39
"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." I don't quite follow this. Can you draw a picture to illustrate what you mean? – Eric Apr 22 '22 at 09:04
@Eric I hope this makes it clear: https://i.stack.imgur.com/3ND5q.png – Ivo Apr 22 '22 at 09:41

score 0 · Answer 9 · answered Apr 23 '22 at 07:27

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$

Catch the invisible and omniscient thief

9 Answers9

Linked