AQA D1 2009 January — Question 7 13 marks

Exam BoardAQA
ModuleD1 (Decision Mathematics 1)
Year2009
SessionJanuary
Marks13
PaperDownload PDF ↗
TopicTravelling Salesman
TypeMST with Parameter Constraint
DifficultyChallenging +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.
Spec7.04c Travelling salesman upper bound: nearest neighbour method7.04d Travelling salesman lower bound: using minimum spanning tree

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\).
\(\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\)-
  1. The nearest point to \(A\) is \(C\).
    1. By considering \(A C\) and \(A B\), show that \(x < 10\).
    2. Find two other inequalities in \(x\).
  2. The nearest neighbour algorithm, starting from \(A\), gives a unique minimum tour \(A C D E B A\).
    1. By considering the fact that Liam's tour visits \(D\) immediately after \(C\), find two further inequalities in \(x\).
    2. Find the value of the integer \(x\).
    3. Hence find the total distance travelled by Liam if he uses this tour.

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]}}