Street Watch


Problem: Salt Lake City looks like a rectangle crossed with M streets going from North to South and with N streets going from East to West. The city is frequently visited by tourists who suppose to run around in the buses. The Utah governor wants to vigil all moves of the buses. He plans to put policemen at some intersections to watch all the buses moving on the streets visible from that intersections. What is the minimum number of policemen needed for the bus watch?

Update (26/03/10)
Solution: Posted by Ashu and Aman in comments!!


  1. place N policemen all the diagonal of the grid

  2. shud hav read the problem properly.
    agree with Ashu.

  3. min(M,N) + |M-N| sounds correct.
    @connect2ppl : The grid is not square.

  4. BTW,
    min(M,N) = (|M+N| - |M-N|)/2
    max(M,N) = (|M+N| + |M-N|)/2

    So, min(M,N) + |M-N| = max(M,N)

    Hence, the answer is max(M,N) :)

  5. @pratik ya it is max(M,N)
    i wrote it that way to imply the way policeman should be kept

    min(M,N) diagonally
    n then mod(M-N) to cover extra streets

  6. no offence, but I have no idea why anyone would think of min(M,N) + |M-N| :D Ashu answered it and then connect2ppl agreed, and then aman agreed, and then you proved it! :D

    I wonder why it only occurred to me as max(m,n) first :P thanks @ PP for pointing it out but I was rather shocked on seeing the answer initially :D


Post a Comment

Popular posts from this blog

Asking a girl out

Coins Puzzle

Consecutive Heads