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

Comments

  1. Unknown12:53 PM, March 26, 2010

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

    ReplyDelete
  2. Anonymous1:22 PM, March 26, 2010

    place N policemen all the diagonal of the grid

    ReplyDelete
  3. Anonymous3:44 PM, March 26, 2010

    shud hav read the problem properly.
    agree with Ashu.

    ReplyDelete
  4. Anonymous3:49 PM, March 26, 2010

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

    ReplyDelete
  5. Pratik Poddar4:26 PM, March 26, 2010

    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
  6. Unknown9:14 PM, March 26, 2010

    @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
  7. Aytidaa Madras1:33 AM, March 27, 2010

    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

Post a Comment

Popular posts from this blog

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 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially)
Read more