12

At x = 0, a thief robbed a bank. The thief ran one of two known directions at a constant speed, towards x < 0 or towards x > 0. The cop arrives at the crime scene some unknown time after the robbery. If the cop is faster than the robber, and traveling at a constant speed as well, is there a guaranteed way of catching the thief?

Daniel
  • 123
  • 5
  • welcome here! sorry, but this seems not on-topic, according to the scope defined in the help center. such off-topic posts may get deleted or closed. please check the help center to see what questions you should/ can ask here on P.SE. happy puzzling! ;) – Omega Krypton Jun 14 '19 at 01:36
  • 4
    I disagree. This should be on topic. IF https://puzzling.stackexchange.com/questions/36565/can-the-policeman-catch-the-thief is ok, then this is.

    Besides the cited precedent, I must point out that this question, while mathematical in nature, isn't purely mathematical, and it certainly has a real enough interpretation to be very interesting.

     – greenturtle3141 Jun 14 '19 at 02:03
  • 2
    This definitely belongs to Puzzling, and it's a great riddle, since it has a twist: while one might think that the cop has only 50% chance of catching the thief, this turns out not to be the case! (see answer below) – dr_ Jun 14 '19 at 11:13

3 Answers3

20

Yes, it's possible.

First, assume the robber left one minute before you arrived and ran left. Run left until you catch up with the position that the robber would now be if that was the case.
Then, assume that the robber left one minute before you arrived and ran right. Run right until you catch up with the position the robber would now be if that was the case.
Then, assume that the robber left two minutes before you arrived and ran left. Run left until you catch up with the position that the robber would now be if that was the case.
Then, assume that the robber left two minutes before you arrived and ran right. Run right until you catch up with the position that the robber would now be if that was the case.
Then, assume that the robber left three minutes before you arrived and ran left...

It takes longer and longer to catch up to these imaginary robbers because of the time you use running back and forth, but eventually one of your assumptions will be correct, and so the imaginary robber in your assumption will be the real robber.

But what if

you don't know the speed of the robber?

It's still possible in this case:

we can use a similar strategy, but modifying the assumptions made. Now, every round includes an assumption about the robber's speed: in the first one, you assume the robber has (at most) 1/2 of your speed, in the second you assume the robber has (at most) 3/4 of your speed, in the third you assume the robber has (at most) 7/8 of your speed, and so on. Since the robber is strictly slower than you, at some point this assumption will be correct. And so eventually, both your speed and time assumptions will be good enough, and you'll pick the right direction and catch up to the robber.

Deusovi
  • 146,248
  • 16
  • 519
  • 609
  • To elaborate, (I think this is right?) we can represent each possibility as a pair $(v,t)$ where $v$ is robber's speed and $t$ is time after robber left. We need to check every pair. Clearly, we can check any pair. If we check a pair $(v_1,t_1)$, we effectively check all $(v_2,t_2)$ where $v_2<v_1$ and $t_2<t_1$. If $c$ is the cop's speed, then $v$ is contained in one of the intervals $[0,.9c]$, $[0,.99c]$, ..., and $t$ is contained in one of $[0,1]$, $[0,2]$, ... so we have a 2D array to check of cardinality $|\mathbb{N}^2| = |\mathbb{N}|$, so we can indeed check all possibilities. – greenturtle3141 Jun 14 '19 at 02:18
  • @greenturtle3141 Right -- I phrased it less mathematically, but this is effectively a cardinality argument in disguise. You don't need to check every point in the array though, because checking any point $(v,t)$ automatically gives you all points $(v',t')$ with $v'\leq v$ and $t'\leq t$. So you only need to check the points along the main diagonal. – Deusovi Jun 14 '19 at 02:33
  • Ah you're right, that's definitely much simpler. – greenturtle3141 Jun 14 '19 at 02:34
  • If I understand, the strategy is to choose the robber is very slow compared to the cop, maybe (1/2)c, if c is the speed of the cop. Since the cop know their own speed, they will know when the should catch up if they went the right way. If it is wrong they turn around and assume the speed is closer to c and chase after the robber for the unnecessary time to catch up. The robber would oscillate back and forth, but how would you choose the assumption of the cops speed at every round? Also, it is unknown how far the robber has already travelled. – Daniel Jun 14 '19 at 04:52
  • 2
    @Daniel You don't make any assumptions about the cop's speed -- you know the cop's speed. And no, the strategy is not to choose that the robber is very slow -- the strategy is to assume the robber is fast, and get better and better approximations. The robber also does not oscillate -- your comment makes no sense to me. – Deusovi Jun 14 '19 at 05:32
  • While this would work, there's an inefficiency that irks me: after you ran left to the 1-minute-point and then right to the 1-minute-point, you then run left to the two-minute point and so on - please instead run further right to the two-minute-point and THEN left again instead! This will save you quite a bit of running ;) – Syndic Jun 14 '19 at 13:02
  • 1
    @Syndic The only problem with that line of thinking is that it can also be extended to the three-minute point, and the four-minute point, and so on infinitely. If you follow that train of thought, then the cop should only ever travel in one direction for fear of being inefficient. – Aleksandr Hovhannisyan Jun 14 '19 at 13:20
  • 1
    @AleksandrH I propose still doing "first both 1-minute-points, then both 2-minute-points, then both 3..." - just with a slight switch in the order. Instead of going L1-R1-L2-R2-L3-R3, you should run L1-R1-R2-L2-L3-R3. The first one would have you run 1+2+3+4+5+6 distances, the second one 1+2+1+4+1+6 (not really since the distances keep growing, but I hope this is enough as a thinking aid^^) – Syndic Jun 14 '19 at 13:25
  • @Deusovi sorry, I meant the cop would oscillate. So the cop should assume the robber's speed relative to their own speed. By checking along the diagonal, I assume you mean to check the points (v, t) for (1, 0.9c) (2, 0.99c), and keep assuming the time before the cop arrived is larger and the speed of the robber is larger, eventually you will catch up. So the cop turns around and tests the next assumption in the other direction. – Daniel Jun 14 '19 at 15:37
  • @Daniel yeah, that's about right. – greenturtle3141 Jun 14 '19 at 16:52
5

Just a guess, but...

If we're only dealing with x < 0 and x > 0, then the cop had to arrive at the crime scene from one of those two directions. If he didn't encounter the robber on his way toward the bank, then doesn't he simply have to go in the direction opposite the one he came in?

Aleksandr Hovhannisyan
  • 245
  • 1
  • 5
-1

thief ran one of two known directions

and

the cop is faster than the robber

So it's garanteed if the cop goes in the known direction for some finite amount of time. Life is guaranteed by no one, so we can't garentee he'll catch the robber.

Philip Rego
  • 111