The route inspection problemEdexcel International A Level Maths: Subtopic test

1. 1
   A street cleaner must travel along every street in a small town, starting and finishing at the same junction. The junctions are $A$, $B$, $C$, $D$ and $E$, and the streets and their lengths in hundreds of metres are $AB=5$, $AC=8$, $BC=4$, $BD=7$, $CD=6$, $CE=9$ and $DE=3$.

   (a)

   How many junctions have an odd number of streets meeting at them?

   [1 mark]

   • A$2$
   • B$3$
   • C$4$
   • D$6$

   (b)

   Which streets must be travelled twice in the shortest route?

   [1 mark]

   • A$BC$ and $CD$
   • B$AB$
   • C$AC$ and $CE$
   • D$BD$

   (c)

   Find the length of the shortest route that the cleaner can take.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A network has four vertices $W$, $X$, $Y$ and $Z$, and every pair of vertices is joined by an arc. The lengths are $WX=6$, $WY=9$, $WZ=8$, $XY=7$, $XZ=10$ and $YZ=5$. A route must traverse every arc at least once, starting and finishing at $W$.

   (a)

   The odd vertices are $W$, $X$, $Y$ and $Z$. In how many different ways can they be paired?

   [1 mark]

   • A$2$
   • B$3$
   • C$4$
   • D$6$

   (b)

   Which pairing of the odd vertices gives the shortest repeated length?

   [1 mark]

   • A$WY$ and $XZ$
   • B$WZ$ and $XY$
   • C$WX$ and $YZ$
   • DAll three pairings give the same total

   (c)

   Find the length of the shortest route.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A gritting lorry must travel along every road in a village at least once, starting and finishing at the depot $A$. The junctions are $A$, $B$, $C$, $D$ and $E$, and the roads and their lengths in km are $AB=2$, $AC=3$, $BC=13$, $BD=8$, $CD=5$, $CE=4$, $DE=11$ and $AE=10$.

   (a)

   List the odd vertices. Find the three ways of pairing them, and the total length of the shortest connections for each pairing.

   [3 marks]

   (b)

   Hence find the length of the shortest route for the lorry, and state which roads are travelled twice. Explain why the length does not depend on which junction the lorry starts from.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A postal worker delivers to every road in a district, starting and finishing at the sorting office $A$. The junctions are $A$ to $F$, and the roads and their lengths in hundreds of metres are $AB=10$, $AC=6$, $BC=5$, $BD=12$, $CE=4$, $DE=8$, $DF=13$, $EF=3$, $AF=9$ and $BE=4$. The lengths of all the roads add up to $74$.

   (a)

   Find the shortest route for the postal worker. Show the odd vertices, the three possible pairings with their lengths, and the length of the route.

   [6 marks]

   (b)

   A new road is built joining $A$ directly to $D$, of length $x$ hundred metres. Find the range of values of $x$ for which the shortest route is shorter than before.

   [6 marks]

   Total for question 4: 12 marks

End of questions