BrainDen.com - Brain Teasers
• 0

# City planning of tourists

## Question

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 frequented by tourists who are suppose to ride around in the busses. The Utah governor wants to controll all moves of the busses. He plans to put policemen at some intersections to watch all the busses moving on the streets visible from that intersections. What is the minimum number of policemen needed for the bus watch?

## 7 answers to this question

• 0

max(m,n) policemen

##### Share on other sites
• 0

square root (m*n)

##### Share on other sites
• 0

one policeman needs to see each horizontal and vertical street.

actually it should be...

squareroot(m^2 +n^2)

Edited by phil1882

##### Share on other sites
• 0

max(m,n) policemen

Does this ensure they can see all the busses, or just all the intersections?

##### Share on other sites
• 0

max(m,n) policemen

Does this ensure they can see all the busses, or just all the intersections?

The entire grid of the streets can be observed by max(m,n) policemen, not just the intersections, so yes, they will see all the buses.

##### Share on other sites
• 0

m or n number of policeman whichever is greater.

##### Share on other sites
• 0

I think this might be right.

Suppose M<N.

Then, keeping one policeman each at the junctions along the diagonal of a square of side M will take care of M number of streets.

And N-M policemen are required who can stand at any point on streets from east to west which does not belong to the M*M square.

## Create an account

Register a new account