2
$\begingroup$

A robot is placed on the top-left 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 he cannot go outside the grid. The robot can revisit vertices and edges. What is the least number of moves required for it to visit every edge of the grid? Good luck!

enter image description here

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Chinese postman problem $\endgroup$
    – RobPratt
    Aug 25, 2020 at 14:08
  • $\begingroup$ Yes it is indeed! $\endgroup$
    – Dmitry Kamenetsky
    Aug 25, 2020 at 14:12

1 Answer 1

Reset to default
2
$\begingroup$

The minimum number of steps is

$28$

How to do it

At step $n$ visit the vertex as indicated by the number $n$ in the following diagram
enter image description here

Proof that this is minimal

The graph has $24$ edges in all.
Eight of the vertices have order $3$. This means that these vertices must be visited at least twice and there is an overlapping edge whenever the second incidence occurs. This means there will be at least four edges visited twice and $24 + 4 = 28$ and this minimum is achieved when we ensure the ends of the overlapping edges are on vertices of order $3$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Absolutely brilliant! Great visualisation and proof. Very fast too. Now you can try the harder version of this puzzle. $\endgroup$
    – Dmitry Kamenetsky
    Aug 25, 2020 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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