This week the #puzzle is: How Greedily Can You Mow the Lawn? #geometry #area #volume #GreedyAlgorithm (Link at the bottom.)

You’re mowing a circular lawn with a radius of 1 unit. You can mow in straight strips that are 1 unit wide.

The fewest number of passes you would need to mow the entire lawn is two, as shown below. In one pass (shown in blue) you can mow half the circle, and in the second pass (shown in red) you can mow the other half of the circle.

However, instead of minimizing the number of passes, you greedily choose how to orient each pass so it cuts as much of the unmowed grass as possible. A pass doesn’t have to go through the center of the circle and can be in any direction, but must be straight and cannot bend.

With this “greedy” approach, how many passes will it take for you to mow the entire lawn?

And for extra credit:

Instead of mowing a two-dimensional lawn, now you’re boring cylinders through a three-dimensional unit sphere. Each cylinder has a diameter of 1 (and a radius of 1/2).

Once again, you are greedily choosing the orientation of your boreholes so that they carve out as much of the remaining sphere as possible with each pass.

With this “greedy” approach, how many passes will it take for you to pulverize the entire sphere?

Highlight to reveal (possibly incorrect) solution:

Desmos 1

Let us go through what choices we have.

• Obviously the 1st pass is simply symmetrical, the middle of the pass going through the center. If it didn’t go through the center, it would cover less area. In my model this pass is horizontal.
• The 2nd pass might simply be the same, just in the other direction? It would get a lot of the 2 remaining bits, leaving 4 bits behind. If this pass is indeed vertical, again, the middle of it goes through the center, to cover as much area as possible. This area would be 0.9132. [ETA: Oops, should be 2 * 0.9132. Wrong conclusions follow.]
• Then I would need 2 passes to cover the remaining 4 bits, either 2 horizontal (or vertical) passes, covering 2 bits every time, or 2 passes crisscrossing, one going up, the other going down, again covering 2 bits every time.
• That would be 4 passes in all.
• Can it be done in a better way?
• I need at least 3 passes, because I can’t cover the 2 remaining bits after the 1st pass in just 1 more pass.
• What if the 2nd pass simply covered 1 of the remaining bits? This area turns out to be 0.6142. So this wouldn’t happen, as it is less than 0.9132.
• There’s an interesting option. What if the 2nd pass was tilted just right, so that it wouldn’t create 4 remaining bits, but only 2? This covers an area of 1.0472. Yes! This is indeed possible. A 3rd pass, tilted the other way, would cover the rest.
• I don’t know whether this is exactly the optimal way to do things. But it proves, that 3 passes can do the job.

And for extra credit:

Desmos 2 Researchgate

There’s something interesting going on at Researchgate, suggesting that a non-greedy solution would need at least 20 circles / 10 cylinders. Because the angular radius of each circle is 30^o.

This one is just me guessing most of the way, illustrated in Desmod:

• 1st and 2nd pass are symmetrical, with the middle of the cylinder passing through the center. They are also perpendicular.
• I assume the same goes for the 3rd pass.
• The next 4 passes (red in my model) are closing some gaps on the surface of the sphere between the 3 existing passes. E.g. one of these cylinders has x=y=z in the middle.
• This leaves 8 bits. I would need 4 more passes to cover these, again using cylinders passing through the center.
• Using this method, with the whole surface covered and all cylinders passing through the center, all of the volume has been covered.
• This would suggest 11 passes.

***

How Greedily Can You Mow the Lawn?