| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2014 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Standard +0.3 This is a standard A-level Decision Mathematics dynamic programming question requiring systematic backward working through a network. While it has multiple parts and 12 marks, it follows a completely algorithmic procedure taught explicitly in D2. The twist of finding x where three routes have equal minimum weight adds mild problem-solving, but the tabular method is routine and requires no novel insight—just careful arithmetic and bookkeeping. |
| Spec | 7.01d Multiplicative principle: arrangements of n distinct objects |
| Stage | State | From | Calculation | Value |
| 1 | I | K | ||
| \(J\) | K | |||
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Stage working from \(K\) backwards correctly identified | M1 | Dynamic programming table method |
| \(I \to K = 12\); \(J \to K = 14\) | A1 | |
| \(G \to K\): via \(I\): \(15+12=27\); \(H \to K\): via \(J\): \(12+14=26\) or via \(H\to\)direct | A1 | |
| \(E \to K\): via \(G\): \(9+27=36\); via \(H\): \(12+26=38\); min \(= 36\) | A1 | |
| \(D \to K\): via \(G\): \((x+2)+27 = x+29\) | M1 | Using \(x\) |
| \(B \to K\): via \(D\): \(4+(x+29)=x+33\); via \(E\): \(4+36=40\) | A1 | |
| \(C \to K\): via \(E\): \(9+36=45\); via \(H\): \(6+13+26=45\) | A1 | Two routes equal |
| \(A \to K\): via \(B\): \(8+\min(x+33, 40)\); via \(C\): \(4+45=49\) | M1 | |
| For three equal minimum routes: \(8+(x+33) = 49 \Rightarrow x+41=49 \Rightarrow x=8\) | M1 A1 | |
| Minimum total weight \(= 49\) | A1 | |
| Three routes: \(A\)-\(B\)-\(D\)-\(G\)-\(I\)-\(K\); \(A\)-\(B\)-\(E\)-\(G\)-\(I\)-\(K\); \(A\)-\(C\)-\(E\)-\(G\)-\(I\)-\(K\) (or via \(H\)/\(J\) variants consistent with \(x=8\)) | A1 | All three correct |
# Question 6:
## Parts (a), (b), (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Stage working from $K$ backwards correctly identified | M1 | Dynamic programming table method |
| $I \to K = 12$; $J \to K = 14$ | A1 | |
| $G \to K$: via $I$: $15+12=27$; $H \to K$: via $J$: $12+14=26$ or via $H\to$direct | A1 | |
| $E \to K$: via $G$: $9+27=36$; via $H$: $12+26=38$; min $= 36$ | A1 | |
| $D \to K$: via $G$: $(x+2)+27 = x+29$ | M1 | Using $x$ |
| $B \to K$: via $D$: $4+(x+29)=x+33$; via $E$: $4+36=40$ | A1 | |
| $C \to K$: via $E$: $9+36=45$; via $H$: $6+13+26=45$ | A1 | Two routes equal |
| $A \to K$: via $B$: $8+\min(x+33, 40)$; via $C$: $4+45=49$ | M1 | |
| For three equal minimum routes: $8+(x+33) = 49 \Rightarrow x+41=49 \Rightarrow x=8$ | M1 A1 | |
| Minimum total weight $= 49$ | A1 | |
| Three routes: $A$-$B$-$D$-$G$-$I$-$K$; $A$-$B$-$E$-$G$-$I$-$K$; $A$-$C$-$E$-$G$-$I$-$K$ (or via $H$/$J$ variants consistent with $x=8$) | A1 | All three correct |
I can see these are answer space pages (pages 17-21) from what appears to be a Decision Mathematics exam paper (P/Jun14/MD02). These pages show only blank answer spaces for questions 6 and 7 - they do not contain any mark scheme content.
To get the mark scheme content you're looking for, you would need to provide images of the actual mark scheme document for this paper, which would be a separate document (typically published by the exam board after the examination series).
The question paper itself (page 20) shows **Question 7** with:
- Part **(a)** [2 marks]
- Part **(b)** [7 marks]
- Part **(c)** [2 marks]
But the mark scheme answers/guidance are not present in these images. Could you provide the mark scheme document images instead?6 The network below has 11 vertices and 16 edges connecting some pairs of vertices. The numbers on the edges are their weights. The weight of the edge $D G$ is given in terms of $x$.
There are three routes from $A$ to $K$ that have the same minimum total weight.\\
\includegraphics[max width=\textwidth, alt={}, center]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-16_863_1444_552_299}
Working backwards from $\boldsymbol { K }$, use dynamic programming, to find:
\begin{enumerate}[label=(\alph*)]
\item the minimum total weight from $A$ to $K$;
\item the value of $x$;
\item the three routes corresponding to the minimum total weight.
You must complete the table opposite as your solution.\\[0pt]
[12 marks]
\section*{Answer space for question 6}
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & From & Calculation & Value \\
\hline
1 & I & K & & \\
\hline
& $J$ & K & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
& & & & \\
\hline
\end{tabular}
\end{center}
\end{enumerate}
\hfill \mbox{\textit{AQA D2 2014 Q6 [12]}}