Question
This question is about a metropolitan area council planning a new town and the location of a new toxic waste dump.
A metropolitan area in a country is modelled as a square. The area has four towns, located at the corners of the square. All units are in kilometres with the $x$-coordinate representing the distance east and the $y$-coordinate representing the distance north from the origin at $(0,0)$.
– Edison is modelled as being positioned at $\mathrm{E}(0,40)$.
– Fermitown is modelled as being positioned at $\mathrm{F}(40,40)$.
– Gaussville is modelled as being positioned at $\mathrm{G}(40,0)$.
– Hamilton is modelled as being positioned at $\mathrm{H}(0,0)$.
The metropolitan area council decides to build a new town called Isaacopolis located at I(30, 20).
A new Voronoi diagram is to be created to include Isaacopolis. The equation of the perpendicular bisector of [IE] is $y=\frac{3}{2} x+\frac{15}{2}$.
The metropolitan area is divided into districts based on the Voronoi regions found in part (c).
A toxic waste dump needs to be located within the metropolitan area. The council wants to locate it as far as possible from the nearest town.
The toxic waste dump, $\mathrm{T}$, is connected to the towns via a system of sewers.
The connections are represented in the following matrix, $\boldsymbol{M}$, where the order of rows and columns is (E, F, G, H, I, T).
$$
\boldsymbol{M}=\left(\begin{array}{llllll}
1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 1
\end{array}\right)
$$
A leak occurs from the toxic waste dump and travels through the sewers. The pollution takes one day to travel between locations that are directly connected.
The digit 1 in $\boldsymbol{M}$ represents a direct connection. The values of 1 in the leading diagonal of $\boldsymbol{M}$ mean that once a location is polluted it will stay polluted
a. The model assumes that each town is positioned at a single point. Describe possible circumstances in which this modelling assumption is reasonable.
b. Sketch a Voronoi diagram showing the regions within the metropolitan area that are closest to each town.
c.i. Find the equation of the perpendicular bisector of [IF].
c.ii.Given that the coordinates of one vertex of the new Voronoi diagram are $(20,37.5)$, find the coordinates of the other two vertices within the metropolitan area.
c.iiiSketch this new Voronoi diagram showing the regions within the metropolitan area which are closest to each town.
d. A car departs from a point due north of Hamilton. It travels due east at constant speed to a destination point due North of Gaussville. It passes through the Edison, Isaacopolis and Fermitown districts. The car spends $30 \%$ of the travel time in the Isaacopolis district.
Find the distance between Gaussville and the car’s destination point.
e.i. Find the location of the toxic waste dump, given that this location is not on the edge of the metropolitan area.
e.ii.Make one possible criticism of the council’s choice of location.
f.i. Find which town is last to be polluted. Justify your answer.
f.ii. Write down the number of days it takes for the pollution to reach the last town.
f.iii.A sewer inspector needs to plan the shortest possible route through each of the connections between different locations. Determine an appropriate start point and an appropriate end point of the inspection route.
Note that the fact that each location is connected to itself does not correspond to a sewer that needs to be inspected.
▶️Answer/Explanation
a. the size of each town is small (in comparison with the distance between the towns)
OR
if towns have an identifiable centre
OR
the centre of the town is at that point $\quad \boldsymbol{R 1}$
Note: Accept a geographical landmark in place of “centre”, e.g. “town hall” or “capitol”.
b.
c.i. the gradient of IF is $\frac{40-20}{40-30}=2$
(A1)
negative reciprocal of any gradient
(M1)
gradient of perpendicular bisector $=\frac{1}{2}$
Note: Seeing $-\frac{2}{3}$ (for example) used clearly as a gradient anywhere is evidence of the “negative reciprocal” method despite being applied to an inappropriate gradient.
midpoint is $\left(\frac{40+30}{2}, \frac{40+20}{2}\right)=(35,30)$
(A1)
equation of perpendicular bisector is $y-30=-\frac{1}{2}(x-35)$
A1
Note: Accept equivalent forms e.g. $y=-\frac{1}{2} x+\frac{95}{2}$ or $2 y+x-95=0$.
Allow FT for the final $\boldsymbol{A 1}$ from their midpoint and gradient of perpendicular bisector, as long as the $\boldsymbol{M 1}$ has been awarded
[4 marks]
c.ii.the perpendicular bisector of $\mathrm{EH}$ is $y=20$
(A1)
Note: Award this A1 if seen in the $y$-coordinate of any final answer or if 20 is used as the $y$-value in the equation of any other perpendicular bisector.
attempt to use symmetry OR intersecting two perpendicular bisectors
(M1)
$\left(\frac{25}{3}, 20\right) \quad \boldsymbol{A 1}$
(20, 2.5) $\quad \boldsymbol{A 1}$
[4 marks ]
c.iii.
d. $30 \%$ of 40 is 12
(A1)
recognizing line intersects bisectors at $y=c$ (or equivalent) but different $x$-values
(M1)
$c=\frac{3}{2} x_1+\frac{15}{2}$ and $c=-\frac{1}{2} x_2+\frac{95}{2}$
finding an expression for the distance in Isaacopolis in terms of one variable
(M1)
$$
x_2-x_1=(95-2 c)-\frac{2 c-15}{3}=100-\frac{8 c}{3}
$$
equating their expression to 12
$$
\begin{aligned}
& 100-\frac{8 c}{3}=0.3 \times 40=12 \\
& c=33
\end{aligned}
$$
distance $=33(\mathrm{~km}) \quad$ A1
e.i. must be a vertex (award if vertex given as a final answer)
(R1)
attempt to calculate the distance of at least one town from a vertex
(M1)
Note: This must be seen as a calculation or a value.
correct calculation of distances
A1
$\frac{65}{3}$ OR 21.7 AND $\sqrt{406.25}$ OR 20.2
$\left(\frac{25}{3}, 20\right) \quad$ A1
Note: Award R1MOAOAO for a vertex written with no other supporting calculations.
Award R1MOAOA1 for correct vertex with no other supporting calculations.
The final $\boldsymbol{A 1}$ is not dependent on the previous $\boldsymbol{A 1}$. There is no follow-through for the final $\boldsymbol{A 1}$.
Do not accept an answer based on “uniqueness” in the question.
[4 marks]
e.ii.For example, any one of the following:
decision does not take into account the different population densities
closer to a city will reduce travel time/help employees
it is closer to some cites than others
R1
Note: Accept any correct reason that engages with the scenario.
Do not accept any answer to do with ethical issues about whether toxic waste should ever be dumped, or dumped in a metropolitan area.
f.i. METHOD 1
attempting $\boldsymbol{M}^3 \quad \boldsymbol{M 1}$
attempting $\boldsymbol{M}^4 \quad \boldsymbol{M 1}$
e.g.
last row/column of $M^3=\left(\begin{array}{llllll}3 & 5 & 1 & 6 & 0 & 7\end{array}\right)$
last row/column of $\boldsymbol{M}^4=\left(\begin{array}{llllll}10 & 12 & 4 & 16 & 1 & 18\end{array}\right)$
hence Isaacopolis is the last city to be polluted
A1
Note: Do not award the $\boldsymbol{A} 1$ unless both $\boldsymbol{M}^3$ and $\boldsymbol{M}^4$ are considered.
Award M1MOAO for a claim that the shortest distance is from $T$ to $I$ and that it is 4, without any support.
METHOD 2
attempting to translate $\boldsymbol{M}$ to a graph or a list of cities polluted on each day
(M1)
correct graph or list
hence Isaacopolis is the last city to be polluted
A1
Note: Award M1A1A1 for a clear description of the graph in words leading to the correct answer.
[3 marks]
f.ii. it takes 4 days
A1
[1 mark]
f.iii.EITHER
the orders of the different vertices are:
E 2
F 1
G 2
H 2
I 1
T 2
(A1)
Note: Accept a list where each order is 2 greater than listed above.
OR
a correct diagram/graph showing the connections between the locations
(A1)
Note: Accept a diagram with loops at each vertex.
This mark should be awarded if candidate is clearly using their correct diagram from the previous part.
THEN
“Start at $F$ and end at I” OR “Start at I and end at F”
A1
Note: Award A1AO for “it could start at either F or I”.
Award A1A1 for “IGEHTF” OR “FTHEGI”.
Award $\mathbf{A 1 A 1}$ for ” $F$ and $I$ ” OR “I and $F$ “.
Question
This question compares possible designs for a new computer network between multiple school buildings, and whether they meet specific requirements.
A school’s administration team decides to install new fibre-optic internet cables underground. The school has eight buildings that need to be connected by these cables. A map of the school is shown below, with the internet access point of each building labelled A-H.
Jonas is planning where to install the underground cables. He begins by determining the distances, in metres, between the underground access points in each of the buildings.
He finds $\mathrm{AD}=89.2 \mathrm{~m}, \mathrm{DF}=104.9 \mathrm{~m}$ and $\mathrm{ADF}=83^{\circ}$.
The cost for installing the cable directly between A and F is $\$ 21310$.
Jonas estimates that it will cost $\$ 110$ per metre to install the cables between all the other buildings.
Jonas creates the following graph, $S$, using the cost of installing the cables between two buildings as the weight of each edge.
The computer network could be designed such that each building is directly connected to at least one other building and hence all buildings are indirectly connected.
The computer network fails if any part of it becomes unreachable from any other part. To help protect the network from failing, every building could be connected to at least two other buildings. In this way if one connection breaks, the building is still part of the computer network. Jonas can achieve this by finding a Hamiltonian cycle within the graph.
After more research, Jonas decides to install the cables as shown in the diagram below.
Each individual cable is installed such that each end of the cable is connected to a building’s access point. The connection between each end of a cable and an access point has a $1.4 \%$ probability of failing after a power surge.
For the network to be successful, each building in the network must be able to communicate with every other building in the network. In other words there must be a path that connects any two buildings in the network. Jonas would like the network to have less than a $2 \%$ probability of failing to operate after a power surge.
a. Find $\mathrm{AF}$.
b. Find the cost per metre of installing this cable.
c. State why the cost for installing the cable between A and F would be higher than between the other buildings.
d.i.By using Kruskal’s algorithm, find the minimum spanning tree for $S$, showing clearly the order in which edges are added.
d.iiHence find the minimum installation cost for the cables that would allow all the buildings to be part of the computer network.
e. State why a path that forms a Hamiltonian cycle does not always form an Eulerian circuit.
f. Starting at $\mathrm{D}$, use the nearest neighbour algorithm to find the upper bound for the installation cost of a computer network in the form of a Hamiltonian cycle.
Note: Although the graph is not complete, in this instance it is not necessary to form a table of least distances.
g. By deleting D, use the deleted vertex algorithm to find the lower bound for the installation cost of the cycle.
h. Show that Jonas’s network satisfies the requirement of there being less than a $2 \%$ probability of the network failing after a power surge.
▶️Answer/Explanation
a. $\mathrm{AF}^2=89.2^2+104.9^2-2(89.2)(104.9) \cos 83$
(M1)(A1)
Note: Award (M1) for substitution into the cosine rule and (A1) for correct substitution.
$$
\mathrm{AF}=129 \mathrm{~m}(129.150 \ldots)
$$
A1
[3 marks]
b. $21310 \div 129.150 \ldots$
(M1)
$\$ 165$
A1
[2 marks]
c. any reasonable statement referring to the lake
R1
(eg. there is a lake between A and F, the cables would need to be installed under/over/around the lake, special waterproof cables are needed for lake, etc.)
[1 mark]
d.i.edges (or weights) are chosen in the order
CE (8239)
DG (8668)
BD (8778)
AB (8811)
DE (8833)
EH (9251)
DF (11 539)
d.iiFinding the sum of the weights of their edges
(M1)
$$
\begin{aligned}
& 8239+8668+8778+8811+8833+9251+11539 \\
& \text { total cost }=\$ 64119 \quad \text { A1 }
\end{aligned}
$$
A1
[2 marks]
e. a Hamiltonian cycle is not always an Eulerian circuit as it does not have to include all edges of the graph (only all vertices)
R1
[1 mark]
f. edges (or weights) are chosen in the order
DG (8668)
GH (9603)
HE (9251)
EC (8239)
CB (13 156)
BA (8811)
AF (21 310)
FD (11 539)
finding the sum of the weights of their edges
(M1)
$8668+9603+9251+8239+13156+8811+21310+11539$
upper bound $=\$ 90577$
A1
[5 marks]
g. attempt to find MST after deleting vertex D
(M1)
these edges (or weights) (in any order)
CE (8239)
$\mathrm{AB}$ (8811)
EH (9251)
GH (9603)
BE (10 153)
FG (12 606)
A1
Note: Prim’s or Kruskal’s algorithm could be used at this stage.
reconnect D to MST with two different edges
(M1)
DG (8668)
BD (8778)
A1
Note: This $\boldsymbol{A 1}$ is independent of the first $\boldsymbol{A}$ mark and can be awarded if both DG and BD are chosen to reconnect D to the MST, even if the MST is incorrect.
finding the sum of the weights of their edges
(M1)
$$
8239+8811+9251+9603+10153+12606+8668+8778
$$
Note: For candidates with an incorrect MST or no MST, the weights of at least seven of the edges being summed (two of which must connect to D) must be shown to award this (M1).
lower bound $=\$ 76109$
A1
[6 marks]
h. METHOD 1
recognition of a binomial distribution
(M1)
$X \sim \mathrm{B}(2,0.014)$
finding the probability that a cable fails (at least one of its connections fails)
$\mathrm{P}(X>0)=0.027804$ OR $1-\mathrm{P}(X=0)=0.027804$
A1
recognition that two cables must fail for the network to go offline M1
recognition of binomial distribution for network, $Y \sim \mathrm{B}(8,0.027804)$
(M1)
A1
therefore, the diagram satisfies the requirement since $1.94 \%<2 \%$
AG
Note: Evidence of binomial distribution may be seen as combinations.
METHOD 2
recognition of a binomial distribution
(M1)
$X \sim \mathrm{B}(16,0.014)$
finding the probability that at least two connections fail
$\mathrm{P}(X \geq 2)=0.0206473 \ldots$ OR $\mathbf{1}-\mathbf{P}(\boldsymbol{X}<\mathbf{2})=\mathbf{0 . 0 2 0 6 4 7 3} \ldots$
A1
recognition that the previous answer is an overestimate
M1
finding probability of two ends of the same cable failing, $F \sim \mathrm{B}(2,0.014)$,
and the ends of the other 14 cables not failing, $S \sim \mathrm{B}(14,0.014)$
$\mathrm{P}(F=2) \times \mathrm{P}(S=0)=0.0000160891 \ldots$
(A1)
$0.0000160891 \ldots \times 8=0.00128713 \ldots$
$0.0206473 \ldots-0.00128713 \ldots=0.0194(0.0193602 \ldots)$
$0.0000160891 \ldots \times 8=0.00128713 \ldots$
$0.0206473 \ldots-0.00128713 \ldots=0.0194(0.0193602 \ldots)$
A1
therefore, the diagram satisfies the requirement since $1.94 \%<2 \%$
AG
METHOD 3
recognition of a binomial distribution $\quad M 1$ $X \sim \mathrm{B}(16,0.014)$
finding the probability that the network remains secure if 0 or 1 connections fail or if 2 connections fail provided that the second failed connection occurs at the other end of the cable with the first failure
(M1)
$\mathrm{P}($ remains secure $)=\mathrm{P}(X \leq 1)+\frac{1}{15} \times \mathrm{P}(X=2)$
A1
$$
=0.9806397625
$$
A1
$\mathrm{P}($ network fails $)=1-0.9806397625=0.0194(0.0193602 \ldots)$
A1
therefore, the diagram satisfies the requirement since $1.94 \%<2 \%$
AG
METHOD 4
P(network failing)
$=1-\mathrm{P}(0$ connections failing $)-\mathrm{P}(1$ connection failing $)-\mathrm{P}(2$ connections on the same cable failing $) \quad$ M1
$=1-0.986^{16}-C 1_{16} \times 0.014 \times 0.986^{15}-C 1_8 \times 0.014^2 \times 0.986^{14}$
A1A1A1
Note: Award $\mathbf{A 1}$ for each of $2^{\text {nd }}, 3^{\text {rd }}$ and last terms.
$=0.0194(0.0193602 \ldots)$
A1
therefore, the diagram satisfies the requirement since $1.94 \%<2 \%$
AG
[5 marks]
Question
A driver needs to make deliveries to five shops $A, B, C, D$ and $E$. The driver starts and finishes his journey at the warehouse $W$. The driver wants to find the shortest route to visit all the shops and return to the warehouse. The distances, in kilometres, between the locations are given in the following table.
▶️Answer/Explanation
a. By deleting $W$, use the deleted vertex algorithm to find a lower bound for the length of a route that visits every shop, starting and finishing at $W$
b. Starting from $W$, use the nearest-neighbour algorithm to find a route which gives an upper bound for this problem and calculate its length. a. deleting and its adjacent edges, the minimal spanning tree is
Note: Award the A1’s for either the edges or their weights.
the minimum spanning tree has weight $=54$
Note: Accept a correct drawing of the minimal spanning tree.
adding in the weights of 2 deleted edges of least weight $\mathrm{WB}$ and $\mathrm{WC}$
(M1)
lower bound $=54+36+39$
$$
=129
$$
A1
[6 marks]
b. attempt at the nearest-neighbour algorithm $\boldsymbol{M 1}$
WB
BA
$\mathrm{AD}$
$\mathrm{DE}$
EC
CW
A1
Note: Award $\boldsymbol{M 1}$ for a route that begins with $\mathrm{WB}$ and then BA.
upper bound $=36+11+15+12+22+39=135$
(M1)A1
[4 marks]
Question
The weights of the edges in the complete graph G are given in the following table.
▶️Answer/Explanation
a. Starting at A, use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for $G$.
b. By first deleting vertex A, use the deleted vertex algorithm together with Kruskal’s algorithm to find a lower bound for the travelling salesman problem for $G$.a.the edges are traversed in the following order
AB $\quad$ A1
$B C$
CF $\quad \mathbf{A 1}$
FE
ED $\quad \boldsymbol{A 1}$
DA $\boldsymbol{A 1}$
upper bound $=$ weight of this cycle $=4+1+2+7+11+8=33 \quad$ A1
[5 marks]
b. having deleted $\mathrm{A}$, the order in which the edges are added is
BC $\mathbf{A 1}$
CF $\quad \mathbf{A 1}$
CD $\mathbf{A 1}$
EF $\boldsymbol{A 1}$
Note: Accept indication of the correct order on a diagram.
to find the lower bound, we now reconnect A using the two edges with the lowest weights, that is AB and AF
(M1)(A1)
lower bound $=1+2+5+7+4+6=25$
A1
Note: Award (M1)(A1)A1 for LB $=15+4+6=25$ obtained either from an incorrect order of correct edges or where order is not indicated.
[7 marks]
Question
Mathilde delivers books to five libraries, A, B, C, D and E. She starts her deliveries at library D and travels to each of the other libraries once, before returning to library D. Mathilde wishes to keep her travelling distance to a minimum.
The weighted graph $H$, representing the distances, measured in kilometres, between the five libraries, has the following table.
a. Draw the weighted graph $H$.
b. Starting at library D use the nearest-neighbour algorithm, to find an upper bound for Mathilde’s minimum travelling distance. Indicate clearly the order in which the edges are selected.
c. By first removing library $\mathrm{C}$, use the deleted vertex algorithm, to find a lower bound for Mathilde’s minimum travelling distance.
▶️Answer/Explanation
a.
complete graph on 5 vertices
A1
weights correctly marked on graph
A1
[2 marks]
b. clear indication that the nearest-neighbour algorithm has been applied M1
DA (or 16) A1
$\mathrm{AB}$ (or 18) then $\mathrm{BC}$ (or 15) $\quad \mathbf{A 1}$
CE (or 17) then ED (or 19) A1
$$
\mathrm{UB}=85 \quad \text { A1 }
$$
[5 marks]
c. an attempt to find the minimum spanning tree
(M1)
DA (16) then $B E(17)$ then $A B(18)$ (total 51) $\quad \boldsymbol{A 1}$
reconnect $\mathrm{C}$ with the two edges of least weight, namely CB (15) and CE (17) M1
$$
\mathrm{LB}=83 \quad \text { A1 }
$$
[4 marks]
Question
Consider the graph G represented in the following diagram.
The graph $G$ is a plan of a holiday resort where each vertex represents a villa and the edges represent the roads between villas. The weights of the edges are the times, in minutes, Mr José, the security guard, takes to walk along each of the roads. Mr José is based at villa A.
a. State, with a reason, whether or not $G$ has an Eulerian circuit.
b. Use Kruskal’s algorithm to find a minimum spanning tree for G, stating its total weight. Indicate clearly the order in which the edges are added.
c. Use a suitable algorithm to show that the minimum time in which Mr José can get from $\mathrm{A}$ to $\mathrm{E}$ is 13 minutes.
d. Find the minimum time it takes Mr José to patrol the resort if he has to walk along every road at least once, starting and ending at A. State clearly which roads need to be repeated.
▶️Answer/Explanation
a.
no because the graph has vertices (A, B, D, F) of odd degree
R1
[1 mark]
b. the edges are added in the order
BI 5
DH 5
A1
AB 6
AF 6
$\mathrm{Cl} 6$
A1
CD 7
EF 7 A1
total weight $=42$
A1
Note: The orders of the edges with the same weight are interchangeable.
Accept indication of correct edge order on a diagram.
[4 marks]
c. clear indication of using Dijkstra for example
M1
d. there are 4 vertices of odd degree (A, F, B and D)
(A1)
attempting to list at least 2 possible pairings of odd vertices
M1
$A \rightarrow F$ and $B \rightarrow D$ has minimum weight $6+17=23$
$A \rightarrow B$ and $F \rightarrow D$ has minimum weight $6+18=24$
$A \rightarrow D$ and $F \rightarrow B$ has minimum weight $20+12=32$
A1A1
Note: Award A1AO for 2 pairs.
minimum time is $(116+23=) 139$ (mins)
(M1)A1
roads repeated are $\mathrm{AF}, \mathrm{BC}$ and $\mathrm{CD}$
A1
[7 marks]