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
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
