Edexcel International A Level Maths
The route inspection problem
Total 27 marks
Name
Class
Date
- 1A street cleaner must travel along every street in a small town, starting and finishing at the same junction. The junctions are , , , and , and the streets and their lengths in hundreds of metres are , , , , , and .(a)How many junctions have an odd number of streets meeting at them?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(b)Which streets must be travelled twice in the shortest route?[1 mark]- A and
- B
- C and
- D
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 , plus the shortest path between the odd junctions
A1: hundreds of metres, which is m
Accept: kmTotal for question 1: 4 marks
- 2A network has four vertices , , and , and every pair of vertices is joined by an arc. The lengths are , , , , and . A route must traverse every arc at least once, starting and finishing at .(a)The odd vertices are , , and . In how many different ways can they be paired?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: B(b)Which pairing of the odd vertices gives the shortest repeated length?[1 mark]- A and
- B and
- C and
- 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 , plus the smallest pairing total
A1:
Accept: follow-through from their pairing in (b)Total for question 2: 4 marks
- 3A gritting lorry must travel along every road in a village at least once, starting and finishing at the depot . The junctions are , , , and , and the roads and their lengths in km are , , , , , , and .(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 , , ,
M1: all three pairings considered, , ,
A1: totals , , , with via (not the direct )
Accept: via , via , via and(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 , plus the least pairing total
A1: km
B1: roads , and 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
- 4A postal worker delivers to every road in a district, starting and finishing at the sorting office . The junctions are to , and the roads and their lengths in hundreds of metres are , , , , , , , , and . The lengths of all the roads add up to .(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 , , ,
M1: all three pairings considered, , ,
A1: , with via (), not the direct
A1: and
B1: shortest repeated length added to
A1: shortest route hundred metres, which is m
Accept: km(b)A new road is built joining directly to , of length hundred metres. Find the range of values of for which the shortest route is shorter than before.[6 marks]Show the mark scheme
Mark scheme
M1: and now have an even number of roads, so only and are odd
A1: the only pairing is , with shortest connection via
M1: new total of the roads with repeated
A1: new route length
M1:
A1:
Accept: follow-through from (a) for the valueTotal for question 4: 12 marks
End of questions