Third Millennium International Mathematical Olympiad 2009
Grade 9
Problem 6

Solution

Copyright © 1996-2010 Alexander Bogomolny

The question is about the area of a shape on a square grid. The most applicabale tool to attack such a problem is Pick's theorem. According to Pick's theorem, any closed broken line with nodes at the grid points encloses area A = I + B/2 - 1, where I is the number of grid points in the enclosure and B is the number of grid points on the curve (i.e., the boundary of the enclosure.)

So the fewer points the line contains and the fewer points that is passes through the smaller is the area it encloses. The absolute minimum of 1/2 is achieved by any grid triangle (B = 3) with no internal points (I = 0.) For this interpretation, the problem has many solutions.

However, it may be assumed that the size of the grid has been specified for a reason. A sensible interpretation of the problem would restrict the search for a solution to the broken lines that pass through as many grid points as possible. It is easy to construct the lines that pass through all 81 points. (As a curiosity, any second step approximation to the Peano curve fits the bill. But there are simpler solutions.) For all these curves, I = 0 and B = 81, making the enclosed area 39.5.

Copyright © 1996-2010 Alexander Bogomolny