Mar 25, 2010

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


Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20...