mathematics - Can the Policeman catch the Thief?

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

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