Maximum polygons on a square grid of dots


Problem

On a 4x4 grid of points, make a polygon with as many sides as you can, by connecting pairs of points to form edges. The polygon may not intersect itself. Further, none of its vertices can lie between two other vertices connected by an edge. What is the largest number of sides possible, and why?

What solutions can you find for other nxn grids? What about wxh grids? What about polyhedra on nxnxn grids? wxhxd grids?


Solution

The maximum number of edges, for a 4x4 grid, is 16, and here's why: Every edge can be cut exactly in half. Call each of these a half-edge. Notice that each point on the grid can be connected to at most 2 half-edges. Thus, a 4x4 grid could have 16 * 2 = 32 half-edges maximum. But 32 half-edges is the same as 16 full edges. So a 4x4 grid has, at best, a 16-gon. But we still don't know that such a 16-gon exists. Luckily, for 4x4 grids, a polygon having the greatest number of sides exists. Here's one such 16-gon:

It turns out that n-gons are possible for all n×n grids except when n = 3 or 5. A proof is here, although I've yet to read it or think about this problem further, so I'm not sure how difficult the proofs are.