18
$\begingroup$

Isaac is in need of money to buy himself a car so he can go to the beach with his friends, so he's decided to start a lawn mowing business. When mowing lawns, he needs to make sure he gets an even tan so when he ends up going to the beach he looks good. We will consider Isaac to have four sides (front, back, left, and right) and each time he mows a new square meter he gets a point worth of tanning for that side. In the end, he needs to have an equal number of points for each side. Another way to look at this is that he needs to be traveling each direction an equal number of times. Here's an example:

enter image description here

Assuming that up is North: if Isaac goes from A to B, he gets one point of tanning for traveling East. If he moves back to A, then he gets a point of tanning for traveling West. This would not give him an even tan because he didn't move North or South, so he would have to move up/down on the grid to get an even tan. Moving from A to B would also mow each of those, leaving the bottom two squares to be mowed.

Isaac's first customer is Mr. Banks. Here's an overhead view of his yard:

enter image description here

The blue space is the garage where Isaac starts mowing the lawn. He wants to mow the entire lawn and end up back at the garage, while getting an even tan and also using the least amount of gas. He can mow over the same spot twice, but it uses gas both times. Each square he mows over uses 1 unit of gas. Will he be able to get an even tan? If not, why? If he can, what route minimizes the gas used?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ This puzzle needs a "white people" tag. haha $\endgroup$
    – JLee
    Commented Jun 4, 2015 at 18:05
  • 1
    $\begingroup$ If he visited each square on the lawn once and only once, he would end accumulating 63 or 64 points of tan? Basically, do we count a point of tan for the blue square? $\endgroup$
    – tfitzger
    Commented Jun 4, 2015 at 18:23
  • $\begingroup$ @tfitzger he would accumulate 64 points, as you are counting each time he moves. He has to move into each green square once, then at the end he moves to the blue square. $\endgroup$
    – MisterEman22
    Commented Jun 4, 2015 at 18:40
  • $\begingroup$ I think answering "Will he be able to get an even tan?" is trivial. The more interesting question is to minimize the amount of gas used. $\endgroup$
    – Engineer Toast
    Commented Jun 4, 2015 at 19:07
  • 1
    $\begingroup$ "I got two twos and a four! I'm an eight!" -Ross Gellar. $\endgroup$
    – Ian MacDonald
    Commented Jun 4, 2015 at 22:34

2 Answers 2

Reset to default
17
$\begingroup$

My best solution is:

Follow the red path, then go back and forth along the violet line. It takes only $68$ points!

Picture:

enter image description here

Basic calculations:

Up and down consume 17 points each, while left and right only 15 (still on the red path). Finally, you go back and forth along the violet line to reach 17. Total is $17\times4=68$

Is it possible to improve?

Sadly you can't! The lower bound is $16\times4=64$ moves, achieved when you consume $16$ points for each direction. Though, there's no Hamiltonian cycle that satisfies this condition, it was proved by @Joel Rondeau here

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Given that the lower limit is $64$, I'd say that this is probably optimal. $\endgroup$
    – Engineer Toast
    Commented Jun 4, 2015 at 19:20
  • 1
    $\begingroup$ This puzzle essentially asks for a proof that that 64 is impossible, and there is an accepted answer. $\endgroup$
    – Julian Rosen
    Commented Jun 4, 2015 at 19:36
  • $\begingroup$ @JulianRosen Thanks! It's exactly what I was looking for! I've included a link to that proof in my answer, since it belongs to Puzzling and copying it would be pointless. $\endgroup$
    – leoll2
    Commented Jun 4, 2015 at 19:43
  • $\begingroup$ Nice answer. How did you arrive at it? $\endgroup$
    – JLee
    Commented Jun 5, 2015 at 3:01
  • $\begingroup$ Good, I was hoping that if nobody could find a 64 one, then someone would be able to prove that you can't get 64. $\endgroup$
    – MisterEman22
    Commented Jun 5, 2015 at 3:57
9
$\begingroup$

I feel like the impossibility proof from the other question was a bit lacking in that it wasn't totally clear that every possible path could be generated by 2x2 squares. So here is another impossibility proof for $64$.

After drawing some possible closed curves of lengths $64$, you might start thinking of each possible solution as a big square with indentations. And in fact you can one at a time "pound out" the indentations to get back to the big square. Here is a picture:

enter image description here

Each time you "pound out" a part of one of these indentations, you remove a "domino" worth of lawn in the 6x6 interior of the big square, and you lose either two vertical steps or two horizontal steps in the tanning process. Could there be an equal number of vertical and horizontal steps removed in this process? Well, no. This is equivalent to tiling a 6x6 chessboard with an equal number of horizontal and vertical dominoes, which cannot be done.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.