Home > Problem of the Week > Archive List > Detail

<< Prev 1/20/2008 Next >>

Mathville's Police Force

The town of Mathsville is shaped like a rectangle with Main Street as its four-sided perimeter. The only other streets in Mathsville run either north-south (5 of them) or east-west (3 of them).

Next year, Mathsville will be hosting the 15th annual Math Olympics and to gear up the town, Mayor Van Euler wants to place a policeman such that every part of every street is being watched. Policemen placed at street corners can see an infinite distance, but not around corners. What is the minimum number of policemen the Mayor will need to hire?

Can you generate a general rule that applies to a town with n north-south streets and m east-west streets?

Finally, does your rule apply to the town of Parallogramville, where the town is in the shape of a parallelogram and Main Street is again its perimeter?


Source: JD (WWU student)

Hint: Draw a picture of a grid representing Mathville...place lima beans (or?) at street vertices to test possible policemen deployments.


Solution Commentary: JD's commentary: For the first case, draw a rectangle with 5 vertical lines and 3 horizontal lines. You have to place a policeman (dot) on every vertical line, including Main Street. Shift the policemen vertically until you have at least one policeman on every horizontal line. Thus, you need 7 policemen.

For the general case, you will need 2 more policemen that n or m...which ever is the higher number.

The general rule does not work in Parallelogramville. Suppose you drew 2 north-south streets at the vertices of the parallelogram to create right angles, and then 1 east-west street. You could place 2 policemen at the opposing vertices of the parallelogram and then 1 policeman on the east-west street. So only a total of 3 policemen are needed in this case.