13
$\begingroup$

The ACLU won a lawsuit against the Squareshire Police Department, alleging that his policy of shooting suspected thieves on sight was unconstitutionally excessive force.

The argument that carried the day was that the policeman doesn't need to shoot: He runs fast enough that, if he ever catches sight of a thief he can simply pursue her on foot, and he will then never need to guess which way she's fleeing. Namely: Because the streets are of limited length, a policeman can't be more than 2 blocks away from a thief he can see, so even if he loses sight of her subsequently, he will be able to reach the point where she was last seen before she has time to reach the next intersection.

Now, however, Squareshire is growing. It consists of $N^2$ city blocks arranged in a square grid made of $2(N+1)$ streets each of length $N$. It is still patrolled by policemen who can run slightly faster than twice the speed of a suspected criminal.

You're a legal staffer with the ACLU, and you've been given the task of proving that even in the enlarged city, any policeman who spots a thief will still have an unbeatable strategy for catching up with her in finite time, and therefore he doesn't need to be allowed to shoot.

How large an $N$ can you extend this argument to?

Note 1: Your argument cannot involve calling for backup. Whether Squareshire has enough policemen that backup is always available would be a question of fact that needs to be decided by a jury, and your superiors don't want to risk that.

Note 2: In contrast to the earlier question, it is not necessary to be able to catch a thief whose position is completely unknown. Only that if the thief and the policeman are ever present in the same street, then she won't afterwards be able to escape.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Are you specifying the cop's speed as being just over twice that of the Thief, or has the expansion of Squareshire allowed the cops to buy better shoes? $\endgroup$
    – supercat
    Jun 25, 2016 at 15:05
  • $\begingroup$ @supercat: Still just over twice the thief's speed. $\endgroup$
    – hmakholm left over Monica
    Jun 25, 2016 at 15:10
  • $\begingroup$ this introduces a new strategy for the thief - can she stop halfway between blocks and do an about turn? or maybe just paws (sorry) for a while? otherwise i've done N=3 $\endgroup$
    – JMP
    Jun 25, 2016 at 15:37
  • $\begingroup$ @JonMarkPerry: As long as she stays in the street, she can stop and/or double back whenever she wants. $\endgroup$
    – hmakholm left over Monica
    Jun 25, 2016 at 15:39
  • $\begingroup$ So the police officer just needs to see the thief to be done? $\endgroup$
    – Dr Xorile
    Jun 25, 2016 at 17:17

3 Answers 3

Reset to default
5
$\begingroup$

I tried using spoilers for the tables but couldn't figure it out sorry.

I believe the cop could catch the thief in a city that is

N=4

Once the cop is within 2 blocks of the thief and knows where he is the thief can't escape because the cop can run to the point he knows hes at and sees the thief before the thief makes another turn Doubling back doesn't help the thief since the cop always runs to the last point he knew the thief was at so doubling back the cop would see the thief crossing that intersection

N=4 case 1
T=0

+----T----+----+----+
|    |    |    |    |   
+----+----+----+----+
|    |    |    |    |    
+----+----+----+----+
|    |    |    |    |    
+----+----+----+----+
|    |    |    |    |    
+----C----+----+----+

T=2
+----C----+----Ta---+
|    |    |    |    |   
+----+----Tb---+----+
|    |    |    |    |    
+----+----+----+----+
|    |    |    |    |    
+----+----+----+----+
|    |    |    |    |    
+----+----+----+----+
Cop is within 2 blocks of the thief and knows where he is since he can either see him (Ta) or knows he turned (Tb) if he can't see him

N=4 case 2
T=0
+----+----+----+----+
|    |    |    |    |   
+----T----+----+----+
|    |    |    |    |    
+----+----+----+----+
|    |    |    |    |    
+----+----+----+----+
|    |    |    |    |    
+----C----+----+----+

T=1
+----+----+----+----+
|    |    |    |    |   
+----+----T----+----+
|    |    |    |    |    
+----C----+----+----+
|    |    |    |    |    
+----+----+----+----+
|    |    |    |    |    
+----+----+----+----+
Cop is within 2 blocks of the thief and knows where he is

N=5 case 1
T=0
+----T----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----C----+----+----+----+

T=2
+----+----+----Ta---+----+
|    |    |    |    |    |
+----C----Ta---+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
Cop is potentially within 2 blocks of the thief but doesn't know where he is (thief at Ta would have to wait for cop to run past)

T=3
+----+----C----+----Ta---+
|    |    |    |    |    |
+----Td---+----Tb---+----+
|    |    |    |    |    |
+----+----Tc---+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
Cop is within 2 blocks but doesn't know where the thief is (could be at Tb or Td without being seen) thief gets away

N=5 case 2
T=0
+----+----+----+----+----+
|    |    |    |    |    |
+----T----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----C----+----+----+----+

T=2
+----+----Ta---+----+----+
|    |    |    |    |    |
+----C----+----Tb---+----+
|    |    |    |    |    |
+----+----Tc---+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
Cop doesn't know where the thief is
T=2.5
+----+-Ta-+-Tb-+----+----+
|    |    |    Tc   |    |
+----+----C----+-Te-+----+
|    |    |    Td   |    |
+----+-Tg-+-Tf-+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+
|    |    |    |    |    |
+----+----+----+----+----+

Cop can't track the thief

So the cop can catch the thief in N=4 but not necessarily in N=5 sized city

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice breakdown! But in case 1, I think your cop ran the wrong way at T=2. If he'd run east instead of north, he'd have gotten to the lower-left point Ta at T=2.5, so any thief hiding near that point would have been caught. If he hasn't caught the thief yet, then he runs north so that at T=3 the thief would have to be at either Ta or Tb (but not Tc or Td). And, if the thief were at Ta, the cop would spot him; so case 1 is actually solved. Your case 2 still looks troublesome, though. $\endgroup$
    – Quuxplusone
    May 2, 2018 at 7:09
2
$\begingroup$

N=5. She needs to be able to travel 3 intersections turning randomly to lose him.
3 intersections is 2 blocks and given the fact that he runs twice as fast he should be able to catch her from a distance of 4 blocks, meaning a city of 5 by 5 blocks.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I find this response difficult to understand. Are you claiming that you have a strategy that the policeman can follow in an $N=5$ city; or that you have a strategy that he can follow in a city of size $N<5$? In either case you don't seem to actually be explaining such a strategy. $\endgroup$
    – hmakholm left over Monica
    Jun 25, 2016 at 18:03
  • $\begingroup$ assuming there are no perimeter streets the officer can be in disadvantage/distance of 4 blocks and still be able to catch the suspect. If the police officer gives chase from the worst position e.g. at the end of one the N/S streets seeing the suspect near the other end, she has to run to the 4th intersection and enter into a E/W street to right or left. now the officer has a distance of X< 4 blocks. she can run one block and then turn N/S again and if she can finish going around this block( running 2 blocks) the officer won't see her, but by then the officer is there already. $\endgroup$
    – kamran
    Jun 26, 2016 at 1:22
0
$\begingroup$

If the thief is not allowed to backtrack or hover during block runs, I think the following works:

Place C and T in a vertical street. C sees T go either left or right, and so moves up and either left or right to match T's movement. This reduces the gap by 1, and C can still see T.

If the thief can reverse:

This doesn't work as she can stop invisible to C halfway along a block.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ In the comments OP stated the thief could backtack or stop. $\endgroup$
    – gtwebb
    Jun 26, 2016 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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