| Exam Board | AQA |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Dynamic programming shortest/longest path |
| Difficulty | Moderate -0.3 This is a standard textbook dynamic programming question requiring systematic backward working through a network to find the longest path. While it requires careful bookkeeping and multiple stages, the algorithm is mechanical and follows a prescribed method with no novel problem-solving or insight needed. The table structure guides students through the process, making it slightly easier than average. |
| Spec | 7.05a Critical path analysis: activity on arc networks7.05b Forward and backward pass: earliest/latest times, critical activities |
| Stage | State | From | Value |
| 1 | G | I | |
| H | I | ||
| 2 | |||
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Let Arsene play A with probability \(p\) | ||
| Against C: \(p(x+3) + (1-p)(x+1) = 2p + x + 1\) | M1 | Setting up expected value expressions for each of Jose's strategies |
| Against D: \(p(1) + (1-p)(3) = 3 - 2p\) | ||
| Setting equal: \(2p + x + 1 = 3 - 2p\) | M1 | Setting the two expressions equal (or using value = 2.5) |
| \(4p = 2 - x\) | ||
| Using value = 2.5: \(3 - 2p = 2.5\) | ||
| \(p = \frac{1}{4}\) | A1 | |
| Arsene plays A with probability \(\frac{1}{4}\), B with probability \(\frac{3}{4}\) | A1 | Must state both probabilities clearly |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Substituting \(p = \frac{1}{4}\) into \(2p + x + 1 = 2.5\) | M1 | Substituting their value of \(p\) into either expression with the value 2.5 |
| \(\frac{1}{2} + x + 1 = 2.5\) | ||
| \(x = 1\) | A1 |
# Question 7:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Let Arsene play A with probability $p$ | | |
| Against C: $p(x+3) + (1-p)(x+1) = 2p + x + 1$ | M1 | Setting up expected value expressions for each of Jose's strategies |
| Against D: $p(1) + (1-p)(3) = 3 - 2p$ | | |
| Setting equal: $2p + x + 1 = 3 - 2p$ | M1 | Setting the two expressions equal (or using value = 2.5) |
| $4p = 2 - x$ | | |
| Using value = 2.5: $3 - 2p = 2.5$ | | |
| $p = \frac{1}{4}$ | A1 | |
| Arsene plays A with probability $\frac{1}{4}$, B with probability $\frac{3}{4}$ | A1 | Must state both probabilities clearly |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Substituting $p = \frac{1}{4}$ into $2p + x + 1 = 2.5$ | M1 | Substituting their value of $p$ into either expression with the value 2.5 |
| $\frac{1}{2} + x + 1 = 2.5$ | | |
| $x = 1$ | A1 | |7 The network below shows a system of one-way roads. The number on each edge represents the number of bags for recycling that can be collected by driving along that road.
A collector is to drive from $A$ to $I$.\\
\includegraphics[max width=\textwidth, alt={}, center]{c18db720-6fe8-4e6c-bd0c-dc51cc341b47-144_867_1644_552_191}
\begin{enumerate}[label=(\alph*)]
\item Working backwards from $\boldsymbol { I }$, use dynamic programming to find the maximum number of bags that can be collected when driving from $A$ to $I$.
You must complete the table opposite as your solution.
\item State the route that the collector should take in order to collect the maximum number of bags.
(a)
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
Stage & State & From & Value \\
\hline
1 & G & I & \\
\hline
& H & I & \\
\hline
& & & \\
\hline
2 & & & \\
\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 Q7}}