| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2008 |
| Session | June |
| Marks | 11 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Chinese Postman with flexible endpoints |
| Difficulty | Standard +0.8 This is a multi-part Chinese Postman problem requiring identification of odd-degree vertices, calculation of minimum pairings for different start/end constraints, and understanding of Eulerian path theory. Part (c) requires insight that optimal flexible routes connect two odd vertices. More demanding than standard single-variant CPP questions but follows established D1 algorithms. |
| Spec | 7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Odds \(A, B, C, D\) | M1 | PI (but \(A, B, C, D\) must be mentioned) |
| m1 | Considering 3 sets of pairings of odd vertices, eg \(AB\) with \(CD\) etc | |
| \(AB + CD = 270 + 270 = 540\) | ||
| \(AC + BD = 290 + 290 = 580\) | A2,1,0 | A1 for 2 correct, A2 for all correct |
| \(AD + BC = 260 + 270 = 530\) | ||
| Repeat \(AD\), \(BC\) | A1F | Follow through their shortest pairing. PI by adding 530 to 1920. Or \(AEHD\) or \(DHEA\) and \(BFGC\) or \(CGFB\) listed in any route |
| (Length = 1920 + 530) = 2450 (metres) | B1 | 6 |
| Answer | Marks | Guidance |
|---|---|---|
| Repeats \(BC\) | E1 | PI by \(BFGC\) or \(CGFB\) listed in a complete route or adding 270 / subtracting 260 |
| (Length = 1920 + 270) = 2190 (metres) | B1 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Min. repeat \(AD\) | E1 | PI by \(AEHD\) or \(DHEA\) listed in a complete route or adding 260 / subtracting 270 |
| (Length = 1920 + 260) = 2180 (metres) | B1 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| \(B, C\) | B1 | 1 |
| Total | 11 |
## 5(a)
| Odds $A, B, C, D$ | M1 | PI (but $A, B, C, D$ must be mentioned) |
| | m1 | Considering 3 sets of pairings of odd vertices, eg $AB$ with $CD$ etc |
| $AB + CD = 270 + 270 = 540$ | | |
| $AC + BD = 290 + 290 = 580$ | A2,1,0 | A1 for 2 correct, A2 for all correct |
| $AD + BC = 260 + 270 = 530$ | | |
| Repeat $AD$, $BC$ | A1F | Follow through their shortest pairing. PI by adding 530 to 1920. Or $AEHD$ or $DHEA$ and $BFGC$ or $CGFB$ listed in any route |
| (Length = 1920 + 530) = 2450 (metres) | B1 | 6 |
## 5(b)
| Repeats $BC$ | E1 | PI by $BFGC$ or $CGFB$ listed in a complete route or adding 270 / subtracting 260 |
| (Length = 1920 + 270) = 2190 (metres) | B1 | 2 | 2450 – 260 = 2190 (2190 with no evidence scores E0B1) |
## 5(c)(i)
| Min. repeat $AD$ | E1 | PI by $AEHD$ or $DHEA$ listed in a complete route or adding 260 / subtracting 270 |
| (Length = 1920 + 260) = 2180 (metres) | B1 | 2 | 2450 – 270 = 2180 (2180 with no evidence scores E0B1) |
## 5(c)(ii)
| $B, C$ | B1 | 1 | Condone start at $B$, finish at $C$ (or reverse) |
| Total | | 11 |5 The diagram shows a network of sixteen roads on a housing estate. The number on each edge is the length, in metres, of the road. The total length of the sixteen roads is 1920 metres.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-05_1371_1267_466_422}
\captionsetup{labelformat=empty}
\caption{Total Length = 1920 metres}
\end{center}
\end{figure}
\begin{enumerate}[label=(\alph*)]
\item Chris, an ice-cream salesman, travels along each road at least once, starting and finishing at the point $A$. Find the length of an optimal 'Chinese postman' route for Chris.
\item Pascal, a paperboy, starts at $A$ and walks along each road at least once before finishing at $D$. Find the length of an optimal route for Pascal.
\item Millie is to walk along all the roads at least once delivering leaflets. She can start her journey at any point and she can finish her journey at any point.
\begin{enumerate}[label=(\roman*)]
\item Find the length of an optimal route for Millie.
\item State the points from which Millie could start in order to achieve this optimal route.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2008 Q5 [11]}}