Mathville's Police Force
The town of Mathsville is shaped like a rectangle with Main Street as its foursided perimeter. The only other streets in Mathsville run either northsouth (5 of them) or eastwest (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 northsouth streets and m eastwest 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 northsouth streets at the vertices of the parallelogram to create right angles, and then 1 eastwest street. You could place 2 policemen at the opposing vertices of the parallelogram and then 1 policeman on the eastwest street. So only a total of 3 policemen are needed in this case.
