Challenge Level

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.