This month the #puzzle is: Math puzzle: The homesick rover #addition #sum

Far away, on a large, rocky exoplanet, a rover from Earth has just arrived on a mission of exploration. But the poor thing doesn’t want to explore. The moment it begins moving, it grows homesick and wants nothing more than to return to the very spot where it began. Unfortunately, it has received very explicit instructions. The first day, it must travel one kilometer forward in a straight line, then turn 90 degrees. The second day, it must travel two kilometers forward, then turn 90 degrees. The third day, it must travel three kilometers forward, then turn 90 degrees. The fourth day, it must travel four kilometers forward, then turn 90 degrees. And so on, for the duration of an eight-day mission.

The rover wants to return to the site where it landed. But it can choose only which direction to turn, left or right, at the end of each day. How can the rover end the eight-day mission back at its landing site?

And as a bonus:

A hundred rovers with the same set of instructions have been sent to other large, rocky planets, each with a different mission length, ranging from one day to 100 days.

How many of these rovers can end their missions back at their landing sites?

Math puzzle: The homesick rover

(Possibly incorrect) solution:

Desmos

Thoughts:

• The rover travels 1 km in some direction on day 1. Let’s call it north.
• On day 2 it travels 2 km either east or west.
• On day 3 it travels 3 km either north or south.
• And so on for 8 days.
• It must go the same amount north as south. It travels 1+3+5+7 = 16 in all. It must go 8 north and 8 south. This can be achieved by traveling e.g. 1+7 north and 3+5 south.
• Same principle for east and west. 2+4+6+8 = 20. 2+8 = 4+6 = 10.

And for the bonus:

Spreadsheet

Thoughts:

• For 100 rovers, with 1-100 day missions, some are excluded right away.
• Let’s say the sum of all the odd numbers is o, and the sum of all the even numbers is e.
• Both o and e have to be even.
• Therefore o is a sum of an even number of numbers.
• For a 1 day mission, o = 1, e = 0. Out. o is odd.
• For a 2 day mission, o = 1, e = 2. Out. o is odd.
• For a 3 day mission, o = 4, e = 2. Possible?
• The next step is, that each sum has to break down into 2 equal sums. But we can’t break 1+3 into 2 equal sums. So this is out too.
• For a 4 day mission, o = 4, e = 6. Out because of 4.
• It’s not enough to say, that o and e are both even, or that o is a sum of an even number of numbers.

Let’s look at the general case for odd numbers.

• o = 1+3+…+n, where n is odd.
• We already know, there has to be an even number of numbers. There are 2k numbers, where k is an integer.
• o = 1+3+…+(4k-1)
  • = 2-1 + 4-1 + … 4k-1
  • = 2 + 4 + … + 4k – 2k
  • = 2(1+2+…+2k) – 2k
  • = 2 * 2k/2 * (1+2k) – 2k
  • 2 * k * (2k+1) – 2k
  • 4k² + 2k – 2k
  • 4k²
• The odd numbers have to break down nicely into 2 sums, each 2k².
• k = 1 doesn’t work, 1+3 can’t be broken down to 2 sums of 2.
• k = 2 works, 1+3+5+7 = 1+7 + 3+5 = 2 * 8.
• k = 3 works, 1+3+5+7+9+11 = 7+11 + 1+3+5+9 = 2 * 18.
• k = 4 works, the sum has 8 numbers, the 4 innermost and the 4 outermost have the same sum, 1+3+13+15 = 5+7+9+11 = 32. In general, this can be done when k is divisible by 4.
• k = 5 works, 19+17+13+1 = 3+5+7+…+16 = 50.
• k = 6 works, 23+21+19+9 = (the rest) = 72.
• k = 7 works, 27+25+23+19+3+1 = 98
• (so far I am just constructing a sum, to see whether it can be done)
• k = 8 works, k = 2 * 4
• Given the first 2k odd numbers, can I always find a sum of 2k²?
• Let’s look at the sum of the m top odd numbers:
• 4k-1 + 4k-3 + … + 4k-2m+1
  • = m/2 * (4k-1 + 4k-2m+1)
  • = m/2 * (8k – 2m)
  • = m * (4k-m)
• I create a spreadsheet and look at my options. If for each k I can find an m, so that the difference between 2k² and m * (4k-m) is small enough to be filled with small, odd numbers, I am home.
• Apparently the only k, this doesn’t work for, is 1.
• For an n day mission, if there are 2k odd numbers (meaning n = 4k or n = 4k-1), and k is an integer, 1 < k, then we can get the sums of odd numbers to work.
• This means 7, 8, 11 and 12 might work. And we have already checked, that regarding the odd numbers, they do.

Now let’s look at the even numbers.

• e = 2+4+…+n, where n is even.
• e = n/2 * (2+n)/2
  • = n * (2+n) / 4
  • = (n² + 2n) / 4
• This has to split up nicely into 2 sums of (n² + 2n) / 8.
• So n² + 2n is divisible by 8.
• We know n is even, so it could be written as 2k.
• n² + 2n = (2k)² + 2*2k
  • = 4k² + 4k
  • = 4k * (k + 1)
• This is divisible by 8 when k is divisible by 2 or k is odd — so always!
• n = 2. This still fails, because 2 is only 1 number and can’t be split up into 2 sums.
• n = 4. This still fails, 2+4 can’t be split up.
• n = 6. 2+4+6 = 2+4 + 6 = 2 * 6.
• n = 8. Already done.
• n = 10. 2+4+6+8+10 = 2 * 15? Oh wait. e/2 also has to be even, because it’s a sum of even numbers. So this fails.
• e/2 = 4k * (k + 1)/8
  • = k * (k+1)/2
• If 2 divides k:
  • k/2 * (k+1)
  • This is even when k/2 is even.
• If 2 divides k+1:
  • k * (k+1)/2
  • This is even when (k+1)/2 is even.
• New rule: Either k or k+1 is divisible by 4.
• n = 10. k = 5. We need (5+1)/2 = 3 to be even, and it isn’t.
• n = 12. k = 6. k is even, but k/2 = 3 isn’t. e = 42. e/2 = 21. Fail.
• n = 14. k = 7. k+1 = 8 is divisible by 4. e = 56. e/2 = 28. 1 of the sums could be 14 + 12 + 2. Success.
• n = 16. k = 8, divisible by 4. e = 72. e/2 = 36. 1 of the sums could be 16 + 14 + 6. Success.
• n = 18, k = 9, k+1 = 10, neither divisible by 4. Fail.
• n = 20, k = 10, k+1 = 11, neither divisible by 4. Fail.
• n = 22, k = 11, k+1 = 12, divisible by 4. e = 132. e/2 = 66. 1 of the sums could be 22 + 20 + 18 + 6.
• n = 24, k = 12, divisible by 4. e = 156. e/2 = 78. 1 of the sums could be 24 + 22 + 20 + 18.
• At this point I predict: For an n day mission, if there are k = n/2 even numbers (meaning n = 2k or n = 2k + 1), if either k or k+1 is divisible by 4, then we can get the sums of even numbers to work.

Putting the 2 rules together:

• For an n day mission, if there are 2k odd numbers (meaning n = 4k or n = 4k-1), and k is an integer, 1 < k, then we can get the sums of odd numbers to work.
• At this point I predict: For an n day mission, if there are k = n/2 even numbers (meaning n = 2k or n = 2k + 1), if either k or k+1 is divisible by 4, then we can get the sums of even numbers to work.

Let’s write this another way.

• The mission has n days.
• If x is an integer, 1 < x, n = 4x or n = 4x-1, success for the odd numbers.
• If y is an integer, n = 2y or n = 2y + 1, y or y+1 divisible by 4, success for the even numbers.

n	x	y(+1)	Result
1	fail		fail
2	fail		fail
3	fail		fail
4	fail		fail
5	fail		fail
6	fail		fail
7	2	3+1	success
8	2	4	success
9	fail		fail
10	fail		fail
11	3	fail	fail
12	3	fail	fail
13	fail		fail
14	fail		fail
15	4	7+1	success
16	4	8	success
17	fail		fail
18	fail		fail
19	5	fail	fail
20	5	fail	fail

This develops into a pattern. These work:

• 7 and 8.
• 15 and 16.
• 23 and 24.
• …