Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Mar 25, 2010

Street Watch

Source: http://www.math.utah.edu/~cherk/puzzles.html

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!!

7 comments:

  1. place N policemen all the diagonal of the grid

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

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

    ReplyDelete
  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) :)

    ReplyDelete
  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

    ReplyDelete
  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

    ReplyDelete