Catching a robber on one lineCan the Policeman catch the Thief?Pursuit Problem II: Surrounded in Marauders' Circular CoveWhich candidate is most washed up?Ernie and the Unexpectedly Exposed PINA puzzle about flies and trains25 Horses and 5 TracksHow Many Diamonds robbed by the 7 D&D thieves?Can the policeman actually catch the thief, instead of shooting?Hack of the International Stamped Time ServerGotta Catch 'Em All!Just One Line! Really?
How was Hillel permitted to go to the skylight to hear the shiur
Why do all the teams that I have worked with always finish a sprint without completion of all the stories?
Should I prioritize my 401(k) over my student loans?
Sci fi short story, robot city that nags people about health
Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)
Interaction between Leyline of Anticipation and Teferi, Time Raveler
Can humans ever directly see a few photons at a time? Can a human see a single photon?
Should my manager be aware of the proposals I receive? How to politely have this happen?
Is there a maximum distance from a planet that a moon can orbit?
How is hair tissue mineral analysis performed?
Require advice on power conservation for backpacking trip
Find the probability that the 8th woman to appear is in 17th position.
Is it illegal to withhold someone's passport and green card in California?
Would it be a copyright violation if I made a character’s full name refer to a song?
Why the feminine "la" in "à la Leonardo DiCaprio", though he is a man?
What does an Input layer of shape=(None,) or (None,12) actually mean?
Folding basket - is there such a thing?
Loss of power when I remove item from the outlet
Cascading Repair Costs following Blown Head Gasket on a 2004 Subaru Outback
Why do some games show lights shine thorugh walls?
What is this tool/thing in an Aztec painting?
Where can I find Intensity vs Observed wavelength graphs?
How does this circuit work? (AM receiver)
Can we put equal sign after aggregate functions in sql?
Catching a robber on one line
Can the Policeman catch the Thief?Pursuit Problem II: Surrounded in Marauders' Circular CoveWhich candidate is most washed up?Ernie and the Unexpectedly Exposed PINA puzzle about flies and trains25 Horses and 5 TracksHow Many Diamonds robbed by the 7 D&D thieves?Can the policeman actually catch the thief, instead of shooting?Hack of the International Stamped Time ServerGotta Catch 'Em All!Just One Line! Really?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
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?
mathematics
asked Jun 14 at 1:15
DanielDaniel
635 bronze badges
New contributor
Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
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?
mathematics
asked Jun 14 at 1:15
DanielDaniel
635 bronze badges
New contributor
Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$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 Krypton
Jun 14 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$
– greenturtle3141
Jun 14 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$
– dr01
Jun 14 at 11:13
add a comment |
$begingroup$
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?
mathematics
asked Jun 14 at 1:15
DanielDaniel
635 bronze badges
New contributor
Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
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?
mathematics
mathematics
asked Jun 14 at 1:15
DanielDaniel
635 bronze badges
New contributor
Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jun 14 at 1:15
DanielDaniel
635 bronze badges
New contributor
Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Jun 14 at 15:47
Daniel
asked Jun 14 at 1:15
DanielDaniel
635 bronze badges
New contributor
Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Jun 14 at 1:15
DanielDaniel
635 bronze badges
asked Jun 14 at 1:15
DanielDaniel
635 bronze badges
635 bronze badges
New contributor
Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Daniel is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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 Krypton
Jun 14 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$
– greenturtle3141
Jun 14 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$
– dr01
Jun 14 at 11:13
add a comment |
$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 Krypton
Jun 14 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$
– greenturtle3141
Jun 14 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$
– dr01
Jun 14 at 11:13
$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 Krypton
Jun 14 at 1:36
$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 Krypton
Jun 14 at 1:36
4
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$
– greenturtle3141
Jun 14 at 2:03
$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$
– greenturtle3141
Jun 14 at 2:03
2
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$
– dr01
Jun 14 at 11:13
$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$
– dr01
Jun 14 at 11:13
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
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.
answered Jun 14 at 2:04
Deusovi♦Deusovi
67.4k7 gold badges232 silver badges293 bronze badges
$endgroup$
$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 $|mathbbN^2| = |mathbbN|$, so we can indeed check all possibilities.
$endgroup$
– greenturtle3141
Jun 14 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 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 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$
– AleksandrH
Jun 14 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$
– Syndic
Jun 14 at 13:25
|
show 5 more comments
$begingroup$
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?
answered Jun 14 at 1:21
AleksandrHAleksandrH
2465 bronze badges
$endgroup$
2
$begingroup$
Since this is mathematical in nature, we can make the assumption that this interpretation is not the intention.
$endgroup$
– greenturtle3141
Jun 14 at 1:59
$begingroup$
Figured as much! That would've been too easy :D
$endgroup$
– AleksandrH
Jun 14 at 13:18
add a comment |
$begingroup$
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.
answered Jun 14 at 22:42
Philip RegoPhilip Rego
11
New contributor
Philip Rego is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "559"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Daniel is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f85055%2fcatching-a-robber-on-one-line%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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.
answered Jun 14 at 2:04
Deusovi♦Deusovi
67.4k7 gold badges232 silver badges293 bronze badges
$endgroup$
$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 $|mathbbN^2| = |mathbbN|$, so we can indeed check all possibilities.
$endgroup$
– greenturtle3141
Jun 14 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 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 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$
– AleksandrH
Jun 14 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$
– Syndic
Jun 14 at 13:25
|
show 5 more comments
$begingroup$
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.
answered Jun 14 at 2:04
Deusovi♦Deusovi
67.4k7 gold badges232 silver badges293 bronze badges
$endgroup$
$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 $|mathbbN^2| = |mathbbN|$, so we can indeed check all possibilities.
$endgroup$
– greenturtle3141
Jun 14 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 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 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$
– AleksandrH
Jun 14 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$
– Syndic
Jun 14 at 13:25
|
show 5 more comments
$begingroup$
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.
answered Jun 14 at 2:04
Deusovi♦Deusovi
67.4k7 gold badges232 silver badges293 bronze badges
$endgroup$
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.
answered Jun 14 at 2:04
Deusovi♦Deusovi
67.4k7 gold badges232 silver badges293 bronze badges
answered Jun 14 at 2:04
Deusovi♦Deusovi
67.4k7 gold badges232 silver badges293 bronze badges
answered Jun 14 at 2:04
Deusovi♦Deusovi
67.4k7 gold badges232 silver badges293 bronze badges
answered Jun 14 at 2:04
Deusovi♦Deusovi
67.4k7 gold badges232 silver badges293 bronze badges
67.4k7 gold badges232 silver badges293 bronze badges
$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 $|mathbbN^2| = |mathbbN|$, so we can indeed check all possibilities.
$endgroup$
– greenturtle3141
Jun 14 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 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 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$
– AleksandrH
Jun 14 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$
– Syndic
Jun 14 at 13:25
|
show 5 more comments
$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 $|mathbbN^2| = |mathbbN|$, so we can indeed check all possibilities.
$endgroup$
– greenturtle3141
Jun 14 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 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 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$
– AleksandrH
Jun 14 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$
– Syndic
Jun 14 at 13:25
$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 $|mathbbN^2| = |mathbbN|$, so we can indeed check all possibilities.
$endgroup$
– greenturtle3141
Jun 14 at 2:18
$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 $|mathbbN^2| = |mathbbN|$, so we can indeed check all possibilities.
$endgroup$
– greenturtle3141
Jun 14 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 at 2:33
$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 at 2:33
2
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 at 5:32
$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 at 5:32
1
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$
– AleksandrH
Jun 14 at 13:20
$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$
– AleksandrH
Jun 14 at 13:20
1
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$
– Syndic
Jun 14 at 13:25
$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$
– Syndic
Jun 14 at 13:25
|
show 5 more comments
$begingroup$
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?
answered Jun 14 at 1:21
AleksandrHAleksandrH
2465 bronze badges
$endgroup$
2
$begingroup$
Since this is mathematical in nature, we can make the assumption that this interpretation is not the intention.
$endgroup$
– greenturtle3141
Jun 14 at 1:59
$begingroup$
Figured as much! That would've been too easy :D
$endgroup$
– AleksandrH
Jun 14 at 13:18
add a comment |
$begingroup$
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?
answered Jun 14 at 1:21
AleksandrHAleksandrH
2465 bronze badges
$endgroup$
2
$begingroup$
Since this is mathematical in nature, we can make the assumption that this interpretation is not the intention.
$endgroup$
– greenturtle3141
Jun 14 at 1:59
$begingroup$
Figured as much! That would've been too easy :D
$endgroup$
– AleksandrH
Jun 14 at 13:18
add a comment |
$begingroup$
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?
answered Jun 14 at 1:21
AleksandrHAleksandrH
2465 bronze badges
$endgroup$
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?
answered Jun 14 at 1:21
AleksandrHAleksandrH
2465 bronze badges
answered Jun 14 at 1:21
AleksandrHAleksandrH
2465 bronze badges
answered Jun 14 at 1:21
AleksandrHAleksandrH
2465 bronze badges
answered Jun 14 at 1:21
AleksandrHAleksandrH
2465 bronze badges
2465 bronze badges
2
$begingroup$
Since this is mathematical in nature, we can make the assumption that this interpretation is not the intention.
$endgroup$
– greenturtle3141
Jun 14 at 1:59
$begingroup$
Figured as much! That would've been too easy :D
$endgroup$
– AleksandrH
Jun 14 at 13:18
add a comment |
2
$begingroup$
Since this is mathematical in nature, we can make the assumption that this interpretation is not the intention.
$endgroup$
– greenturtle3141
Jun 14 at 1:59
$begingroup$
Figured as much! That would've been too easy :D
$endgroup$
– AleksandrH
Jun 14 at 13:18
2
2
$begingroup$
Since this is mathematical in nature, we can make the assumption that this interpretation is not the intention.
$endgroup$
– greenturtle3141
Jun 14 at 1:59
$begingroup$
Since this is mathematical in nature, we can make the assumption that this interpretation is not the intention.
$endgroup$
– greenturtle3141
Jun 14 at 1:59
$begingroup$
Figured as much! That would've been too easy :D
$endgroup$
– AleksandrH
Jun 14 at 13:18
$begingroup$
Figured as much! That would've been too easy :D
$endgroup$
– AleksandrH
Jun 14 at 13:18
add a comment |
$begingroup$
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.
answered Jun 14 at 22:42
Philip RegoPhilip Rego
11
New contributor
Philip Rego is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
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.
answered Jun 14 at 22:42
Philip RegoPhilip Rego
11
New contributor
Philip Rego is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
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.
answered Jun 14 at 22:42
Philip RegoPhilip Rego
11
New contributor
Philip Rego is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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.
answered Jun 14 at 22:42
Philip RegoPhilip Rego
11
New contributor
Philip Rego is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Jun 14 at 22:42
Philip RegoPhilip Rego
11
New contributor
Philip Rego is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered Jun 14 at 22:42
Philip RegoPhilip Rego
11
answered Jun 14 at 22:42
Philip RegoPhilip Rego
11
11
New contributor
Philip Rego is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Philip Rego is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
Daniel is a new contributor. Be nice, and check out our Code of Conduct.
Daniel is a new contributor. Be nice, and check out our Code of Conduct.
Daniel is a new contributor. Be nice, and check out our Code of Conduct.
Daniel is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f85055%2fcatching-a-robber-on-one-line%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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 Krypton
Jun 14 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$
– greenturtle3141
Jun 14 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$
– dr01
Jun 14 at 11:13