The route inspection problem

The route inspection problem Test

Spec 3.1 · Edexcel International A Level Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel International A Level Maths

The route inspection problem

Total 27 marks

Name

Class

Date

  1. 1
    A street cleaner must travel along every street in a small town, starting and finishing at the same junction. The junctions are AA, BB, CC, DD and EE, and the streets and their lengths in hundreds of metres are AB=5AB=5, AC=8AC=8, BC=4BC=4, BD=7BD=7, CD=6CD=6, CE=9CE=9 and DE=3DE=3.
    (a)
    How many junctions have an odd number of streets meeting at them?
    [1 mark]
    • A22
    • B33
    • C44
    • D66
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    Which streets must be travelled twice in the shortest route?
    [1 mark]
    • ABCBC and CDCD
    • BABAB
    • CACAC and CECE
    • DBDBD
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Find the length of the shortest route that the cleaner can take.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: total length of the streets 5+8+4+7+6+9+3=425+8+4+7+6+9+3=42, plus the shortest path BD=7BD=7 between the odd junctions
    A1:
    4949 hundreds of metres, which is 49004900 m
    Accept:
    4.94.9 km

    Total for question 1: 4 marks

  2. 2
    A network has four vertices WW, XX, YY and ZZ, and every pair of vertices is joined by an arc. The lengths are WX=6WX=6, WY=9WY=9, WZ=8WZ=8, XY=7XY=7, XZ=10XZ=10 and YZ=5YZ=5. A route must traverse every arc at least once, starting and finishing at WW.
    (a)
    The odd vertices are WW, XX, YY and ZZ. In how many different ways can they be paired?
    [1 mark]
    • A22
    • B33
    • C44
    • D66
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    Which pairing of the odd vertices gives the shortest repeated length?
    [1 mark]
    • AWYWY and XZXZ
    • BWZWZ and XYXY
    • CWXWX and YZYZ
    • DAll three pairings give the same total
    Show the mark scheme

    Mark scheme

    Answer: C
    (c)
    Find the length of the shortest route.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: total length 6+9+8+7+10+5=456+9+8+7+10+5=45, plus the smallest pairing total 1111
    A1:
    5656
    Accept: follow-through from their pairing in (b)

    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 AA. The junctions are AA, BB, CC, DD and EE, and the roads and their lengths in km are AB=2AB=2, AC=3AC=3, BC=13BC=13, BD=8BD=8, CD=5CD=5, CE=4CE=4, DE=11DE=11 and AE=10AE=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]
    Show the mark scheme

    Mark scheme

    B1: odd vertices AA, BB, DD, EE
    M1: all three pairings considered,
    AB+DEAB+DE, AE+BDAE+BD, AD+BEAD+BE
    A1: totals
    1111, 1515, 1717, with DE=9DE=9 via CC (not the direct 1111)
    Accept:
    AE=7AE=7 via CC, AD=8AD=8 via CC, BE=9BE=9 via AA and CC
    (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]
    Show the mark scheme

    Mark scheme

    M1: total length of the roads 5656, plus the least pairing total 1111
    A1:
    6767 km
    B1: roads
    ABAB, DCDC and CECE travelled twice
    R1: the route is a closed route which uses every road, so it has the same length wherever it starts

    Accept: follow-through from (a)

    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 AA. The junctions are AA to FF, and the roads and their lengths in hundreds of metres are AB=10AB=10, AC=6AC=6, BC=5BC=5, BD=12BD=12, CE=4CE=4, DE=8DE=8, DF=13DF=13, EF=3EF=3, AF=9AF=9 and BE=4BE=4. The lengths of all the roads add up to 7474.
    (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]
    Show the mark scheme

    Mark scheme

    B1: odd vertices AA, CC, DD, FF
    M1: all three pairings considered,
    AC+DFAC+DF, AF+CDAF+CD, AD+CFAD+CF
    A1:
    AC+DF=6+11=17AC+DF=6+11=17, with DF=11DF=11 via EE (8+38+3), not the direct 1313
    A1:
    AF+CD=9+12=21AF+CD=9+12=21 and AD+CF=18+7=25AD+CF=18+7=25
    B1: shortest repeated length
    1717 added to 7474
    A1: shortest route
    9191 hundred metres, which is 91009100 m
    Accept:
    9.19.1 km
    (b)
    A new road is built joining AA directly to DD, of length xx hundred metres. Find the range of values of xx for which the shortest route is shorter than before.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: AA and DD now have an even number of roads, so only CC and FF are odd
    A1: the only pairing is
    CFCF, with shortest connection 77 via EE
    M1: new total of the roads
    74+x74+x with 77 repeated
    A1: new route length
    81+x81+x
    M1:
    81+x<9181+x<91
    A1:
    x<10x<10
    Accept: follow-through from (a) for the value
    9191

    Total for question 4: 12 marks

End of questions

Subtopic tests