| Exam Board | AQA |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2009 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Topic | Travelling Salesman |
| Type | MST with Parameter Constraint |
| Difficulty | Challenging +1.2 This question requires systematic application of inequalities to find a parameter value, combining nearest neighbour algorithm knowledge with algebraic manipulation. While it involves multiple steps and careful reasoning about which edges are shortest, each individual step is straightforward inequality work. The structure is guided and methodical rather than requiring novel insight, making it moderately above average difficulty for D1. |
| Spec | 7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree |
| \(\boldsymbol { A }\) | \(\boldsymbol { B }\) | \(\boldsymbol { C }\) | \(\boldsymbol { D }\) | \(\boldsymbol { E }\) | |
| A | - | \(x + 6\) | \(2 x - 4\) | \(3 x - 7\) | \(4 x - 14\) |
| \(\boldsymbol { B }\) | \(x + 6\) | - | \(3 x - 7\) | \(3 x - 9\) | \(x + 9\) |
| \(\boldsymbol { C }\) | \(2 x - 4\) | \(3 x - 7\) | - | \(2 x - 1\) | \(x + 8\) |
| \(\boldsymbol { D }\) | \(3 x - 7\) | \(3 x - 9\) | \(2 x - 1\) | - | \(2 x - 2\) |
| E | \(4 x - 14\) | \(x + 9\) | \(x + 8\) | \(2 x - 2\) | - |
7 Liam is taking part in a treasure hunt. There are five clues to be solved and they are at the points $A , B , C , D$ and $E$. The table shows the distances between pairs of points. All of the distances are functions of $x$, where $\boldsymbol { x }$ is an integer.
Liam must travel to all five points, starting and finishing at $A$.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
& $\boldsymbol { A }$ & $\boldsymbol { B }$ & $\boldsymbol { C }$ & $\boldsymbol { D }$ & $\boldsymbol { E }$ \\
\hline
A & - & $x + 6$ & $2 x - 4$ & $3 x - 7$ & $4 x - 14$ \\
\hline
$\boldsymbol { B }$ & $x + 6$ & - & $3 x - 7$ & $3 x - 9$ & $x + 9$ \\
\hline
$\boldsymbol { C }$ & $2 x - 4$ & $3 x - 7$ & - & $2 x - 1$ & $x + 8$ \\
\hline
$\boldsymbol { D }$ & $3 x - 7$ & $3 x - 9$ & $2 x - 1$ & - & $2 x - 2$ \\
\hline
E & $4 x - 14$ & $x + 9$ & $x + 8$ & $2 x - 2$ & - \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item The nearest point to $A$ is $C$.
\begin{enumerate}[label=(\roman*)]
\item By considering $A C$ and $A B$, show that $x < 10$.
\item Find two other inequalities in $x$.
\end{enumerate}\item The nearest neighbour algorithm, starting from $A$, gives a unique minimum tour $A C D E B A$.
\begin{enumerate}[label=(\roman*)]
\item By considering the fact that Liam's tour visits $D$ immediately after $C$, find two further inequalities in $x$.
\item Find the value of the integer $x$.
\item Hence find the total distance travelled by Liam if he uses this tour.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{AQA D1 2009 Q7 [13]}}