Escape Management

A thief has just robbed a bank at the center of a city. He has done the robbery quietly, so he believes he is not being tracked. In fact, though, a silent alarm has alerted the police to the theft and they know the exact position of the thief. Their hope is to catch the thief and his accomplices.

The city is laid out as a 19 × 19 road grid. The thief (T) starts exactly in the center, that is, nine blocks from any border. Figure 1-1 shows the upper right portion of the whole grid. The thief begins to drive north towards the first intersection in the northern half of the city. At every intersection the car can go right, left, or straight (not backwards). The thief will escape if he arrives at either the northern or southern edges.

Figure 1-1: The thief T starts where indicated. He is nine blocks from the northern, eastern, southern, and western borders, though only the first two are shown.

The police (P) want to let the thief move to see where T will go with his car, but they want to prevent the car from leaving the grid, at least for a while.

At every intersection, the thief chooses where to go except that the police, by their presence, can force T to go straight or to turn right or left. On the other hand, the police want to leave T as much freedom as possible. They therefore have to decide how to deploy their resources to achieve one of several outcomes.

1. The police want to control T’s direction at only five intersections. They know that T is extremely motivated to escape. How long (in terms of single block steps) at most will it take T to arrive at either the northern or southern border?

2. Suppose that the police want to prevent T from reaching the northern or southern borders. Therefore the police plan to control T’s direction m out of every n times for some m < n. What should m and n be to minimize the fraction of time P forces T to change directions while still preventing T from escaping?

3. How does your answer change if T can escape by reaching any border, including the eastern and western ones?