Can the Policeman catch the Thief?

Question

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

$\hskip2in$

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)

Answer 1

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.

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:

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.

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$)

Answer 2

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.

Answer 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.

Answer 4

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.

Answer 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.