Tuesday, June 23, 2015

Solution to Perimeter Puzzle

On a six-by-six grid, shade 28 squares so that the perimeter of the resulting shape is (a) as small as possible (b) as large as possible.

This puzzle was my Father's Day indulgence. To maximize the perimeter, I intuitively created a "checkerboard" design inside the grid:

The perimeter of this shape is 56—and in fact, 56 is the greatest possible perimeter. To see this, consider any shading of 28 squares whatsoever, leaving 8 squares unshaded. One way to compute the perimeter of the resulting shape is as follows:

(1) For each unshaded square, count +1 for each neighbor that is shaded.

(2) For each shaded square on the boundary of the grid, count +1.

(3) For each shaded corner, count an additional +1.

The total for (1) must be less than or equal to 8 \(\times\) 4 = 32, because there are 8 unshaded squares and an unshaded square can have at most 4 shaded neighbors. Meanwhile, there are 20 boundary squares, so the total for (2) must be less than or equal to 20. And there are 4 corners, so the total for (3) must be less than or equal to 4. Hence, the total perimeter must be less than or equal to 32 + 20 + 4 = 56. QED

The smallest possible perimeter is 22. I found this value intuitively by creating a 5-by-5 block with 3 squares left over. I couldn't think of an optimality proof, so I wrote a computer program to analyze all 30,260,340 possible ways to shade 28 squares on a six-by-six grid. Sure enough, the smallest possible perimeter is 22, attained in the following distinct ways:

After that, I thought some more about how to find the minimum perimeter in some other way besides brute force. You can convert the problem to a quadratic integer program by assigning a variable \(x_i = 0, 1\) to each square and implementing the perimeter computation using algorithm (1)-(3) above. But I wanted an insightful approach. 

It seemed that what I wanted to know was the minimum perimeter of an orthogonal polygon of given area. Googling this question got me nowhere, however.

So by generalizing my simple-minded \(28 = 5\times 5 + 3\) approach, I conjectured that the minimum perimeter would be \(2({\rm Fl}(\sqrt{n})+n\,{\rm div}\,{\rm Fl}(\sqrt{n})+1^*)\), where \(n\) is the number of squares in the polygon, \({\rm Fl}(\cdot)\) is the Floor function, and the asterisk on the 1 means that you only add the 1 if \({\rm Fl}(\sqrt{n}) (n\,{\rm div}\,{\rm Fl}(\sqrt{n})) < n\). This conjecture just says that you can find the minimal perimeter by arranging the shaded squares in a nice rectangular shape, with the extra tiles stacked nicely on the side.

For \(n=1,2,3,\dots\) you get the sequence 4, 6, 8, 8, 10, 10, 12, 12, 12, 14, 14, 14, ....  I figured it couldn't hurt to search for this sequence in the Online Encylopedia of Integer Sequences. And what do you know? It was the minimal perimeter sequence that I was looking for!

The citation given for this result is Harary and Harborth (1976), "Extremal Animals," Journal of Combinatorics, Information & System Sciences 1(1), pp. 1–8. I don't find a PDF freely available online, but the second citation can be downloaded here. A simpler formula for the sequence is \(2{\rm Cl}(2\sqrt{n})\), where \({\rm Cl}(\cdot)\) denotes the Ceiling function. Harary and Harborth found this result by building an optimal configuration in a spiral pattern.

I see now that I would have had better luck at the outset if I'd googled "minimal perimeter polyomino." The first result for that search is this 2005 paper by Kurz, which extends Harary and Harborth by counting the number of optimal configurations. The formula for the number of optimal configurations is pretty complicated, but I think that for the case \(n=28\) there are supposed to be 6 distinct configurations with minimal perimeter 22. However, I only saw 5 distinct optimal configurations during my exhaustive search. I assume the discrepancy arises from the fact that Kurz will have counted the 4-by-7 polyomino, which has perimeter 22 (and hence is optimal too) but which doesn't fit inside the six-by-six grid that constrained our puzzle.

Just for fun, I'll end with a histogram showing how often each perimeter value occurs among the 30,260,340 possible configurations:

The most common perimeter value is 40, attained for example by this configuration:

Postscript: The Online Encyclopedia of Integer Sequences was recently the subject of a newspaper item in The Guardian; read it here. OEIS is supported by donations—having used the tool to such good advantage here, I have donated to them today.

No comments: