User interface language: English | Español

Date May 2022 Marks available 3 Reference code 22M.3.AHL.TZ2.2
Level Additional Higher Level Paper Paper 3 Time zone Time zone 2
Command term Find Question number 2 Adapted from N/A

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 AD=89.2mDF=104.9m and AD^F=83°.

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.

Find AF.

[3]
a.

Find the cost per metre of installing this cable.

[2]
b.

State why the cost for installing the cable between A and F would be higher than between the other buildings.

[1]
c.

By using Kruskal’s algorithm, find the minimum spanning tree for S, showing clearly the order in which edges are added.

[3]
d.i.

Hence find the minimum installation cost for the cables that would allow all the buildings to be part of the computer network.

[2]
d.ii.

State why a path that forms a Hamiltonian cycle does not always form an Eulerian circuit.

[1]
e.

Starting at 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.

[5]
f.

By deleting D, use the deleted vertex algorithm to find the lower bound for the installation cost of the cycle.

[6]
g.

Show that Jonas’s network satisfies the requirement of there being less than a 2% probability of the network failing after a power surge.

[5]
h.

Markscheme

AF2=89.22+104.92-289.2104.9cos83         (M1)(A1)


Note: Award (M1) for substitution into the cosine rule and (A1) for correct substitution.


AF=129 m   129.150           A1

 

[3 marks]

a.

21310÷129.150         (M1)

$165           A1

 

[2 marks]

b.

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]

c.

edges (or weights) are chosen in the order

CE    8239
DG    8668
BD    8778
AB    8811
DE    8833
EH    9251
DF    11539               A1A1A1

Note: Award A1 for the first two edges chosen in the correct order. Award A1A1 for the first six edges chosen in the correct order. Award A1A1A1 for all seven edges chosen in the correct order. Accept a diagram as an answer, provided the order of edges is communicated.

 

[3 marks]

d.i.

Finding the sum of the weights of their edges               (M1)
8239+8668+8778+8811+8833+9251+11539

total cost =$64119               A1

 

[2 marks]

d.ii.

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]

e.

edges (or weights) are chosen in the order

DG   8668
GH   9603
HE   9251
EC   8239
CB   13156
BA   8811
AF   21310
FD   11539              A1A1A1


Note:
Award A1 for the first two edges chosen in the correct order. Award A1A1 for the first five edges chosen in the correct order. Award A1A1A1 for all eight edges chosen in the correct order. Accept a diagram as an answer, provided the order of edges is communicated.

 

finding the sum of the weights of their edges                (M1)
8668+9603+9251+8239+13156+8811+21310+11539

upper bound =$90577              A1

 

[5 marks]

f.

attempt to find MST after deleting vertex D         (M1)
these edges (or weights) (in any order)

CE   8239
AB   8811
EH   9251
GH   9603
BE   10153
FG   12606              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 A1 is independent of the first 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]

g.

METHOD 1

recognition of a binomial distribution         (M1)
X~B2, 0.014

finding the probability that a cable fails (at least one of its connections fails)
PX>0=0.027804  OR  1-PX=0=0.027804             A1

recognition that two cables must fail for the network to go offline         M1

recognition of binomial distribution for network, Y~B8, 0.027804         (M1)

PY2=0.0194  0.0193602  OR  1-PY<2=0.0194  0.0193602             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~B16, 0.014

finding the probability that at least two connections fail
PX2=0.0206473  OR  1-PX<2=0.0206473             A1

recognition that the previous answer is an overestimate          M1

finding probability of two ends of the same cable failing, F~B2, 0.014,
and the ends of the other 14 cables not failing, S~B14, 0.014
PF=2×PS=0=0.0000160891             (A1)

 

0.0000160891×8=0.00128713...

0.0206473-0.00128713=0.0194  0.0193602             A1

therefore, the diagram satisfies the requirement since 1.94%<2%             AG

 

METHOD 3

recognition of a binomial distribution          M1
X~B16, 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)

P(remains secure) =PX1+115×PX=2             A1

=0.9806397625             A1

P(network fails) =1-0.9806397625=0.0194  0.0193602              A1

therefore, the diagram satisfies the requirement since 1.94%<2%             AG

 

METHOD 4

P(network failing)

=1-P0 connections failing-P1 connection failing-P2 connections on the same cable failing          M1

=1-0.98616-C116×0.014×0.98615-C18×0.0142×0.98614              A1A1A1


Note: Award A1 for each of 2nd, 3rd and last terms.


=0.0194  0.0193602              A1

therefore, the diagram satisfies the requirement since 1.94%<2%             AG

 

[5 marks]

h.

Examiners report

This question part was intended to be an easy introduction to help candidates begin working with the larger story and most candidates handled it well. However, it was surprisingly common for a candidate to correctly choose the cosine rule and to make the correct substitutions into the formula but then arrive at an incorrect answer. The frequency of this mistake suggests that candidates were either making simple entry mistakes into their GDC or forgetting to ensure that their GDC was set to degrees rather than radians.

a.

(b) and (c) Most candidates were able to gain the three marks available.

b.
[N/A]
c.

(d), (f) and (g) These three question parts required candidates to demonstrate their ability to carry out graph theory algorithms. Kruskal’s algorithm was split into two different question parts to guide candidates to show their work. As a result, many were able to score well in part (d)(ii) either from having the correct MST or from “follow through” marks from an incorrect MST. However, without this guidance in 2(f) and 2(g), many candidates did a poor job of showing the process they were using to apply the algorithms. The candidates that scored well were detailed in showing the order of how edges were selected and how they were being summed to arrive at the final answers. Although “follow through” within the problem was not available for the final answer in parts 2(f) and 2(g), many candidates missed the opportunity to gain the final method mark in both parts by not fully showing the process they used.

d.i.
[N/A]
d.ii.

Many candidates were able to state the definitions of Hamiltonian cycles and Eulerian circuits. However, the question was not asking for definitions but rather a distinct conclusion of why a Hamiltonian cycle is not always an Eulerian circuit. Disappointingly, many incorrect answers contained five or more lines or writing that may have used up exam time that could have been devoted to other question parts. Another common mistake seen here was candidates incorrectly trying to state a reason based on the number of odd vertices.

e.
[N/A]
f.
[N/A]
g.

This question was very challenging for almost all the candidates. Although there were several different methods that candidates could have used to answer this question, most candidates were only able to gain one or two marks here. Many candidates did recognize that something binomial was needed, but few knew how to setup the correct parameters for the distribution.

h.

Syllabus sections

Topic 3—Geometry and trigonometry » SL 3.2—2d and 3d trig
Show 99 related questions
Topic 3—Geometry and trigonometry

View options