Patulous Pegboard Polygons

Abstract

A problem in a recent competition was: Given a 2004 by 2004 square grid of dots, what is the largest number of edges of a convex polygon whose vertices are dots in the grid? Of course, the question can be asked for any value of 2004, say n. For n = 2, 3 and 4 it’s easy to see (Figure 1) that the answers are p = 2n: 4 6 8 Figure 1: The best polygons for n = 2, 3 and 4 The next three (Figure 2) are not quite so obvious: