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?
$\begingroup$
$\endgroup$
3
asked Sep 25, 2020 at 2:00
-
14$\begingroup$ If the robot cannot revisit cells, how can it revisit the starting cell? $\endgroup$– SneftelSep 25, 2020 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. BreveleriSep 25, 2020 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 KamenetskySep 26, 2020 at 0:30
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
3
I claim that
yes, this is possible.
Here's why:
-
1$\begingroup$ This is correct! For reference these structures are called Golygons. $\endgroup$ Sep 25, 2020 at 6:19
-
3
-
$\begingroup$ If it looks like a duck and quacks like a duck then it is probably a duck :) $\endgroup$ Apr 16, 2021 at 1:52
$\begingroup$
$\endgroup$
3
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.
answered Sep 25, 2020 at 13:49
-
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$– KevinSep 25, 2020 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, 2020 at 21:45
-
2$\begingroup$ oooh I like the 5.5 answer. Clever! $\endgroup$ Sep 26, 2020 at 0:34
$\begingroup$
$\endgroup$
4
Ignoring the ambiguous phrasing about not being allowed to revisit any cell including the starting cell: wouldnt' the minimal solution be: +1i; +2i; -3i?
-
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$– StivSep 25, 2020 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, 2020 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$– StivSep 25, 2020 at 20:48
-
1
$\begingroup$
$\endgroup$
2
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).
-
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$– SneftelSep 25, 2020 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$– SneftelSep 25, 2020 at 13:03