Monday, September 23, 2013

Puzzle: Don't step on the grass

I was suddenly reminded of a geometric puzzle.  This puzzle is not original, but the thematic content is mine.

There is a patch of grass on a high school grounds.  It's shaped like a square (each side being one unit long).  The students aren't supposed to walk on it, but they do.  You could prevent them from walking on the grass by surrounding it with a fence.

But you can save on some fencing by exploiting a key fact about these high school students: they will only ever walk through the grass in straight lines.  So as long as you build enough fences to block all straight lines through the grass, you can prevent students from walking through it.  (Note that paths skimming the edge of the grass don't count, but paths cutting through the corners do count.)  What's the minimum length of fencing necessary?

If that puzzle is too easy, imagine that the grass is shaped like a regular hexagon.

I don't know if this will help, but there's a website which lets you construct geometrical shapes, as if you had a ruler and compass. Here is a square to start, and here is a hexagon.

I would have asked about a grass field shaped like a regular pentagon, but it's quite difficult.  Try it if you're brave.

See the solution

9 comments:

Secret Squïrrel said...

I can block all paths on the square patch with an amount of fencing totalling a bit over 2.8 units.

For the hexagon, assuming that its sides are also 1 unit long, I can do it using a smidge over 4.5 units of fence.

I also had a go at the pentagon. I can do that with a little over 3.5 units but I'm not convinced it's minimal.

I've been coy about my methods to give others a chance to have a go but I can provide more detail if the lengths aren't sufficient.

miller said...

I think your hexagon and pentagon solutions are improvements over mine. If you like, you can send them to my e-mail.

miller said...

Clearly I did not have the optimal solutions myself yet. I managed to match your hexagon solution of 4.5. I also figured out a way to do the square in under 2.8.

Rain said...

Clearly, I suck at geometry, as my solutions all involve more fencing than yours. I can solve the square with 2sqrt(2) units (about 2.8 units) of fencing, the pentagon with 5sin(54)/sin(72) units (the angles are in degrees) (about 4.25 units) and the hexagon with 3+3sqrt(3) units (about 8.2 units). My solutions are as follows (ignore the grey circle around each polygon):
square: http://upload.wikimedia.org/wikipedia/commons/thumb/a/a5/Regular_polygon_4_annotated.svg/200px-Regular_polygon_4_annotated.svg.png
pentagon: http://upload.wikimedia.org/wikipedia/commons/thumb/0/01/Regular_polygon_5_annotated.svg/200px-Regular_polygon_5_annotated.svg.png
hexagon: http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Regular_polygon_6_annotated.svg/200px-Regular_polygon_6_annotated.svg.png

miller said...

Rain,
That hexagon solution looks like a 6, rather than a 8.2.

It may help to focus a bit on the square. It turns out that there is a better solution than the 'X'. It may also help to consider the solution for a long rectangle. The rectangle's solution and square's solution vary continuously from one to the other.

Rain said...

Well, yes, of course it's a 6. *slaps forehead* My brain wasn't functioning properly, and I miscalculated an angle. Thanks for pointing it out! (3+3sqrt(3) is an awesome number, though...)

As for the (very) long rectangle, the obvious solution is one long side and the two short sides (in the limit when the long sides measure infinitely more than the short sides, the length of this is simply that of a long side), but as the rectangle approaches a square this becomes less and less effective compared to both diagonals (for a perfect square, three sides is 3 units long and two diagonals is 2sqrt(2) units long. (It would be interesting to calculate when exactly both short sides plus one long side equals both diagonals, but I'm too lazy to do it right now. I'm willing to bet the ratio between the long and short sides at that exact point is something like the golden ratio or the square root of a small integer.) I don't see how this solution to the rectangle would help me find the solution to the square, but a couple of minutes ago I managed to solve the square in 2+1/sqrt(2) (approximately 2.7) units. The solution is beautiful, and it's also analogous to the solution to every other regular polygon with more than four sides (at least to the polygons with an even number of sides, but I believe the ones with an odd number of sides also have analogous solutions). The pentagon requires 3+cos(54) (approximately 3.6) units, and the hexagon requires 9/2 units.

Cheers!

Rain said...

Also, it's interesting to note that, if L is the optimal fence length and P is the perimeter of the polygon, then the limit of L as the number of sides tends to infinity (i.e. as the polygon becomes a circle) is exactly P. Assuming the students are point particles, it's impossible to prevent them from walking over a circular patch of grass without enclosing the entire circle with a fence. For anyone who doesn't yet have the solution to the polygons (square, pentagon, etc) but wants a (very vague) hint, this could be it. =)

miller said...

2 + 1/sqrt(2) is actually a *better* solution to the square than the one I had in mind. The hint I gave you about rectangles was an attempt to direct you towards a 1+sqrt(3) solution.

But now that you've given me that number, I can find a better solution! The trick is that these solutions really like 120 degree angles for some reason.

It's also possible to improve your hexagon and pentagon solutions. :) I had worked out some better solutions while corresponding with Secret Squirrel.

Rain said...

The improvement you are talking about yields [2+sqrt(3)]/sqrt(2) (approximately 2.64) units for the square. That's the best possible solution with a fence having that shape (err, "broken arrow"?). Don't know whether there are any better solutions not involving that fence shape, though. And yes, I found the optimal angle to be 120 degrees for some reason.

Too lazy to do the pentagon and the hexagon right now, but I'll get back to you on them.

Thanks for posting such an interesting problem. I thought I had solved it fairly easily with my original x/star/asterisk solutions, but there's a lot more to it than meets the eye!