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:
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:
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?
Answer
My best solution is:
Follow the red path, then go back and forth along the violet line. It takes only $68$ points!
Picture:
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
No comments:
Post a Comment