Only Connect

I noticed a lack of odd totals. Is this a coincidence?

Sarah and Iain of Madras College, Joshua of Blue Mountains Grammar School, Jack of Ecclesfield comprehensive, Annie of HKMA David Li Kwok Po College all came up with the route C--F--B--A--E--D as having the minimum total distance.of 44 km.

Kate Smith of Stocksbridge High School did the same journey in reverse order!

***

I liked the comments from Stephen and Mark Church Cowley St. James School:

The quickest way that the salesman can get round all the shops is by going: C-F-B-A-E-D, which has a total distance of 44km. Second closest was A-E-B-F-C-D, which totalled 46km. We originally thought that the salesman had to start at shop A, but realised that the text on the puzzle didn't say that.

***

Andrei of School 205 Bucharest offered some useful information on how to reduce the "trial and improvement/error" nature of most of your answers:

I solved the problem using successively the Nearest Neighbour Algorithm and the Cheapest Link Algorithm (A description of these two algorithms can be found in the following web page: mathforum )

First I made a table with the distances from one shop to another:

........A ...B ... C ... D ... E ... F
A ... X ... 9 ... X ... X ... 8 ... 14
B ... X ... X ... 14 .. X ... 8 ... 7
C ... X ... X ... X ... 15 .. X ... 8
D ... X ... X ... X ... X ... 12 .. 12
E ... X ... X ... X ... X ... X .... 10
F ... X ... X ... X ... X ... X ... X

I used the Nearest Neighbour Algorithm, taking each shop as starting point:

1. Starting point -- A

Shops Distance (km)
A --E - 8
E --B - 8
B --F - 7
F --C - 8
C --D - 15
Total 46

2. Starting point --B

Shops Distance (km)
B --F - 7
F --C - 8
C --D - 15
D --E - 12
E --A - 8
Total 50

3. Starting point --C

Shops Distance (km)
C --F - 7
F --B - 8
B --E - 15
E --A - 12
A --D-- Total Impossible

4. Starting point D

4.1.
Shops Distance (km)
D --E - 12
E --A - 8
A --B - 9
B --F - 7
F --C - 8
Total 44

4.2.
Shops Distance (km)
D --E - 12
E --B - 8
B --F - 7
F --C - 8
C --A-- Total Impossible

4.3.
Shops Distance (km)
D-- F - 12
F --B - 7
B --E - 8
E --A - 8
A --C -- Total Impossible

5. Starting point --E

5.1.
Shops Distance (km)
E --A - 8
A --B - 9
B --F - 7
F --C - 8
C --D - 15
Total 47

5.2. Shops Distance (km)
E --B - 8
B --F - 7
F --C - 8
C --D - 15
D --A-- Total Impossible

6. Starting point -- F

6.1.
Shops Distance (km)
F --B - 7
B --E - 8
E --A - 8
A --D -- Total Impossible

6.2.
Shops Distance (km)
F --B - 7
B --E - 8
E --A - 8
A --C -- Total Impossible

Using this algorithm, I obtain the following solution. The salesman must go by the route D -- E -- A -- B -- F -- C, travelling a total distance of 44 kilometres.

Now, I use an adapted version of the Cheapest Link Algorithm:

The cheapest links are:

Cheapest links
Distance (km)
B --F - 7
F --C - 8
A --E - 8
B --E - 8

The route is the following: A -- E -- B -- F -- C

The remaining shop (D) can only be connected to C, as the A -- C link doesn't exist. The distance C -- D is 15 km. The total distance on this route is 46 kilometres.

The solution is the following route D -- E --A --B --F --C, with a total distance of 44 kilometres. The solution is correct, because, is I used only the distances 7, 8, 8, 8, 9 (the smallest) the distance would have been 40 kilometres. But, with these links the salesman couldn't have reached shop D. So, instead of one 8, I used 12, obtaining 44 kilometres, exactly 4 km more than 40 km.

Note: In the problem it wasn't specified if the salesman must return to the starting place (normally it mustn't), and I considered so.