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?
3
-
$\begingroup$ 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! ;) $\endgroup$– Omega KryptonJun 14, 2019 at 1:36
-
4$\begingroup$ I disagree. This should be on topic. IF puzzling.stackexchange.com/questions/36565/… 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. $\endgroup$– greenturtle3141Jun 14, 2019 at 2:03
-
2$\begingroup$ 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) $\endgroup$– dr_Jun 14, 2019 at 11:13
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
10
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.
-
$\begingroup$ 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. $\endgroup$ Jun 14, 2019 at 2:18
-
$\begingroup$ @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. $\endgroup$– Deusovi ♦Jun 14, 2019 at 2:33
-
2$\begingroup$ @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. $\endgroup$– Deusovi ♦Jun 14, 2019 at 5:32
-
1$\begingroup$ @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. $\endgroup$ Jun 14, 2019 at 13:20
-
1$\begingroup$ @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^^) $\endgroup$– SyndicJun 14, 2019 at 13:25
$\begingroup$
$\endgroup$
2
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?
-
3$\begingroup$ Since this is mathematical in nature, we can make the assumption that this interpretation is not the intention. $\endgroup$ Jun 14, 2019 at 1:59
-
$\begingroup$ Figured as much! That would've been too easy :D $\endgroup$ Jun 14, 2019 at 13:18
$\begingroup$
$\endgroup$
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.
