Standard +0.3 This is a standard textbook application of dynamic programming with a minimax objective on a simple network. The algorithm is routine (working backwards, comparing maximum costs along paths), requires no novel insight, and is a direct application of taught methods. Slightly easier than average due to the small network size and straightforward minimax criterion.
\end{figure}
Figure 1 represents the maintenance choices a council can make and their costs, in \(\pounds 1000\) s, over the next four years.
The council wishes to minimise the greatest annual cost of maintenance.
Use dynamic programming to find a minimax route from S to T .
(9)
State your route and the greatest annual cost incurred by the council.
(2)
Calculate the average annual cost to the council.
(2)
The images you've shared appear to be completely blank or white — I cannot see any mark scheme content in them. The only visible text is on the third image, which shows publishing information for Edexcel Publications (Summer 2010, Order Code UA023714).
Could you please re-upload the mark scheme pages? It's possible the images didn't upload correctly or the content is not rendering visibly. Once I can see the actual mark scheme content, I'll be happy to extract and format it as requested.
# Question 4:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| First stage T complete, working backwards | 1M1 | |
| Stage 1 values correct | 1A1 | cao (condone lack of *) |
| Second stage completed | 2M1 | Penalise reversed states here and in (b); bod if something in each column |
| Any 2 states correct | 2A1 | Penalise * errors with an A mark only once in the question |
| All 3 states correct | 3A1 | Penalise * errors only once in the question |
| $3^{rd}$ and $4^{th}$ stages completed | 3M1 | Bod if something in each column |
| Any 2 states correct | 4A1ft | Penalise * errors only once; A, B or C |
| All 3 states correct | 5A1ft | Penalise * errors only once; A, B and C |
| Final S state correct | 6A1ft | Penalise * errors only once |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route (S to T or reverse) and cost stated | 1M1 | |
| Correct route and cost | 1A1ft | cao; penalise reversed states here |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Sum of four arcs $\div 4$ | 1M1 | Do not award if they 'add' to this method |
| Correct answer | 1A1 | cao; $32\,500$ gets both marks |
**Special Cases:**
| Case | Description | Max Marks |
|------|-------------|-----------|
| SC1 Maximin | Treat as misread | MAX 11/13 |
| SC2 Maximum route | 1M1,1A1; 2M0; 3M1,4A1ft,5A0,6A1ft, M1A1ft M1A1ft | MAX 9/13 |
| SC3 Minimum route | Marks as SC2 | — |
| SC4 Maximax | 1M1,1A1; 2M0; 3M1,4A0,5A0,6A0,M1A1ft M1A1ft | MAX 7/13 |
| SC5 Minimin | Marks as SC4 | — |
| SC6 Working forwards | 1M1,1A0; 2M0; 3M1,4A0,5A0,6A0,M1A1ft M1A1ft | MAX 6/13 |
# SC 5 Minimin
**Stage 1 (working backwards from T):**
| Answer | Mark | Guidance |
|--------|------|----------|
| GT = 17*, HT = 21*, IT = 29* | B1 | Values at stage 1 correct with asterisks |
**Stage 2:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $\min(22,17)=17^*$, $\min(31,21)=21$, $\min(34,21)=21^*$, $\min(39,29)=29$, $\min(52,29)=29^*$ | B1 | Stage 2 values correct with asterisks |
**Stage 3:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $\min(41,17)=17^*$, $\min(38,21)=21$, $\min(44,21)=21^*$, $\min(36,21)=21^*$, $\min(35,29)=29$ | B1 | Stage 3 values correct with asterisks |
**Stage 4:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $\min(37,17)=17^*$, $\min(39,21)=21$, $\min(41,21)=21$ | B1 | Stage 4 values correct |
**Route:** SADGT | B1 | Route correctly identified |
---
# SC 6 Working forwards S to T
**Stage 1:**
| Answer | Mark | Guidance |
|--------|------|----------|
| AS = 37*, BS = 39*, CS = 41* | B1 | Stage 1 values correct with asterisks |
**Stage 2:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $\max(41,37)=41^*$, $\max(38,37)=38^*$, $\max(44,39)=44$, $\max(36,41)=41$, $\max(35,41)=41^*$ | B1 | Stage 2 values correct with asterisks |
**Stage 3:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $\max(22,41)=41^*$, $\max(31,41)=41$, $\max(34,38)=38^*$, $\max(39,38)=39^*$, $\max(52,41)=52$ | B1 | Stage 3 values correct with asterisks |
**Stage 4:**
| Answer | Mark | Guidance |
|--------|------|----------|
| $\max(17,41)=41$, $\max(21,38)=38^*$, $\max(29,39)=39$ | B1 | Stage 4 values correct |
**Route:** SAEHT | B1 | Route correctly identified |
---
# Q6b Misreads — Alternative 1 (Increasing $x$ first, then $y$, then $z$)
**Tableau 1 (increasing $x$):**
| Answer | Mark | Guidance |
|--------|------|----------|
| $r$: row unchanged; $x$: $R_2 \div 2$; $t$: $R_3 + R_2$; $P$: $R_4 + R_2$ | M1 A1 | Correct pivot operations on $x$ column |
| Values: $r=24$, $x=14$, $t=36$, $P=14$ | A1 | Correct values |
**Tableau 2 (increasing $y$):**
| Answer | Mark | Guidance |
|--------|------|----------|
| $y: R_1\div 1$; $x: R_2-\frac{1}{2}R_1$; $t: R_3-R_1$; $P: R_4+\frac{3}{2}R_1$ | M1 A1 | Correct pivot operations on $y$ column |
| Values: $y=24$, $x=2$, $t=12$, $P=50$ | A1 | Correct values |
**Tableau 3 (increasing $z$):**
| Answer | Mark | Guidance |
|--------|------|----------|
| $y: R_1-2R_2$; $z: R_2\div 2$; $t: R_3-3R_2$; $P: R_4+R_2$ | M1 A1 | Correct pivot on $z$ column |
| Values: $y=20$, $z=2$, $t=6$, $P=52$ | A1 | Optimal value $P=52$ |
---
# Q6b Misreads — Alternative 2 (Increasing $x$, then $z$, then $y$)
**Tableau 1 (increasing $x$):** Same as Alternative 1 first tableau | M1 A1 A1 | As above |
**Tableau 2 (increasing $z$):**
| Answer | Mark | Guidance |
|--------|------|----------|
| $r: R_1-2R_2$; $z: R_2\div 2$; $t: R_3-5R_2$; $P: R_4+4R_2$ | M1 A1 | Correct pivot on $z$ |
| Values: $r=10$, $z=7$, $t=1$, $P=42$ | A1 | Correct values |
**Tableau 3 (increasing $y$):**
| Answer | Mark | Guidance |
|--------|------|----------|
| $y: R_1\div\frac{1}{2}$; $z: R_2-\frac{1}{4}R_1$; $t: R_3+\frac{1}{4}R_1$; $P: R_4+\frac{1}{2}R_1$ | M1 A1 | Correct pivot on $y$ |
| Values: $y=20$, $z=2$, $t=6$, $P=52$ | A1 | Optimal value $P=52$ |
---
# Q6b Misreads — Alternative 3 (Increasing $y$, then $x$, then $z$)
**Tableau 1 (increasing $y$):**
| Answer | Mark | Guidance |
|--------|------|----------|
| $y: R_1\div 1$; $s: R_2-R_1$; $t: R_3-\frac{1}{2}R_1$; $P: R_4+2R_1$ | M1 A1 | Correct pivot on $y$ |
| Values: $y=24$, $s=4$, $t=10$, $P=48$ | A1 | Correct values |
**Tableau 2 (increasing $x$):**
| Answer | Mark | Guidance |
|--------|------|----------|
| $y$: no change; $x: R_2\div 2$; $t: R_3-3R_2$; $P: R_4+R_2$ | M1 A1 | Correct pivot on $x$ |
| Values: $y=24$, $x=2$, $t=12$, $P=50$ | A1 | Correct values |
**Tableau 3 (increasing $z$):**
| Answer | Mark | Guidance |
|--------|------|----------|
| $y: R_1-2R_2$; $z: R_2\div 1$; $t: R_3+R_2$; $P: R_4+R_2$ | M1 A1 | Correct pivot on $z$ |
| Values: $y=20$, $z=2$, $t=6$, $P=52$ | A1 | Optimal value $P=52$ |
---
# Q6b Misreads — Alternative 4 (Increasing $y$, then $z$)
**Tableau 1 (increasing $y$):** Same as Alternative 3 first tableau | M1 A1 A1 | As above |
**Tableau 2 (increasing $z$):**
| Answer | Mark | Guidance |
|--------|------|----------|
| $y: R_1-2R_2$; $z: R_2\div 2$; $t: R_3-2R_2$; $P: R_4+2R_2$ | M1 A1 | Correct pivot on $z$ |
| Values: $y=20$, $z=2$, $t=6$, $P=52$ | A1 | Optimal value $P=52$ |
The images you've shared appear to be completely blank or white — I cannot see any mark scheme content in them. The only visible text is on the third image, which shows publishing information for Edexcel Publications (Summer 2010, Order Code UA023714).
Could you please re-upload the mark scheme pages? It's possible the images didn't upload correctly or the content is not rendering visibly. Once I can see the actual mark scheme content, I'll be happy to extract and format it as requested.
4.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{a91f96a3-a9b4-4bf5-bfdf-93c34912e54a-5_774_1623_264_221}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}
Figure 1 represents the maintenance choices a council can make and their costs, in $\pounds 1000$ s, over the next four years.
The council wishes to minimise the greatest annual cost of maintenance.
\begin{enumerate}[label=(\alph*)]
\item Use dynamic programming to find a minimax route from S to T .\\
(9)
\item State your route and the greatest annual cost incurred by the council.\\
(2)
\item Calculate the average annual cost to the council.\\
(2)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2010 Q4 [13]}}