A robot is placed on some vertex of a 3x3 grid. At each move the robot can take one step (up, down, left or right) along the edge of the grid to the adjacent vertex, but it cannot go outside the grid. The robot can revisit vertices, but it cannot revisit edges. What is the most number of edges that it can visit?
2$\begingroup$ I expect the 4x4, 5x5, 6x6, 7x7, ... versions to come soon. Better answer the general version here. $\endgroup$– WhatsUpJun 23, 2022 at 9:38
$\begingroup$ hehe you know me too well. And I am sorry for creating similar puzzles. $\endgroup$– Dmitry KamenetskyJun 23, 2022 at 9:53
$\begingroup$ I thought for a moment that you'd asked this before but that was a slightly different question. $\endgroup$– Jaap ScherphuisJun 23, 2022 at 10:03
$\begingroup$ yes slightly different $\endgroup$– Dmitry KamenetskyJun 23, 2022 at 10:10
3$\begingroup$ Note that this is (almost) completely solved for arbitrary finite graphs. They key word is Eulerian path (en.wikipedia.org/wiki/Eulerian_path). Starting with any graph remove the minimal number of edges so that the remaining graph has at most 2 vertices of odd degree. Then, theorem: the remaining graph has a path that covers all edges. The (almost) part come from how many/ which edges to remove to get at most 2 vertices with odd degree. $\endgroup$– quaragueJun 23, 2022 at 11:01
I think the highest number of edges you can visit is
Each of the eight vertices on the edge of the grid (not in corners) has degree three which means we can visit, at most, two of these vertices more than once (at the beginning and at the end). Hence, six of these vertices will have edges coming from them not included in the path. The minimum number of edges missed in a path will thus be three as we can pair up these six vertices as the endpoints of the missing edges.
I number the vertices included in the path, together with highlighting the missed edges in red
2$\begingroup$ Nice work, well done. $\endgroup$ Jun 23, 2022 at 18:38
I believe I have the solution for the general $n \times n$:
As user quarague indicated in the comments, this problem boils down to finding the least number of edges to remove such that the remaining graph has two odd-degree nodes. That subgraph has a Eulerian path - a path that uses all the remaining edges. All the interior nodes already have an even degree so we only need to deal with nodes around the border. This means that all the deletions can be around the border to obtain the optimal result.
For even $n \geq 4$:
We can use the following pattern of deleted edges (shown in red). The two odd-degree nodes are shown with circles - they will be the endpoints of the path. This gives $2n^2$ remaining edges.
For odd $n \geq 3$:
We can use the following pattern of deleted edges. This gives $2n^2+3$ remaining edges. This matches the solution found by hexomino for $n=3$.
For completeness, $n=2$ is a special case, which can be solved like so:
$\begingroup$ Can anyone verify my logic here? $\endgroup$ Jun 25, 2022 at 12:11