74

The town of Squareshire has six streets: four sides of a square and the lines joining the midpoints of opposite sides.

$\hskip2in$enter image description here

A policeman is chasing a thief along these streets. If they are ever on the same street, then the policeman can shoot the thief. The policeman runs slightly faster than twice the thief (say 2.0001 times the speed of the thief). How can he shoot the thief?

Source: Moscow mathematical Olympiad, 1978

Clarification:

The squares between the streets contain houses and walls, so the policeman can't see the thief unless they're on the same street. He has no idea about the exact location and strategy used by the thief.

(Thanks to and Milo Brandt and Falco for the suggestion on clarification)

Ankoganit
  • 18,612
  • 3
  • 74
  • 133
  • Can anyone help to center the image? – Ankoganit Jun 24 '16 at 03:38
  • 5
    Finally a [tag:mathematics] puzzle which is not just some "find the sequence" and is more puzzle than mathematics. I wish I could upvote more. – BmyGuest Jun 24 '16 at 09:36
  • Are they, any of them allowed to move backwards too ? – Mladen Oršolić Jun 24 '16 at 12:42
  • @MladenOršolić Sure. – Ankoganit Jun 24 '16 at 13:14
  • 3
    Clarification: You should add, that the policemen has no idea about the exact location and strategy used by the thief. The solution on the other hand has to work for any strategy used by the thief (so even if he does not know the position of the policeman, a perfect strategy will catch him, even if he moves according to a perfect evasive strategy) – Falco Jun 24 '16 at 13:49
  • 1
    @Falco Thanks, I edited it accordingly. If something is still not clear, please feel free to edit. – Ankoganit Jun 24 '16 at 13:58
  • Can the policeman look behind while running, without stopping or slowing down? Basically, does he have a 360° vision? – vsz Jun 24 '16 at 15:13
  • Any reasonable policeman would call for backup at this point... – Mason Wheeler Jun 24 '16 at 18:27
  • 6
    Shooting at a mere thief would appear to be excessive force -- especially since a policeman this fast won't need to. If he ever spots the thief, then just run towards her at 2+epsilon speed. Since no street is longer than 2 blocks, if he ever loses sight of the thief, he will be fast enough to be at the point where he saw her last before she can reach the next intersection. – hmakholm left over Monica Jun 24 '16 at 23:54
  • 1
    @vsz he does have 360$^{\circ}$ vision. It that sounds unrealistic, embed the town into a sci-fi movie, where the policeman has a 360-degree-sensor-cum-auto-shooter and thief has a hi-tech X-ray-vision camera. – Ankoganit Jun 25 '16 at 03:18
  • 1
    This was recently also asked and answered at math.SE and artofproblemsolving. – joriki Jun 25 '16 at 09:02
  • 1
    Thanks @joriki . Both of the links you gave attributes the problem to Moscow Maths Olympiad, 1978, so I am editing my question to include that info. – Ankoganit Jun 25 '16 at 09:12
  • @Ankoganit: Good idea. But regarding "both": Note that they're from the same person, so just one independent source for that attribution. – joriki Jun 25 '16 at 09:28
  • @HenningMakholm The puzzle comes from Moscow during the Soviet period: shooting at a suspected thief was probably by far the most reasonable thing they'd done that day. – David Richerby Jun 25 '16 at 11:01
  • Would you like to add an additional challenge of showing a strategy via which a thief who knows the policeman's route can evade the policeman indefinitely if the policeman is not more than twice as fast as the thief, or would that be better as a separate question? – supercat Jun 25 '16 at 15:04
  • @supercat I'm myself working on it, but couldn't reach any conclusion. I am not even sure that such a strategy exists. Maybe $2+\epsilon$ is not the best lower bound? I'd be more than happy if someone can further progress on this, possibly in another (open-ended) question. Anybody is welcome to ask a new question on that. :) – Ankoganit Jun 25 '16 at 15:16
  • 1
    @Ankoganit: For the case of speed being 2.0, mark four locations on each of the three east-west streets at the 1/8, 3/8, 5/8, and 7/8 locations, and likewise for the north-south avenues. Assume Cop starts the intersection of South Street and Central Avenue, and Thief might be at any of the 16 marked positions the cop can't see. Every time the cop moves one space, mark as "possible" every place the thief could be that's next to someplace the thief could have been before but isn't in line of sight of the cop. If you play the game I think you'll find a small number of patterns recurring. – supercat Jun 25 '16 at 20:16
  • Excuse me if im wrong but if the hunter is 2.0001 the speed of the thief i guess its inevitable that the hunter gets the shot unless the hunter and the thief only stick to one block lande and pendle back and fourth. For example upper right block upper lane, down left block bottom lane. To illustrate this a scetch with the graphic divided each block into numbers 1-8. If thief moves first i cant find a scenario where he isnt shot if time is infinite excluding variance. – Aurigae Jun 26 '16 at 11:04
  • @Aurigae I'm not sure I understand what you mean, but if you mean that the thief will necessarily get shot (provided the policeman chooses a right strategy), then that's right, and that's what one has to show. But I don't get your reasoning. – Ankoganit Jun 26 '16 at 13:28
  • @BmyGuest Its not too hard to find more maths Olympiad problems on the internet and share them here ;) – Nic Jul 05 '16 at 00:48
  • @Nic If those fit into the general "quality" criteria of puzzles (not math-problems) here on site and the reference is given, I don't have a problem with that. This one clearly is a good example. A bit of flavour-story (very litte), a precise and "small" yet not trivial task which can be solved by thinking not necessarilly mathematical deduction, and which has an answer which can be understood by the general public without too much issue. – BmyGuest Jul 05 '16 at 07:08

5 Answers5

46

Yes, the policeman can catch the thief, although it may take a very long time. In particular, the following strategy works: The policeman starts in the center. First, he makes a counterclockwise loop around the top right quadrant. Then, he makes a counterclockwise loop around the top left quadrant. Then, he makes a counterclockwise loop around the bottom left quadrant. He continues making such loops until he catches the thief, each time moving to the next quadrant in counterclockwise order. The strategy is illustrated in the following picture, where he executes the red arrows, then the green arrows, then the blue arrows, then the yellow arrows, and then repeat the whole process ad nauseam. The diagram below labels the four steps in each counterclockwise loop from $1$ to $4$, which will be useful in discussing the strategy.

Diagram of the described strategy

In the comments, @f'' points out that this strategy may also be described as follows: The policeman walks around the perimeter counterclockwise. Each time he reaches the midpoint of an edge, he walks into the center and then back out, continuing his traversal of the perimeter from where he left off.

To show that this works, let us first notice that the thief can never safely visit the center of Squareshire. This is because, for her to do so, she would have to run from the perimeter to the center and then back in the time it takes the policeman to make one loop. However, this requires her to run past two edges in the time the policeman runs four, which she cannot do.

In particular, this "disconnects" the center in a way, meaning that, if the thief is not in the center, there is a unique point $P$ on the perimeter where she last left the perimeter, and where she must later enter the perimeter again. This will always be a midpoint of one of the outer edges. An important property is that the thief is no better off leaving the perimeter, then coming back, than she is just standing at point $P$. That is, if she leaves the perimeter at a point $P$, and the policeman then sees that point, she will be surely caught.

To show this, consider what happens during the policeman's first loop around the top left quadrant. If $P$ is the midpoint of the top edge, then the policeman sees it after walking two edges. It continues to be visible to the policeman until he reaches the midpoint of the top edge, at which point he sees everywhere the thief could safely be*. If $P$ is the midpoint of the left edge, then the policeman must have already travelled more than one edge before the policeman enters, and the first time the policeman will see $P$ is when he returns to the center. He will also see the whole edge connecting to $P$, so the thief will die regardless of whether she stayed at $P$, or ventured inwards. The case for the midpoint of the bottom or left edges is similar.

This establishes that, if the thief can survive, she can do so while staying on the perimeter. However, the policeman is "sweeping" the perimeter faster than she can move. In particular, let us label every point of the perimeter by a number** with the numbers increasing in the counterclockwise direction such that the difference between two labels is proportional to the distance between them, as walked on the perimeter. We will consider that $1$ and $0$ represent the same point:

the perimeter labelled as described, with 0 at the right-hand midpoint, then quarter, half, three quarters counterclockwise at the other midpoints

During the policeman's first loop, he is able to see the point $0$, then for a while sees all the points in $[-1/8,1/8]$, then sees all the points in $[1/8,3/8]$. On his way back to the center, he sees the point $1/4$. Then, on the next loop around, he sees the same sequence of points, just shifted by $1/4$ forwards, to signify that he is now sweeping the next quadrant. The significance is that the thief can travel at most some constant amount less than $1/4$ around the perimeter in each of these steps, so the policeman's view eventually catches up. A plot of this is provided below, where the thief's position on the perimeter is a yellow line, running as fast as it can away, and the policeman's view is the shaded region bounded by blue and purple lines. The $x$-axis gives the distance walked by the policeman as a fraction of the perimeter.

enter image description here

The important note here is that the thief's line is limited in slope to some constant less than $1/2$, whereas the policeman's view is moving forwards with an average slope of $1/2$. The thief wishes to avoid her line intersecting the policeman's view, but this is, of course, impossible.

(*Note that the thief could have run across the center so that the policeman doesn't see her until he returns to the center, but we already established that running through the center is a fatal mistake, so we assume the thief doesn't do this.)

(**For mathematicians, we're really considering the perimeter to be $\mathbb R/\mathbb Z$, and then lifting both the policeman's view and the thief's position to $\mathbb R$)

Milo Brandt
  • 7,881
  • 2
  • 27
  • 53
  • Is this possible if both run at same speed? so i can apply strategy in counter strike. – wrangler Jun 24 '16 at 05:40
  • 2
    @wrangler If they run at the same speed, the thief can evade forever by choosing one square and staying on the opposite side of it from the policeman. – f'' Jun 24 '16 at 05:42
  • 6
    @MiloBrandt This strategy can also be described as going around the perimeter and making some visits to the center. That could make it easier to show why the policeman will catch up to the thief. – f'' Jun 24 '16 at 05:45
  • An animation of the best thief strategy would be awesome ! – Fabich Jun 24 '16 at 08:55
  • 1
    @Lordofdark the best Thief's strategy... Hmm, sounds like an extension to the puzzle. "How long can the Thief hold out in best case...?" – BmyGuest Jun 24 '16 at 09:38
  • 1
    @f'' Is it implied that the thief always knows the position of the policemen, but the policemen doesn't know where the thief is? Because if the thief doesn't know where the policemen is, I don't think he can have a perfect strategy, even if he is 1000 times faster than the policeman, because as soon as he sees him it is over, and before that he can just run around randomly.... – Falco Jun 24 '16 at 09:43
  • This answer assumes that the policeman looks in all directions: while running and at every crossroad. Otherwise a thief (knowing the pattern) could avoid the policeman forever (e.g. staying behind the officer). – Matthias Bäßler Jun 24 '16 at 11:21
  • @Falco I assumed that they both know exactly where eachother are, but this answer assumes that they do not. – Trenin Jun 24 '16 at 12:23
  • 3
    @Trenin, if the policeman knows where the thief is, this becomes trivial, because he is faster he can simply follow the exact same path the thief is running and will easily catch him very fast. Maximum distance of the two is 4 units (if the whole thing is 2x2) so if the thief runs 4 units, the policeman will run 8 in the same time and catch him. – Falco Jun 24 '16 at 13:51
  • @MatthiasBäßler If the officer looks ahead of himself on the first 3 edges of each loop, and behind himself for the next edge, then stops at the center for a small amount of time to look around (but not so long that his average speed decreases below half the thief's), this strategy still works. He could also always look forwards, taking a moment to look around at the center and after the first edge. – Milo Brandt Jun 24 '16 at 13:54
  • @Lordofdark The thief's best strategy against the strategy I propose is to start such that, after the officer has run the two edges to the top left, the thief is just going around the bottom left corner. Then, the thief just runs counterclockwise until being caught. (It's pretty close to what the graph shows) – Milo Brandt Jun 24 '16 at 13:57
  • 1
    I agree with f'' that I'd have understood the plan better if it was described as running the perimeter and going in and out of the centre every time you pass one of the mid points. Otherwise excellent answer. :) – Chris Jun 24 '16 at 14:10
  • 2
    Why did the OP state that the policeman run a little over 2 times faster than the thief? Does that mean that if the policeman just nice runs 2 times faster than the thief, is impossible to shoot the thief? – ministic2001 Jun 24 '16 at 14:46
  • @Falco Agreed. That is why I thought the problem was unclear. It was trivial the way I was looking at it and I needed to review this answer before I discovered I was making a different assumption. – Trenin Jun 24 '16 at 19:12
  • @ministic2001 If the police follows the exact strategy as in this answer, it may be impossible. For example,when the police starts from the center, the thief from the NW corner, and sweeps the perimeter counter clockwise. I don't yet know about the general case; maybe the lowest necessary speed for the police would be a nice follow-up? – Ankoganit Jun 25 '16 at 03:58
  • 1
    @Ankoganit I think that would be an interesting question. I've been thinking a lot about it, and have yet to come to an answer. (Nor any interesting approaches - I could definitely write a computer program to decide efficiently whether the policeman moving exactly twice as fast as the thief could make the catch, but that wouldn't be a terribly satisfying way to go about it) – Milo Brandt Jun 26 '16 at 20:21
4

Well, first of all, I don't know what the thief has stolen, but unless it is a weapon of mass destruction or something that the thief intends to use to kill, it's pretty hard to justify valuing the stolen object more highly than human life. Death does not seem to be a just punishment for illegal reallocation of property, especially when the policeman is clearly fast enough to catch the thief without lethal force. The moment he sees the thief, he can simply run straight toward the thief and with his speed advantage, he is guaranteed to reach the next intersection in time to see which way the thief has turned, and he will catch him before he can traverse two city blocks. I understand that he is being caught red-handed, but he still deserves due process and may yet be reformed into a productive member of society.

That said, the strategy of simply walking one direction around the perimeter while always travelling to the center and back at each intersection has been posted, and is a correct answer. But constantly reversing direction at the center point is very stressful on our policeman's ankles, and this could take a while! So I wanted to point out that there is an alternate strategy that doesn't involve any fast direction reversals. By removing these direction reversals, he will also catch the thief faster, because the decelleration at the center of the square will be removed.

If the policeman begins on the perimeter heading counter-clockwise:
1. When he comes to a perimeter intersection, he always turns left.
2. He runs straight through the center (glancing down the other center street each direction as he crosses it, of course).
3. He turns left to again run counter-clockwise down the perimeter (after glancing over his right shoulder for the thief).
4. After rounding the corner, he returns to step 1 as he approaches the intersection.

By following these steps, he is actually combing the perimeter in a clockwise direction, but jumps ahead and then doubles back instead of proceeding around the perimeter directly. The thief cannot visit the center for the same reason mentioned in other answers - the policeman returns to the center faster than the thief can get to the center and then back to the perimeter. The thief will stay on the run the longest by just heading clockwise. (Maybe he likes jogging?) If he tries to go counter-clockwise, he cannot move fast enough to skip over one of the policeman's block circuits, so he will be caught faster. However, even proceeding clockwise, he will be caught eventually, because the policeman only covers exactly twice as much ground as the thief as he pursues him in the clockwise direction, and his speed is greater than twice the thief's speed.

I should also point out that just as with the other strategy, the policeman always turns in the same direction (left). This causes a repetitive motion strain on his knees and ankles. So I might suggest that if he chases this thief down in the clockwise direction, he might go in the counter-clockwise direction the next time he has to chase down a thief in this odd, completely closed-off town square.

Mark Bailey
  • 140
  • 5
3

@MiloBrandt already showed a working strategy and a proof, but I thought some of the arguments can be simplified a bit. Since I didn't want to suggest an edit to his legitimate solution, decided to add my version below.

As Milo already pointed out, a good strategy for the policeman would be to encompass the 4 blocks of the town in a clock-wise manner one by one, clock-wise.

Since the policeman is twice as fast as the thief, if the thief is in the center of the town at some point, then there exists a moment in which the policeman is in the center, and the thief is not on the boundary, i.e. he gets shot.

Now, assuming the thief never visits the center, his angle with respect to the coordinate system defined by the two middle roads changes continuously. The angle of the policeman with respect to the same coordinate system can be defined to change continuously as well. Since the policeman needs less time to increase his angle with 360 degrees than the thief, there will be a moment when the two have the same angle. However, this implies that the policeman will be able to see the thief, and shoot him.

P.S. If the moderators or Milo decide it is better to edit the original solution using this one, feel free to do so and erase this answer.

Puzzle Prime
  • 6,964
  • 31
  • 62
1

First, a solution if the policemen knows where the thief is.

The policeman goes to the centre intersection. If the thief is on one of the centre streets, the policeman wins. Otherwise, assume that the thief is on the top half of the leftmost street.

If the thief is on the bottom quarter of the top half (i.e. between half and three quarters of the way up), the policeman should run left, and if the thief flees downwards the policeman can shoot him as he passes the intersection, or if he flees upwards, the policeman will reach the leftmost street before the thief reaches the top-left corner, and also see him to shoot him (because the policeman runs twice as fast).

If the thief is on the top quarter of the top half (i.e. more than three quarters of the way up), first the policeman should run leftwards, then upwards. This is a total distance of 2 units, where 1 unit is the distance between intersections. If the thief flees downwards, then the policeman will catch him as he passes the intersection. If he flees upwards, then the distance to the top middle intersection is at least 1.5 units. In the time it takes the thief to travel 1 unit, the policeman can travel two units and be at the top-left corner, and by that time the thief will only be a quarter of the way along the top street.

If the policeman doesn't know where the thief is, just repeat the above many times, starting at the centre each time, and picking a random street to run down and corner to run towards each time. The thief can't predict which way the policeman will go so he eventually the thief will be hiding somewhere where this strategy will work.

Gavin Smith
  • 119
  • 1
  • 2
    What if the thief accidentally predicts which way the policeman would go? The strategy must work with 100% certainty even in the worst-case scenario. – Ankoganit Jun 25 '16 at 09:46
  • It's impossible to predict which way the policeman would go infinitely many times. – Gavin Smith Jun 25 '16 at 11:16
  • 2
    @GavinSmith It's not impossible. The thief could have attached a localization device to the policeman. – Oriol Jun 25 '16 at 16:27
  • @gavin smith the idea is that no matter what starting point and combination of motions that the thief makes, it is impossible for them to escape. – user64742 Jun 25 '16 at 19:56
-5

Policeman will wait at the center of Squareshire. the moment he sees that thief run through any other street he shall run to that street and in the direction to which thief ran. And as u said Policeman runs twice than theif. he will find thief about half way on street.

Wasiq Shahrukh
  • 1,046
  • 12
  • 24
  • 20
    Sorry, not correct. The thief too can wait in a corner forever. – Ankoganit Jun 24 '16 at 05:42
  • 3
    And you are missing the vital point: As soon as he sees the thief... he shoots to kill and it's over ;-) Seeing the thief is the goal, and not as easy as you may think – Falco Jun 24 '16 at 09:44