Sunday, November 10, 2013

Solutions: Don't step on the grass

See the original problem

The "Don't step on the grass" puzzle was something I saw once, but at first I couldn't find it.  It turns out it came from Wu : Riddles, under the header "Samwise and Gandalf".  It involves Samwise trying to dig up a telephone line being used by Lord Sauron.  My flavor text is much more banal in comparison.

I was surprised at the depth of this puzzle.  Not only was every initial solution I found wrong, but so was every second solution.  Here I'll show some of the suboptimal solutions.  (The final solutions will be hidden as spoilers.)  Below each solution is the length of fence, assuming that the polygon has unit sides.

My first solution was to have an X across the square.

Square: 2*sqrt(2) = 2.828

This of course suggested radially symmetric solutions.  So I looked for the best radially symmetric solutions for the pentagon and hexagon.  For the pentagon, this involved a tricky geometric construction which I show below (the circle crosses the center of the pentagon, and line segments are colinear with the centers of circles).

Hexagon: 6*sqrt(3)/2 = 5.196
Pentagon: 4.396

Commenter Secret Squirrel found better solutions, so I immediately realized that radial symmetry was a bad constraint.  I soon found the following solutions.

square: 1+sqrt(3) = 2.732
pentagon: 3.728
hexagon: 4.5

Finding that square solution was a breakthrough, because it made me realize the importance of 120 degree angles.  To make a physics analogy, it's like you have bubbles.  Bubbles shape themselves to minimize surface area.  If three bubbles are adjacent to each other, they'll form flat surfaces with 120 degree angles.  This led to an improvement in the pentagon solution.

Pentagon: 3.580

I also found another solution to the pentagon, which is not quite as good.  Also, commenter Rain found a solution for the square which was 2+1/sqrt(2).

Pentagon: 3.588
Square: 2+1/sqrt(2) = 2.707

Even though the above two solutions are excellent, they could still be improved with 120 degree angles.  The hexagon solution was the right idea, but could be improved with a little rearrangement.  Here are the final solutions:

Square: sqrt(2)+sqrt(6)/2 = 2.639
Pentagon: 3.544
Hexagon: 1+sqrt(3)*2 = 4.464


Baumann Eduard said...

This remembers me the soap bubbles in Polygons, see

miller said...

Oh, neat!

My understanding of soap bubble physics is that the curvature of any surface is determined by the pressure difference between the bubbles. This means each surface must have constant curvature (either a straight line or circular arc). And since any given bubble is characterized by a single pressure, this leads to what you call Laplace's Rule on your page.

In my puzzle here, the area enclosed by fences doesn't matter, so it's effectively like all the bubbles have zero pressure. That's why we don't see solutions with curved surfaces.

Larry Hamelin said...

How do you know if you have the optimum solution?

miller said...

I don't know if I have the best solutions.