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

min(M,N) + mod(M - N)

ReplyDeleteplace N policemen all the diagonal of the grid

ReplyDeleteshud hav read the problem properly.

ReplyDeleteagree with Ashu.

min(M,N) + |M-N| sounds correct.

ReplyDelete@connect2ppl : The grid is not square.

BTW,

ReplyDeletemin(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) :)

@pratik ya it is max(M,N)

ReplyDeletei 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

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

ReplyDeleteI 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