Third Millennium International Mathematical Olympiad 2009
Grade 9
Problem 6

Through the vertices of a 9×9 grid square draw a broken line with nodes at the grid points that encloses the least possible area.

Solution

|Up| |Contact| |Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

No one tried to solve this problem. No one posted a request to clarify the conditions of the problem even though during the olympiad a chat facility was available at all times.

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.

|Up| |Contact| |Front page| |Contents| |Geometry|

Copyright © 1996-2018 Alexander Bogomolny