Saturday, June 27, 2015

The Perimeter Puzzle Under an Additional Constraint

A reader sent this configuration for the perimeter puzzle:

This suggests a new version of the puzzle:

Maximize perimeter among configurations like the one above, namely: (1) The boundary doesn't self-intersect; and (2) there are no "holes."

(Requirement (1) is saying that we don't allow "kitty-corner" shaded squares, that is, two shaded squares that touch corners, with the other two squares meeting at that corner being unshaded.)

I tried my hand at this and was unable to improve on the reader's example, which has perimeter 40. Here are my best attempts, which also have perimeter 40:

Is 40 maximal? Well, it is not hard to see that a tame shape cannot have perimeter greater than 46. To see this, consider that if any of the 8 unshaded squares had 4 shaded neighbors, then because of the no-kitty-corner constraint, that unshaded square would have to be fully surrounded by shaded squares, that is, the unshaded square would be a hole. But by assumption there are no holes, hence each unshaded square must have 3 or fewer shaded neighbors. Moreover, at least one unshaded square must touch the boundary of the grid, or else the 8 unshaded squares would form a great big hole. So it follows by algorithm (1)–(3) of my last post that the perimeter must be less than or equal to $8\times 3 + 19 + 4 = 47$. But the perimeter has to be even, so the perimeter must be less than or equal to 46.

I don't actually think there is a tame configuration with perimeter 46—the greatrest value attained seems to be 40.

For what it's worth, I wrote some computer code to identify the tame configurations among the 30 million or so in the full space. (It might have been easier to chuck my old work and build up the tame configurations from scratch, but I had a body of commands sitting there, so....) First I culled the kitty-corner cases, and then because it was easy I culled the single-square holes. For the remaining configurations, I wrote a function to convert the boundary into a graph-theoretic object, and then I used a built-in function to determine whether that graph was a single connected component. A total of 1,512,395 configurations survived the sorting process. Of these, 143,920 had perimeter 40, and none had perimeter greater than 40. So if my code does what it's supposed to do, then this is the maximum value.

Just for interest, here are some randomly chosen maximizers from the computer run: