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$
  • 14
    $\begingroup$ If the robot cannot revisit cells, how can it revisit the starting cell? $\endgroup$ – Sneftel Sep 25 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$ – A. I. Breveleri Sep 25 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$ – Dmitry Kamenetsky Sep 26 at 0:30
14
$\begingroup$

I claim that

yes, this is possible.

Here's why:

enter image description here

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is correct! For reference these structures are called Golygons. $\endgroup$ – Dmitry Kamenetsky Sep 25 at 6:19
  • 3
    $\begingroup$ Looks like a duck $\endgroup$ – Jason Goemaat Sep 25 at 15:28
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.

| improve this answer | |
$\endgroup$
  • 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 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$ – Jaap Scherphuis Sep 25 at 21:45
  • 2
    $\begingroup$ oooh I like the 5.5 answer. Clever! $\endgroup$ – Dmitry Kamenetsky Sep 26 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?

| improve this answer | |
$\endgroup$
  • 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 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$ – Nomen nesco Sep 25 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 at 20:48
  • 1
    $\begingroup$ @Stiv that's a funny story :) $\endgroup$ – Dmitry Kamenetsky Sep 26 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).

| improve this answer | |
$\endgroup$
  • 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 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 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.