5
$\begingroup$

A man starting from the town A, has to inspect all the roads shown from town to town. Their respective lengths, 13, 12, and 5 miles, are all shown. What is the shortest possible route he can adopt, ending his journey wherever he likes?

Grid of roads with road lengths

You can tap/click on the above map to view a bigger map.

If you wish to have your answer upvoted and accepted by me, you must clearly indicate the inspector’s route, give the total route length and prove why there is no shorter route.

Attribution:

536 PUZZLES & CURIOUS PROBLEMS by Henry Ernest Dudeney

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Normally I approve of using inclusive pronouns but I don’t like changing the wording of puzzles that I post that other people have written. $\endgroup$ Commented Apr 2, 2025 at 3:32

2 Answers 2

Reset to default
6
$\begingroup$

A town is odd if it has an odd number of roads leading out of it. The only way to walk every road leading from an odd town exactly once is to start or finish there, as each other trip through a town uses two roads (one arriving and one leaving). The above map has 6 odd towns - A, C, E, G, H, I. Hence, to make it possible to walk every road exactly once, we would need to add two more roads to make four of these towns even.

In practice, this means we will need to walk two roads twice. Hence if we can demonstrate such a route that both roads walked twice are of length 5 miles, the shortest road length, then we are done.

One such route is:

A-B-C-D-E-F-A - Walk all exterior roads, current total 78 miles.

A-G-B-H-D-I-F-G - Walk the road between A and G, then the large downward-pointing triangle. Current total 155 miles.

G-H-C-H-I-E-I-G - Walk the inner triangle, plus two trips each down CH and EI (our two repeats). Grand total 211 miles.

Improve this answer
$\endgroup$
0
9
$\begingroup$

The answer is

ABCHCDEIEFGBHDIHGIFAG and he has gone 211 miles.

Reason why this is optimum

First of all the total length of the routes without going over any route more than once is 201. Now we need to work out the minimum number of overlapping paths and in order to do so we need to make the graph Eulerian:
The graph is non Eulerian since it contains 6 vertices with an odd degree: ACEGHI. In order to make it Eulerian we need to introduce edges between the vertices which results in zero or two vertices which have an odd degree. Also we need do it only between connected vertices. It is impossible to make 6 odd to 2 or 0 with the introduction of just one edge. However with the introduction of minimum 2 edges we can achieve this: between the odd Vertex C and H and between I and E. Therefore the graph can have at minimum only 2 overlapping routes. The minimum value of the surplus of 2 lines overlapped is the shortest edge x2. The shortest edge is 5. 5x2 is 10 and 10+201 is 211. Therefore 211 is optimal.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.