| Exam Board | Edexcel |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Year | 2023 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Route Inspection |
| Type | Route inspection with parameter |
| Difficulty | Challenging +1.2 This is a standard route inspection problem with a parameter, requiring identification of odd vertices, application of the Chinese Postman algorithm, and solving an inequality. While it involves multiple steps and algebraic manipulation with constraints, the techniques are routine for Further Maths students and the problem structure is typical of textbook exercises in Decision Mathematics. |
| Spec | 7.02g Eulerian graphs: vertex degrees and traversability7.04e Route inspection: Chinese postman, pairing odd nodes |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(1\) | B1 | cao |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| The route is not an example of a path as vertex C appears twice | B1 | Must refer to C appearing twice (not just that a vertex is repeated) or that it contains cycle \(C-F-E-C\). All technical language must be correct. Do not isw any incorrect reasoning |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| As the route contains two roads that need to be traversed twice, either pairing AB, AC or BD, CD needs to be repeated | B1 | Recognising that one of the two pairings between B and C containing two arcs will need to be repeated. Condone those who consider direct arc BC provided at least one pairing via A or D is considered too |
| \(AB + AC = 3x+6\) and \(BD + CD = 3x+2\) and as \(3x+6 > 3x+2\) (for all \(x\)), \(BD + CD\) are repeated | B1 | Correct deduction that \(BD+CD\) needs to be repeated (or \(AB+AC\) is not repeated). Must see both simplified expressions. Cannot be awarded if other inequalities formed unless explicitly rejected with correct reason |
| \(5x - 8 > 3x + 2\) | M1 | Considers explicitly direct route between B and C (\(5x-8\)) and compares with either pairing \(AB+AC\) or \(BD+CD\) |
| \(x > 5\) | A1 | cao |
| \((20x+3) + (3x+2) \leqslant 189\) | M1 | \((20x+3)\) + (either \(3x+6\) or \(3x+2\)) together with 189 (allow equals or any inequality) |
| \(x \leqslant 8\) | A1 | cao. Note: If full marks awarded in (c) but any other inequalities apart from \(x>5\) and \(x \leqslant 8\) are found, withhold the second B mark |
## Question 5:
### Part 5(a):
| Answer | Marks | Guidance |
|--------|-------|----------|
| $1$ | B1 | cao |
### Part 5(b):
| Answer | Marks | Guidance |
|--------|-------|----------|
| The route is not an example of a path as vertex C appears twice | B1 | Must refer to C appearing twice (not just that a vertex is repeated) or that it contains cycle $C-F-E-C$. All technical language must be correct. Do not isw any incorrect reasoning |
### Part 5(c):
| Answer | Marks | Guidance |
|--------|-------|----------|
| As the route contains two roads that need to be traversed twice, either pairing AB, AC or BD, CD needs to be repeated | B1 | Recognising that **one** of the two pairings between B and C containing two arcs will need to be repeated. Condone those who consider direct arc BC provided at least one pairing via A or D is considered too |
| $AB + AC = 3x+6$ and $BD + CD = 3x+2$ and as $3x+6 > 3x+2$ (for all $x$), $BD + CD$ are repeated | B1 | Correct deduction that $BD+CD$ needs to be repeated (or $AB+AC$ is not repeated). Must see both simplified expressions. Cannot be awarded if other inequalities formed unless explicitly rejected with correct reason |
| $5x - 8 > 3x + 2$ | M1 | Considers explicitly direct route between B and C ($5x-8$) and compares with either pairing $AB+AC$ **or** $BD+CD$ |
| $x > 5$ | A1 | cao |
| $(20x+3) + (3x+2) \leqslant 189$ | M1 | $(20x+3)$ + (either $3x+6$ or $3x+2$) together with 189 (allow equals or any inequality) |
| $x \leqslant 8$ | A1 | cao. **Note:** If full marks awarded in (c) but any other inequalities apart from $x>5$ and $x \leqslant 8$ are found, withhold the second B mark |5.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{9edb5209-4244-4916-b3ee-d77e395e8cab-06_873_739_178_664}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{center}
\end{figure}
[The weight of the network is $20 x + 3$ ]
Figure 4 shows a graph G that contains 8 arcs and 6 vertices.
\begin{enumerate}[label=(\alph*)]
\item State the minimum number of arcs that would need to be added to make G into an Eulerian graph.
\item Explain whether or not the route $\mathrm { A } - \mathrm { C } - \mathrm { F } - \mathrm { E } - \mathrm { C } - \mathrm { D } - \mathrm { B }$ is an example of a path on G.
Figure 4 represents a network of 8 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
You are given that $x > 1.6$\\
A route is required that
\begin{itemize}
\item starts and finishes at the same vertex
\item traverses each road at least once
\item minimises the total time taken
\end{itemize}
The route inspection algorithm is applied to the network in Figure 4 and the time taken for the route is found to be at most 189 minutes.
Given that the inspection route contains two roads that need to be traversed twice,
\item determine the range of possible values of $x$, making your reasoning clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD1 AS 2023 Q5 [8]}}