21M.1.AHL.TZ2.11

pestleMathematicsAIHLPaper 121M· ahl-3-16-tree-and-cycle-algorithms-chinese-postman-travelling-salesmansource ↗

The diagram below shows a network of roads in a small village with the weights indicating the distance of each road, in metres, and junctions indicated with letters.

Musab is required to deliver leaflets to every house on each road. He wishes to minimize his total distance.

Musab starts and finishes from the village bus-stop at $A$ . Determine the total distance Musab will need to walk.

[5]

Instead of having to catch the bus to the village, Musab’s sister offers to drop him off at any junction and pick him up at any other junction of his choice.

Explain which junctions Musab should choose as his starting and finishing points.

[2]

Markscheme / solution

Odd vertices are $A, B, D, H$ A1

Consider pairings: M1

Note: Award (M1) if there are four vertices not necessarily all correct.

$AB DH$ has shortest route $AD, DE, EB$ and $DE, EH,$
so repeated edges $(19 + 16 + 19) + (16 + 27) = 97$

Note: Condone $AB$ in place of $AD, DE, EB$ giving $56 + (16 + 27) = 99$ .

$AD BH$ has shortest route $AD$ and $BE, EH,$
so repeated edges $19 + (19 + 27) = 65$

$AH BD$ has shortest route $AD, DE, EH$ and $BE, ED$ ,
so repeated edges $(19 + 16 + 27) + (19 + 16) = 97$ A2

Note: Award A1 if only one or two pairings are correctly considered.

so best pairing is $AD, BH$
weight of route is therefore $582 + 65 = 647$ A1

[5 marks]

least value of the pairings is $19$ therefore repeat $AD$ R1

$B$ and $H$ A1

Note: Do not award R0A1.

[2 marks]

Examiners’ report

[N/A]