3
$\begingroup$

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?

enter image description here

$\endgroup$
7
  • 2
    $\begingroup$ I expect the 4x4, 5x5, 6x6, 7x7, ... versions to come soon. Better answer the general version here. $\endgroup$
    – WhatsUp
    Jun 23 at 9:38
  • $\begingroup$ hehe you know me too well. And I am sorry for creating similar puzzles. $\endgroup$ Jun 23 at 9:53
  • $\begingroup$ I thought for a moment that you'd asked this before but that was a slightly different question. $\endgroup$ Jun 23 at 10:03
  • $\begingroup$ yes slightly different $\endgroup$ Jun 23 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$
    – quarague
    Jun 23 at 11:01

2 Answers 2

7
$\begingroup$

I think the highest number of edges you can visit is

21

Reasoning

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.

Example

I number the vertices included in the path, together with highlighting the missed edges in red
enter image description here

$\endgroup$
1
  • 2
    $\begingroup$ Nice work, well done. $\endgroup$ Jun 23 at 18:38
0
$\begingroup$

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.

enter image description here

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$.

enter image description here

For completeness, $n=2$ is a special case, which can be solved like so:

enter image description here

$\endgroup$
1
  • $\begingroup$ Can anyone verify my logic here? $\endgroup$ Jun 25 at 12:11

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.