111. The city has a plan view of a rectangle divided into cells: $n$ streets are parallel to each other, $m$ others intersect them at right angles. On the city streets - but not at the intersections - there are police officers. Each police officer reports the number of the car passing by, the direction of its movement, and the time it passed. What is the minimum number of police officers needed to be placed on the streets so that their reports can uniquely reconstruct the path of any car traveling on a closed route (the route does not pass through the same street segment twice)?
111. Answer: the smallest number of police officers is $(m-1)(n-1)$.

If the police officers are placed in the required manner, the entire grid of streets breaks down into some number $k$ of pieces that do not contain closed routes (cycles), otherwise

![](https://cdn.mathpix.com/cropped/2024_05_21_7b8a6b2625543c3dae75g-147.jpg?height=238&width=488&top_left_y=1187&top_left_x=105)

Fig. 69 shows a cycle along which one can travel without being noticed by any of the police officers. If the remaining piece of the grid contains $p$ intersections, then it contains exactly $p-1$ street segments (see problem 8). Since there are a total of $m \cdot n$ intersections, the number of segments without police officers is $m n-k$. The total number of street segments is $2 m n-m-n$. Therefore, the number of occupied segments is

$$
m n-m-n+k \geqslant(m-1)(n-1)
$$

An example of the required placement of $(m-1)(n-1)$ police officers is shown in Fig. 59.