IBDP MAI : Topic 3 Geometry and trigonometry - AHL 3.12Vector applications to kinematics AI HL Paper 3
Question : Computer Network Design for School Buildings [18 marks]
This question compares possible designs for a new computer network between multiple school buildings, assessing whether they meet specific requirements. A school’s administration team plans to install fibre-optic internet cables underground to connect eight buildings (A–H), with Jonas tasked to design and evaluate the network’s cost and reliability.
a Question a [2 marks] – Distance Calculation
Jonas maps the school’s buildings (A–H):
Given AD = 89.2 m, DF = 104.9 m, and ∠ADF = 83°, find AF:
AF = m
Show Solution
Using the cosine rule: AF² = 89.2² + 104.9² – 2(89.2)(104.9)cos(83°)
AF = 129 m (129.150…)
Detailed Solution:
- Apply the cosine rule: \( AF^2 = AD^2 + DF^2 – 2 \cdot AD \cdot DF \cdot \cos(\angle ADF) \).
- Insert values: \( AD = 89.2 \, \text{m}, DF = 104.9 \, \text{m}, \angle ADF = 83^\circ \).
- Compute \( AD^2 \): \( 89.2^2 = 7956.64 \).
- Compute \( DF^2 \): \( 104.9^2 = 11004.01 \).
- Determine \( \cos(83^\circ) \approx 0.1219 \) using a calculator.
- Calculate \( 2 \cdot 89.2 \cdot 104.9 \cdot 0.1219 \approx 2279.77 \).
- Substitute: \( AF^2 = 7956.64 + 11004.01 – 2279.77 = 16680.88 \).
- Find \( AF \): \( \sqrt{16680.88} \approx 129.15 \, \text{m} \).
- Round to 129 m as per standard practice.
b Question b [2 marks] – Cost per Metre
The cost to install the cable directly between A and F is $21,310. Find the cost per metre:
Cost per metre = $
Show Solution
Cost per metre = 21,310 ÷ 129.150 ≈ $165
Detailed Solution:
- Formula: \( \text{Cost per metre} = \frac{\text{Total cost}}{\text{Distance}} \).
- Total cost = $21,310.
- Distance \( AF = 129.15 \, \text{m} \) (from 2a, using precise value).
- Divide: \( \frac{21,310}{129.15} \approx 165.04 \).
- Round to nearest dollar: $165 per metre.
c Question c [1 mark] – Cost Difference Explanation
Jonas estimates $110 per metre for other cables. State why the cost for A to F is higher:
Show Solution
A lake between A and F increases costs (e.g., waterproof cables or routing around it).
Detailed Solution:
- Cost for A to F = $165/m (from 2b).
- Jonas’s estimate for other cables = $110/m.
- Observe map: A lake is between A and F.
- Higher cost due to need for waterproof cables or rerouting around the lake.
d Question d [4 marks] – Minimum Spanning Tree
Jonas creates graph S with cable installation costs as edge weights:
(i) Use Kruskal’s algorithm to find the minimum spanning tree for S, showing the order of edges:
(ii) Find the minimum installation cost:
$
Show Solution
(i) Order: CE (8239), DG (8668), BD (8778), AB (8811), DE (8833), EH (9251), DF (11,539)
(ii) Total cost = $64,119
Detailed Solution:
- Kruskal’s algorithm: Add edges in ascending weight order, skipping cycles.
- Edges: CE (8239), DG (8668), BD (8778), AB (8811), DE (8833), EH (9251), GH (9603), BE (10,153), FG (12,606), CB (13,156), AF (21,310).
- Add CE (8239): Connects C-E.
- Add DG (8668): Connects D-G.
- Add BD (8778): Connects B-D.
- Add AB (8811): Connects A-B.
- Add DE (8833): Connects D-E, links C-E-D.
- Add EH (9251): Connects E-H.
- Add DF (11,539): Connects D-F, links all 8 vertices.
- Total: \( 8239 + 8668 + 8778 + 8811 + 8833 + 9251 + 11,539 = 64,119 \).
e Question e [1 mark] – Hamiltonian vs Eulerian
State why a Hamiltonian cycle does not always form an Eulerian circuit:
Show Solution
A Hamiltonian cycle visits all vertices but not necessarily all edges, unlike an Eulerian circuit.
Detailed Solution:
- Hamiltonian cycle: Visits each vertex once, returns to start.
- Eulerian circuit: Uses each edge once, returns to start.
- Difference: Hamiltonian may skip edges; Eulerian requires all edges.
- Eulerian needs even-degree vertices, Hamiltonian doesn’t guarantee this.
f Question f [3 marks] – Nearest Neighbour Algorithm
Starting at D, use the nearest neighbour algorithm to find the upper bound for the installation cost of a Hamiltonian cycle:
Upper bound = $
Show Solution
Order: DG (8668), GH (9603), HE (9251), EC (8239), CB (13,156), BA (8811), AF (21,310), FD (11,539)
Total = $90,577
Detailed Solution:
- Nearest Neighbour: Start at D, pick cheapest edge to unvisited vertex.
- D to G: DG (8668).
- G to H: GH (9603).
- H to E: HE (9251).
- E to C: EC (8239).
- C to B: CB (13,156).
- B to A: BA (8811).
- A to F: AF (21,310).
- F to D: FD (11,539).
- Total: \( 8668 + 9603 + 9251 + 8239 + 13,156 + 8811 + 21,310 + 11,539 = 90,577 \).
g Question g [3 marks] – Deleted Vertex Algorithm
By deleting D, use the deleted vertex algorithm to find the lower bound for the installation cost of the cycle:
Lower bound = $
Show Solution
MST without D: CE (8239), AB (8811), EH (9251), GH (9603), BE (10,153), FG (12,606)
Reconnect D: DG (8668), BD (8778)
Total = $76,109
Detailed Solution:
- Delete D, find MST of A, B, C, E, F, G, H.
- Edges: CE (8239), AB (8811), EH (9251), GH (9603), BE (10,153), FG (12,606).
- MST cost: \( 8239 + 8811 + 9251 + 9603 + 10,153 + 12,606 = 58,663 \).
- Reconnect D with two cheapest edges: DG (8668), BD (8778).
- Reconnection cost: \( 8668 + 8778 = 17,446 \).
- Total: \( 58,663 + 17,446 = 76,109 \).
h Question h [2 marks] – Network Reliability
Jonas installs cables as shown:
Each cable connection has a 1.4% failure probability after a power surge. Show that the network’s failure probability is less than 2%:
Show Solution
X ~ B(2, 0.014), P(cable fails) = 1 – (0.986)² = 0.027804
Y ~ B(8, 0.027804), P(Y ≥ 2) = 0.0194 (1.94% < 2%)
Requirement satisfied.
Detailed Solution:
- Network fails if 2+ vertices are isolated.
- Each vertex has 2 cables; isolated if both fail.
- Cable failure probability = 0.014; success = 0.986.
- X ~ Bin(2, 0.014): P(both fail) = \( 0.014^2 = 0.000196 \).
- P(at least one succeeds) = \( 0.986^2 \approx 0.972196 \).
- P(isolated) = \( 1 – 0.972196 = 0.027804 \).
- Y ~ Bin(8, 0.027804): P(Y ≥ 2) = 1 – P(Y = 0) – P(Y = 1).
- P(Y = 0) = \( 0.972196^8 \approx 0.7986 \).
- P(Y = 1) = \( 8 \cdot 0.027804 \cdot 0.972196^7 \approx 0.1820 \).
- P(Y ≥ 2) = \( 1 – 0.7986 – 0.1820 = 0.0194 \) (1.94%).
- 1.94% < 2%, satisfied.