| Exam Board | AQA |
|---|---|
| Module | Further AS Paper 2 Discrete (Further AS Paper 2 Discrete) |
| Year | 2019 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Groups |
| Type | Non-group structures |
| Difficulty | Standard +0.8 This is a multi-part graph theory question requiring understanding of Eulerian paths (part a), minimum spanning trees for lower bounds (part b(i)), nearest neighbour algorithm (part b(ii)), and practical application with time calculations (part c). While the individual techniques are standard Further Maths content, the question requires careful application across multiple contexts, interpretation of a network diagram, and justification of answers. The combination of algorithmic application and problem-solving across several parts elevates this above a routine exercise, though it remains within standard Further Maths scope. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree7.04e Route inspection: Chinese postman, pairing odd nodes |
| \multirow{2}{*}{} | Bex | |||
| Strategy | \(\mathbf { B } _ { \mathbf { 1 } }\) | \(\mathbf { B } _ { \mathbf { 2 } }\) | \(\mathbf { B } _ { \mathbf { 3 } }\) | |
| \multirow{4}{*}{Ali} | \(\mathbf { A } _ { \mathbf { 1 } }\) | 2 | -1 | 3 |
| \(\mathbf { A } _ { \mathbf { 2 } }\) | -4 | -2 | 2 | |
| \(\mathbf { A } _ { \mathbf { 3 } }\) | 0 | 1 | 1 | |
| \(\mathrm { A } _ { 4 }\) | -3 | 2 | -2 | |
| Answer | Marks | Guidance |
|---|---|---|
| Identifies odd nodes as \(B, E, G, H\) | M1 | Must identify route inspection problem |
| Finds six shortest distances between odd-degree nodes: \(B\)-\(E\): 195, \(B\)-\(G\): 105, \(B\)-\(H\): 110, \(E\)-\(H\): 250, \(E\)-\(G\): 230, \(G\)-\(H\): 50 (at least four correct) | M1 | |
| All three correct minimum pairings: \((B\text{-}E)(G\text{-}H) = 195+50 = 245\), \((B\text{-}G)(E\text{-}H) = 105+250 = 355\), \((B\text{-}H)(E\text{-}G) = 110+230 = 340\) | A1 | |
| Uses shortest pairing (245) to find total distance \(= 1465 + 245 = 1710\) m \(= 1.710\) km | M1 | |
| \(1.710 \div 7 = 0.244\) hours | A1F | Follow through from their total distance |
| Answer | Marks |
|---|---|
| Two shortest arcs from entrance: \(AB = 45\), \(AG = 60\) | B1 |
| Lower bound \(= 510 + 45 + 60 = 615\) metres | B1 |
| Answer | Marks |
|---|---|
| Applies nearest neighbour algorithm from \(A\): \(A\)-\(B\)-\(C\)-\(D\)-\(E\)-\(F\)-\(I\)-\(H\)-\(G\)-\(A\) | M1 |
| Upper bound \(= 45+50+60+100+90+75+85+50+60 = 615\) metres | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Upper and lower bounds are both 615 m, so optimal distance is 615 metres | R1 | |
| \(0.615 \div 5 + 8 \times \frac{1}{60} = 0.256\) hours | M1 | |
| Times for Ashley and Brook are both approximately \(\frac{1}{4}\) of an hour | A1 | Must compare in consistent units |
| Answer | Marks | Guidance |
|---|---|---|
| Ashley and Brook work at a constant rate with no breaks; OR the speed at which Ashley and Brook move on the paths remains constant whether or not the grass has been cut | B1 | Must be a plausible assumption in context |
# Question 6:
## Part 6(a):
| Identifies odd nodes as $B, E, G, H$ | M1 | Must identify route inspection problem |
| Finds six shortest distances between odd-degree nodes: $B$-$E$: 195, $B$-$G$: 105, $B$-$H$: 110, $E$-$H$: 250, $E$-$G$: 230, $G$-$H$: 50 (at least four correct) | M1 | |
| All three correct minimum pairings: $(B\text{-}E)(G\text{-}H) = 195+50 = 245$, $(B\text{-}G)(E\text{-}H) = 105+250 = 355$, $(B\text{-}H)(E\text{-}G) = 110+230 = 340$ | A1 | |
| Uses shortest pairing (245) to find total distance $= 1465 + 245 = 1710$ m $= 1.710$ km | M1 | |
| $1.710 \div 7 = 0.244$ hours | A1F | Follow through from their total distance |
## Part 6(b)(i):
| Two shortest arcs from entrance: $AB = 45$, $AG = 60$ | B1 | |
| Lower bound $= 510 + 45 + 60 = 615$ metres | B1 | |
## Part 6(b)(ii):
| Applies nearest neighbour algorithm from $A$: $A$-$B$-$C$-$D$-$E$-$F$-$I$-$H$-$G$-$A$ | M1 | |
| Upper bound $= 45+50+60+100+90+75+85+50+60 = 615$ metres | A1 | |
## Part 6(c)(i):
| Upper and lower bounds are both 615 m, so optimal distance is 615 metres | R1 | |
| $0.615 \div 5 + 8 \times \frac{1}{60} = 0.256$ hours | M1 | |
| Times for Ashley and Brook are both approximately $\frac{1}{4}$ of an hour | A1 | Must compare in consistent units |
## Part 6(c)(ii):
| Ashley and Brook work at a constant rate with no breaks; OR the speed at which Ashley and Brook move on the paths remains constant whether or not the grass has been cut | B1 | Must be a plausible assumption in context |
---
6 The diagram shows a nature reserve which has its entrance at $A$, eight information signs at $B , C , \ldots , I$, and fifteen grass paths.
The length of each grass path is given in metres.\\
The total length of the grass paths is 1465 metres.\\
\includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-10_812_1192_584_424}
To cut the grass, Ashley starts at the entrance and drives a mower along every grass path in the nature reserve.
The mower moves at 7 kilometres per hour.
6
\begin{enumerate}[label=(\alph*)]
\item Find the least possible time that it takes for Ashley to cut the grass on all fifteen paths in the nature reserve and return to the entrance.
Fully justify your answer.\\
6
\item Brook visits every information sign in the nature reserve to update them, starting and finishing at the entrance.
For the eight information signs, the minimum connecting distance of the grass paths is 510 metres.
6 (b) (i) Determine a lower bound for the distance Brook walks to visit every information sign.\\
Fully justify your answer.\\[0pt]
[2 marks]\\
6 (b) (ii) Using the nearest neighbour algorithm starting from the entrance, determine an upper bound for the distance Brook walks to visit every information sign.\\[0pt]
[2 marks]\\
6
\item Brook takes one minute to update the information at one information sign. Brook walks on the grass paths at an average speed of 5 kilometres per hour. Ashley and Brook start from the entrance at the same time.
6 (c) (i) Use your answers from parts (a) and (b) to show that Ashley and Brook will return to the entrance at approximately the same time.
Fully justify your answer.\\
6 (c) (ii) State an assumption that you have used in part (c)(i).\\
\includegraphics[max width=\textwidth, alt={}, center]{dcf97b92-d067-41d4-89a6-ea5bab9ea4ff-13_2488_1716_219_153}\\
$7 \quad$ Ali and Bex play a zero-sum game. The game is represented by the following pay-off matrix for Ali.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\multirow{2}{*}{} & \multicolumn{4}{|c|}{Bex} \\
\hline
& Strategy & $\mathbf { B } _ { \mathbf { 1 } }$ & $\mathbf { B } _ { \mathbf { 2 } }$ & $\mathbf { B } _ { \mathbf { 3 } }$ \\
\hline
\multirow{4}{*}{Ali} & $\mathbf { A } _ { \mathbf { 1 } }$ & 2 & -1 & 3 \\
\hline
& $\mathbf { A } _ { \mathbf { 2 } }$ & -4 & -2 & 2 \\
\hline
& $\mathbf { A } _ { \mathbf { 3 } }$ & 0 & 1 & 1 \\
\hline
& $\mathrm { A } _ { 4 }$ & -3 & 2 & -2 \\
\hline
\end{tabular}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA Further AS Paper 2 Discrete 2019 Q6 [13]}}