6
$\begingroup$

A robot starts on a cell in an infinite grid. On the first turn it can move 1 cell horizontally or vertically. On the $n$-th turn ($n>1$) it can move $n$ cells horizontally or vertically, but it cannot revisit cells (еxcept the starting cell). Is the robot able to come back to its starting cell?

$\endgroup$
3
  • 14
    $\begingroup$ If the robot cannot revisit cells, how can it revisit the starting cell? $\endgroup$
    – Sneftel
    Sep 25 '20 at 11:02
  • 1
    $\begingroup$ Dmitry is a puzzle master of hefty repute but in this case he has presented an incompletely specified problem, and has precipitately accepted Deusovi's answer before responding to Sneftel's request for clarification. $\endgroup$ Sep 25 '20 at 19:38
  • $\begingroup$ The intended wording should be "cannot revisit cells, except the starting cell". But I didn't think of it at the time and I won't change it now since we already have answers with the other interpretation. $\endgroup$ Sep 26 '20 at 0:30
14
$\begingroup$

I claim that

yes, this is possible.

Here's why:

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ This is correct! For reference these structures are called Golygons. $\endgroup$ Sep 25 '20 at 6:19
  • 3
    $\begingroup$ Looks like a duck $\endgroup$ Sep 25 '20 at 15:28
  • $\begingroup$ If it looks like a duck and quacks like a duck then it is probably a duck :) $\endgroup$ Apr 16 '21 at 1:52
8
$\begingroup$

While Deusovi has a perfectly valid answer to the question, there are other possibilities.

Firstly, there is a possible loophole that allows for a short solution.

If the robot shuts down as soon as it reaches its starting point, then the final turn does not need to be fully completed. In this case you can do it in $5.5$ turns:
1R, 2D, 3D, 4L, 5U, 3R
where the letters indicate the directions of the steps (Right, Left, Up, Down).

Even without that loophole, it is possible to

solve it in $7$ turns.
1R, 2D, 3L, 4D, 5L, 6U, 7R
Note that this is not a golygon since two moves (1 and 7) form a single side of this hexagon.

Proof this is minimal:

The total distance travelled must be even, because any displacement to the right must be compensated by an equal displacement to the left, and similarly for up and down.
Clearly $4$ turns is not sufficient without retracing steps. In $5$ and $6$ turns the robot would travel a distance of $15$ and $21$, but these are odd numbers so not possible. This means $7$ is minimal.

$\endgroup$
3
  • 2
    $\begingroup$ In that case, couldn't he do it on the second step? Step 1 move left 1, on the second move right 1then shut down? $\endgroup$
    – Kevin
    Sep 25 '20 at 21:22
  • 1
    $\begingroup$ @Kevin I suppose so, if you are only looking at the squares being visited. I was thinking of the path being a line, and that you are not allowed to revisit any point on the path (except the starting point), so then you cannot go back along the same path, even if it is for only one unit of distance. $\endgroup$ Sep 25 '20 at 21:45
  • 2
    $\begingroup$ oooh I like the 5.5 answer. Clever! $\endgroup$ Sep 26 '20 at 0:34
2
$\begingroup$

Ignoring the ambiguous phrasing about not being allowed to revisit any cell including the starting cell: wouldnt' the minimal solution be: +1i; +2i; -3i?

$\endgroup$
4
  • 1
    $\begingroup$ Hi, and welcome to Puzzling :) I'm not convinced that completely ignoring the requirement "he cannot revisit cells" is a legitimate strategy here - two cells other than the starting cell get revisited with this approach, which definitely breaks the rule. Since it's specified in the question, I think it's a pretty key component of it and this therefore doesn't answer the question as written. Sorry! $\endgroup$
    – Stiv
    Sep 25 '20 at 20:38
  • 1
    $\begingroup$ Thanks for the reply - I obviously had a brain-freeze and misread that only the endpoints of each move mustn't be revisiting cells. Wouldn't have been much of a puzzle then. Note to self: don't post after more then one glass of wine... $\endgroup$ Sep 25 '20 at 20:44
  • 1
    $\begingroup$ Easily done! It does make it rather trivial without that constraint! And wine is a dangerous thing - I once booked a yurt holiday in the middle of nowhere on the coldest weekend of the year (in January) after a bottle of red; I went on it too - NEVER AGAIN! :D $\endgroup$
    – Stiv
    Sep 25 '20 at 20:48
  • 1
    $\begingroup$ @Stiv that's a funny story :) $\endgroup$ Sep 26 '20 at 0:36
0
$\begingroup$

1i + 2j - 3j - 4i - 5i - 6j + 7j + 8i = 0(i+j) . The sequence of positions is: 0 i i+2j i-j -3i-j -8i-j -8i-7j -8i 0 The only repeat is zero (vector).

$\endgroup$
2
  • 1
    $\begingroup$ The endpoints are not repeated, but cells along the way are repeated. For instance, the robot visits i+j before and after the second step. $\endgroup$
    – Sneftel
    Sep 25 '20 at 13:01
  • 2
    $\begingroup$ (If the question were changed to allow this, of course, it would be simpler to just do i + 2i - 3i.) $\endgroup$
    – Sneftel
    Sep 25 '20 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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