| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2016 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Count vertex occurrences in route |
| Difficulty | Moderate -0.3 This is a standard Chinese Postman Problem application with straightforward identification of odd vertices and pairing. Part (a) requires basic CPP algorithm, part (b) tests understanding that optimal semi-Eulerian paths connect two odd vertices, and part (c) is a minor variation. The question is methodical but requires only textbook procedures with no novel insight or complex reasoning—slightly easier than average A-level due to its algorithmic nature. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| \(BD + FH \quad (10 + 12) = 22\) | M1 | These 3 sets of lettered pairs added |
| \(BF + DH \quad (18 + 14) = 32\) | A2,1,0 | 3 correct, 2 correct |
| \(BH + DF \quad (16 + 18) = 34\) | ||
| Min \(167 + 22\) | m1 | PI 167 + their min of 3 totals |
| \(= 189\) (min) | A1 CSO | Must have scored the first 4 marks. If M0 scored, then 189 scores SC2 |
| (ii) 3 | B1 | 6 marks total |
| (b)(i) Repeat BD | M1 | PI; Eg \(167 + BD\) or \(189 - FH\) or \(167 + 10\) or \(189 - 12\) |
| 177 (min) | A1 | |
| (ii) F, H | B1 | 3 marks total |
| (c)(i) 179 (min) | B1 | |
| (ii) B | B1 | 2 marks total |
**(a)(i)** (Odd vertices: B, D, F, H)
$BD + FH \quad (10 + 12) = 22$ | M1 | These 3 sets of lettered pairs added
$BF + DH \quad (18 + 14) = 32$ | A2,1,0 | 3 correct, 2 correct
$BH + DF \quad (16 + 18) = 34$ |
Min $167 + 22$ | m1 | PI 167 + their min of 3 totals
$= 189$ (min) | A1 CSO | Must have scored the first 4 marks. If M0 scored, then 189 scores SC2
**(ii)** 3 | B1 | 6 marks total
**(b)(i)** Repeat BD | M1 | PI; Eg $167 + BD$ or $189 - FH$ or $167 + 10$ or $189 - 12$
177 (min) | A1 |
**(ii)** F, H | B1 | 3 marks total | Both correct with no extras and must be 2 vertices not an edge. Do not accept 'Start F and Finish H'
**(c)(i)** 179 (min) | B1 |
**(ii)** B | B1 | 2 marks total
**Total: 11 marks**
---4 Amal delivers free advertiser magazines to all the houses in his village. The network shows the roads in his village. The number on each road shows the time, in minutes, that Amal takes to walk along that road.\\
\includegraphics[max width=\textwidth, alt={}, center]{fb95068f-f76d-492a-b385-bce17b26ae30-08_846_1264_445_388}
\begin{enumerate}[label=(\alph*)]
\item Amal starts his delivery round from his house, at vertex $A$. He must walk along each road at least once.
\begin{enumerate}[label=(\roman*)]
\item Find the length of an optimal Chinese postman route around the village, starting and finishing at Amal's house.
\item State the number of times that Amal passes his friend Dipak's house, at vertex $D$.
\end{enumerate}\item Dipak offers to deliver the magazines while Amal is away on holiday. Dipak must walk along each road at least once. Assume that Dipak takes the same length of time as Amal to walk along each road.
\begin{enumerate}[label=(\roman*)]
\item Dipak can start his journey at any vertex and finish his journey at any vertex. Find the length of time for an optimal route for Dipak.
\item State the vertices at which Dipak could finish, in order to achieve his optimal route.
\end{enumerate}\item \begin{enumerate}[label=(\roman*)]
\item Find the length of time for an optimal route for Dipak, if, instead, he wants to finish at his house, at vertex $D$, and can start his journey at any other vertex.
\item State the start vertex.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2016 Q4 [11]}}