Only connect
The graph represents a salesman’s area of activity with the
shops that the salesman must visit each day. What route around the
shops has the minimum total distance?
Age
11 to 14
Challenge level
Problem
The graph below represents a salesman's area of activity with shops at A, B, C, D, E and F. (It isn't drawn to scale.)
Image
The numbers represent the distance in kilometres between the places that salesman must visit each day.
What route around the shops has the minimum total distance?
Getting Started
You need to be systemmatic.
How about finding a way to record you findings as you go along?
Student Solutions
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.