A city has M roads from north-south and N roads from east-west. The roads are small enough that the entire road is visible from any point on the road. The governor wants to monitor the roads, so he wishes to place policemen at intersections. What is the minimum number of policemen needed so that the entire road network is visible?

- via Math Puzzles

Max(m,n).

For Number of policemen = Max(m,n) - we can have a construction where the entire road network is visible

For Number of policemen < Max(m,n) - we can prove that at least one road is not being monitored

Hence, proved

Are you sure? In a 5x3 road, I can simply place 3 cops at (1,1),(2,2) and (3,3). Doesn't that suffice?

I believe that on a 5 x 3 road there is no pair (3,3) because this would mean that there are at least 4 roads in both directions. I assume that the axis count as roads.

Yea you are right.

When the question says 'so that the entire road network is visible', does it mean that all the intersections are visible or that the entire length of all the roads are visible?

Good question. It seems Pratik is right after all.

Yes Max(M,N).