Question 3 - A-Level Maths

Edexcel FD1 AS 2024 June — Question 3 11 marks

Exam Board	Edexcel
Module	FD1 AS (Further Decision 1 AS)
Year	2024
Session	June
Marks	11
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Shortest Path
Type	Chinese Postman with start/end constraints
Difficulty	Challenging +1.2 This is a multi-part Chinese Postman problem requiring Dijkstra's algorithm, identification of odd vertices, and solving simultaneous constraints. While it involves several techniques, each step is algorithmic and follows standard procedures taught in FD1. The constraint-solving in part (e) is straightforward algebra. More challenging than average due to multiple parts and integration of concepts, but still within standard Further Maths AS expectations.
Spec	7.02b Graph terminology: tree, simple, connected, simply connected 7.04a Shortest path: Dijkstra's algorithm 7.04e Route inspection: Chinese postman, pairing odd nodes

3. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{ca57c64b-0b33-4179-be7f-684bd6ea2162-06_764_1547_314_355} \captionsetup{labelformat=empty} \caption{Figure 3}

\end{figure} [The total weight of the network is $139 + x + y$ ]

Explain what is meant by the term "tree". Figure 3 represents a network of walkways in a warehouse.
The arcs represent the walkways and the nodes represent junctions between them.
The number on each arc represents the length, in metres, of the corresponding walkway.
The values $x$ and $y$ are unknown, however it is known that $x$ and $y$ are integers and that $$9 < x < y < 14$$
1. Use Dijkstra's algorithm to find the shortest route from A to M.
2. State an expression for the length of the shortest route from A to M . The warehouse manager wants to check that all of the walkways are in good condition.
  Their inspection route starts at B and finishes at C .
  The inspection route must traverse each walkway at least once and be as short as possible.
State the arcs that are traversed twice.
State the number of times that H appears in the inspection route. The warehouse manager finds that the total length of the inspection route is 172 metres.
Determine the value of $x$ and the value of $y$

Show mark scheme Show mark scheme source

Question 3:

Part (a)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
A tree is a connected graph with no cycles	B1	Must state "connected" graph and must state "no cycles". Paths and/or loops are NOT correct

Part (b)(i)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
Working value in at least three boxes and a larger numerical value replaced by smaller in at least two of C, F, G, H	M1	1.1b
All values in A, B, C, E, F, K correct. Condone lack of 0 in A's working value	A1 (A,B,C,E,F,K)	Penalise order of labelling only once per question. A, B, C, E, F, K must be labelled in that order
All values D, J, H correct and working values in correct order	A1 (D,J,H)	Check D, J, H labelled in that order and D labelled before K
All values/expressions in G, L, M correct on follow through and working values in correct order	A1ft (G,L,M)	To follow through M, check working value follows from candidate's final values from feeds into M. Note $x+15\ x+23$ is fine, but $x+23\ x+15$ is incorrect and scores A0. Do not award ft if candidate has used numerical values

Part (b)(ii)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
Shortest route from A to M is AEJHLM	A1	CAO
Length of shortest route is $x + 15$	A1ft	ft their final value at M only (must be an expression)

Part (c)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
Arcs HL and LM need to be traversed twice	B1	CAO (arcs HL and LM, NOT H(L)M). Do NOT accept if extra arcs included

Part (d)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
H would appear 3 times	B1	CAO. NOT dependent on the correct repeated arcs in part (c)

Part (e)

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
$139 + x + y + 5 + 3 = 172$	M1	Setting total weight of network ($139 + x + y$) plus 8 (or their repeated arcs) equal to 172
$x + y = 25$
$x = 12,\ y = 13$	A1	CAO both values clearly assigned. Dependent on correct repeated arcs [accept minimum sight of H and M and 8 (5+3) in part (c)]. If $x=12, y=13$ stated with no working, M0A0

# Question 3:

## Part (a)
| Answer/Working | Mark | Guidance |
|---|---|---|
| A tree is a connected graph with no cycles | B1 | Must state "connected" graph and must state "no cycles". Paths and/or loops are NOT correct |

## Part (b)(i)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Working value in at least three boxes and a larger numerical value replaced by smaller in at least two of C, F, G, H | M1 | 1.1b |
| All values in A, B, C, E, F, K correct. Condone lack of 0 in A's working value | A1 (A,B,C,E,F,K) | Penalise order of labelling only once per question. A, B, C, E, F, K must be labelled in that order |
| All values D, J, H correct and working values in correct order | A1 (D,J,H) | Check D, J, H labelled in that order and D labelled before K |
| All values/expressions in G, L, M correct on follow through and working values in correct order | A1ft (G,L,M) | To follow through M, check working value follows from candidate's final values from feeds into M. Note $x+15\ x+23$ is fine, but $x+23\ x+15$ is incorrect and scores A0. Do not award ft if candidate has used numerical values |

## Part (b)(ii)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Shortest route from A to M is AEJHLM | A1 | CAO |
| Length of shortest route is $x + 15$ | A1ft | ft their final value at M only (must be an expression) |

## Part (c)
| Answer/Working | Mark | Guidance |
|---|---|---|
| Arcs HL and LM need to be traversed twice | B1 | CAO (arcs HL and LM, NOT H(L)M). Do NOT accept if extra arcs included |

## Part (d)
| Answer/Working | Mark | Guidance |
|---|---|---|
| H would appear 3 times | B1 | CAO. NOT dependent on the correct repeated arcs in part (c) |

## Part (e)
| Answer/Working | Mark | Guidance |
|---|---|---|
| $139 + x + y + 5 + 3 = 172$ | M1 | Setting total weight of network ($139 + x + y$) plus 8 (or their repeated arcs) equal to 172 |
| $x + y = 25$ | | |
| $x = 12,\ y = 13$ | A1 | CAO both values clearly assigned. Dependent on correct repeated arcs [accept minimum sight of H and M and 8 (5+3) in part (c)]. If $x=12, y=13$ stated with no working, M0A0 |

Show LaTeX source

3.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{ca57c64b-0b33-4179-be7f-684bd6ea2162-06_764_1547_314_355}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{center}
\end{figure}

[The total weight of the network is $139 + x + y$ ]
\begin{enumerate}[label=(\alph*)]
\item Explain what is meant by the term "tree".

Figure 3 represents a network of walkways in a warehouse.\\
The arcs represent the walkways and the nodes represent junctions between them.\\
The number on each arc represents the length, in metres, of the corresponding walkway.\\
The values $x$ and $y$ are unknown, however it is known that $x$ and $y$ are integers and that

$$9 < x < y < 14$$
\item \begin{enumerate}[label=(\roman*)]
\item Use Dijkstra's algorithm to find the shortest route from A to M.
\item State an expression for the length of the shortest route from A to M .

The warehouse manager wants to check that all of the walkways are in good condition.\\
Their inspection route starts at B and finishes at C .\\
The inspection route must traverse each walkway at least once and be as short as possible.
\end{enumerate}\item State the arcs that are traversed twice.
\item State the number of times that H appears in the inspection route.

The warehouse manager finds that the total length of the inspection route is 172 metres.
\item Determine the value of $x$ and the value of $y$
\end{enumerate}

\hfill \mbox{\textit{Edexcel FD1 AS 2024 Q3 [11]}}

This paper (4 questions)

View full paper

Q1 9 Q2 8 Q3 11 Q4 12