City planning of tourists

8 posts in this topic

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites

Posted · Report post

square root (m*n)

0

Share this post


Link to post
Share on other sites

Posted · Report post

max(m,n) policemen

0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

one policeman needs to see each horizontal and vertical street.

actually it should be...

squareroot(m^2 +n^2)

Edited by phil1882
0

Share this post


Link to post
Share on other sites

Posted · Report post

max(m,n) policemen

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

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

m or n number of policeman whichever is greater.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.