Log In

Vigilance campaign

Posted on: July 30th, 2013 by
7

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


7 Responses to Vigilance campaign

  1. Pratik Poddaar had this to say about that:

    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

    • admin had this to say about that:

      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?

      • Sid Hollander had this to say about that:

        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.

  2. Shrey had this to say about that:

    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?

  3. Shiny had this to say about that:

    Yes Max(M,N).


{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}