Question 5 - A-Level Maths

OCR D2 2011 January — Question 5 18 marks

Exam Board	OCR
Module	D2 (Decision Mathematics 2)
Year	2011
Session	January
Marks	18
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Dynamic Programming
Type	Dynamic programming order sequencing
Difficulty	Moderate -0.5 This is a standard D2 dynamic programming question with routine state-space formulation. Part (i) requires simple arithmetic along a given path, (ii) tests understanding of visiting constraints (straightforward conceptual check), and (iii) asks students to trace back through a partially completed DP table—all mechanical applications of the standard algorithm with no novel problem-solving required.
Spec	7.01a Types of problem: existence, construction, enumeration, optimisation 7.08a Pay-off matrix: zero-sum games 7.08b Dominance: reduce pay-off matrix 7.08c Pure strategies: play-safe strategies and stable solutions 7.08d Nash equilibrium: identification and interpretation 7.08e Mixed strategies: optimal strategy using equations or graphical method

5 A card game between two players consists of several rounds. In each round the players both choose a card from those in their hand; they then show these cards to each other and exchange tokens. The number of tokens that the second player gives to the first player depends on the colour of the first player's card and the design on the second player's card. The table shows the number of tokens that the first player receives for each combination of colour and design. A negative entry means that the first player gives tokens to the second, zero means that no tokens are exchanged. Let the stages be $0,1,2,3,4,5$. Stage 0 represents arriving at the sanctuary entrance. Stage 1 represents visiting the first bird, stage 2 the second bird, and so on, with stage 5 representing leaving the sanctuary. Let the states be $0,1,2,3,4$ representing the entrance/exit, kite, lark, moorhen and nightjar respectively.

Calculate how many minutes it takes to travel the route $$( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 4 ) - ( 5 ; 0 ) .$$ The friends then realise that if they try to find the quickest route using dynamic programming with this (stage; state) formulation, they will get the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$, or this in reverse, taking 27 minutes.
Explain why the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$ is not a solution to the friends' problem. Instead, the friends set up a dynamic programming tabulation with stages and states as described above, except that now the states also show, in brackets, any birds that have already been visited. So, for example, state $1 ( 234 )$ means that they are currently visiting the kite and have already visited the other three birds in some order. The partially completed dynamic programming tabulation is shown opposite.
For the last completed row, i.e. stage 2, state 1(3), action 4(13), explain where the value 18 and the value 6 in the working column come from.

Complete the table in the insert and hence find the order in which the birds should be visited to give a quickest route and find the corresponding minimum journey time.

Stage

State

Action

Working

Suboptimal minimum

\multirow{4}{*}{4}

1(234)

2(134)

3(124)

4(123)

\multirow{12}{*}{3}

1(23)

4(123)

$17 + 6 = 23$

1(24)

3(124)

$12 + 2 = 14$

1(34)

2(134)

$14 + 3 = 17$

2(13)

4(123)

$17 + 4 = 21$

2(14)

3(124)

$12 + 2 = 14$

2(34)

1(234)

$10 + 3 = 13$

3(12)

4(123)

$17 + 3 = 20$

3(14)

2(134)

$14 + 2 = 16$

3(24)

1(234)

$10 + 2 = 12$

4(12)

3(124)

$12 + 3 = 15$

4(13)

2(134)

$14 + 4 = 18$

4(23)

1(234)

$10 + 6 = 16$

\multirow{12}{*}{2}

1(2)

3(12) 4(12)

$20 + 2 = 22$

1(3)

2(13) 4(13)

$21 + 3 = 24 18 + 6 = 24$

1(4)

2(1)

2(3)

2(4)

3(1)

3(2)

3(4)

4(1)

4(2)

4(3)

\multirow{4}{*}{1}

Show mark scheme Show mark scheme source

Question 5(i):

Answer	Marks	Guidance
Answer	Mark	Guidance
The number of tokens that the first player gains equals the number that the second player loses. The total number of tokens is unchanged.	B1	Explaining why game is zero-sum; Describing a single instance not what happens in the long run
Collaboration cannot benefit both players; No reason to cooperate	B1	Describing what zero-sum means for the way in which the players play the game; Not just 'one player can only gain by making the other lose'

Question 5(ii):

Answer	Marks	Guidance
Answer	Mark	Guidance
Finding row minima and maximin correctly (numerical values must be seen)	M1	Row maximin is $-1$
Finding col maxima and minimax correctly (or negatives of these), numerical values must be seen	M1	Col minimax is $1$
Play-safe strategy for first player is Red; Play-safe strategy for second player is Triangle	A1	Finding Red (R) and Triangle (T or $\Delta$), following both method marks gained
Game is unstable since $1 \neq -1$; row maximin $\neq$ col minimax	B1	Unstable and a correct reason (may be explained in words, e.g. if second chooses triangle then first would do better by choosing blue)
In a stable game, playing safe is the best strategy for each player in the long run	B1	Explaining what play-safe strategies mean for a stable game
In an unstable game, playing safe cannot be the best strategy for both players	B1	Explaining what play-safe strategies mean for the playing of an unstable game

Question 5(iii):

Answer	Marks	Guidance
Answer	Mark	Guidance
Red: $-2 < -1$; Yellow: $2 < 3$; In each row the entry for square is bigger than the entry for circle, so the second player loses more by choosing square than by choosing circle. The second player should not choose square.	B1	Showing both comparisons (or equivalent) or in words; Circle dominates square (given) as the pay-off is better (for the second player) in each row; Do not choose square

Question 5(iv):

Answer	Marks	Guidance
Answer	Mark	Guidance
Triangle: $-1(p) + 0(1-p) = -p$; Circle: $1(p) - 3(1-p) = 4p - 3$	B1	Both expressions correct (in any form); may also have square: $2p - 2(1-p) = 4p-2$
Sketch graph showing two lines intersecting	B1	Either a correct sketch graph (condone missing scales and/or labels), no ft, except may have $4p-2$ as well; or correct reasoning (considering $p=0$, $p=1$ and intersection or using gradients); Calculating intersection on its own is not enough
$-p = 4p - 3 \Rightarrow p = 0.6$	B1	$0.6$ cao; If circle column was removed in (iii), instead of square then ft for (iv) to $p = 0.4$

Question 5(v):

Answer	Marks	Guidance
Answer	Mark	Guidance
New table with Blue row multiplied by $-1$, giving Blue row: $5, -1, -3$	—	Values for Blue being multiplied by $-1$ was given in question
Add 3 throughout to make all entries non-negative; giving augmented table with Red: $5,2,4$; Yellow: $1,3,0$; Blue: $8,2,0$	M1	$-5$ becomes $5$, then add $3$ to values; This table is sufficient for the M mark
When second player chooses square, first expects to win $5x + y + 8z$ in augmented table	A1	Square, or first column, explicitly identified as giving the constraint

Question 5(vi):

Answer	Marks	Guidance
Answer	Mark	Guidance
$5x + y + 8z = 3.4$; $2x + 3y + 2z = 2.4$; $4x = 2.4$	M1	At least one of the values $3.4, 2.4, 2.4$ correct
All three values	A1	All three values
$m \leq 3.4, 2.4, 2.4 \Rightarrow m \leq 2.4$; $M = m - 3 \Rightarrow M \leq -0.6$; Need maximum value of $M \Rightarrow M = -0.6$	B1	$-0.6$ cao

# Question 5(i):

| Answer | Mark | Guidance |
|--------|------|----------|
| The number of tokens that the first player gains equals the number that the second player loses. The total number of tokens is unchanged. | B1 | Explaining why game is zero-sum; Describing a single instance not what happens in the long run |
| Collaboration cannot benefit both players; No reason to cooperate | B1 | Describing what zero-sum means for the way in which the players play the game; Not just 'one player can only gain by making the other lose' |

# Question 5(ii):

| Answer | Mark | Guidance |
|--------|------|----------|
| Finding row minima and maximin correctly (numerical values must be seen) | M1 | Row maximin is $-1$ |
| Finding col maxima and minimax correctly (or negatives of these), numerical values must be seen | M1 | Col minimax is $1$ |
| Play-safe strategy for first player is Red; Play-safe strategy for second player is Triangle | A1 | Finding Red (R) and Triangle (T or $\Delta$), following both method marks gained |
| Game is unstable since $1 \neq -1$; row maximin $\neq$ col minimax | B1 | Unstable and a correct reason (may be explained in words, e.g. if second chooses triangle then first would do better by choosing blue) |
| In a stable game, playing safe is the best strategy for each player in the long run | B1 | Explaining what play-safe strategies mean for a stable game |
| In an unstable game, playing safe cannot be the best strategy for both players | B1 | Explaining what play-safe strategies mean for the playing of an unstable game |

# Question 5(iii):

| Answer | Mark | Guidance |
|--------|------|----------|
| Red: $-2 < -1$; Yellow: $2 < 3$; In each row the entry for square is bigger than the entry for circle, so the second player loses more by choosing square than by choosing circle. The second player should not choose square. | B1 | Showing both comparisons (or equivalent) or in words; Circle dominates square (given) as the pay-off is better (for the second player) in each row; Do not choose square |

# Question 5(iv):

| Answer | Mark | Guidance |
|--------|------|----------|
| Triangle: $-1(p) + 0(1-p) = -p$; Circle: $1(p) - 3(1-p) = 4p - 3$ | B1 | Both expressions correct (in any form); may also have square: $2p - 2(1-p) = 4p-2$ |
| Sketch graph showing two lines intersecting | B1 | Either a correct sketch graph (condone missing scales and/or labels), no ft, except may have $4p-2$ as well; or correct reasoning (considering $p=0$, $p=1$ and intersection or using gradients); Calculating intersection on its own is not enough |
| $-p = 4p - 3 \Rightarrow p = 0.6$ | B1 | $0.6$ cao; If circle column was removed in (iii), instead of square then ft for (iv) to $p = 0.4$ |

# Question 5(v):

| Answer | Mark | Guidance |
|--------|------|----------|
| New table with Blue row multiplied by $-1$, giving Blue row: $5, -1, -3$ | — | Values for Blue being multiplied by $-1$ was given in question |
| Add 3 throughout to make all entries non-negative; giving augmented table with Red: $5,2,4$; Yellow: $1,3,0$; Blue: $8,2,0$ | M1 | $-5$ becomes $5$, then add $3$ to values; This table is sufficient for the M mark |
| When second player chooses square, first expects to win $5x + y + 8z$ in augmented table | A1 | Square, or first column, explicitly identified as giving the constraint |

# Question 5(vi):

| Answer | Mark | Guidance |
|--------|------|----------|
| $5x + y + 8z = 3.4$; $2x + 3y + 2z = 2.4$; $4x = 2.4$ | M1 | At least one of the values $3.4, 2.4, 2.4$ correct |
| All three values | A1 | All three values |
| $m \leq 3.4, 2.4, 2.4 \Rightarrow m \leq 2.4$; $M = m - 3 \Rightarrow M \leq -0.6$; Need maximum value of $M \Rightarrow M = -0.6$ | B1 | $-0.6$ cao |

---

Show LaTeX source

5 A card game between two players consists of several rounds. In each round the players both choose a card from those in their hand; they then show these cards to each other and exchange tokens. The number of tokens that the second player gives to the first player depends on the colour of the first player's card and the design on the second player's card.

The table shows the number of tokens that the first player receives for each combination of colour and design. A negative entry means that the first player gives tokens to the second, zero means that no tokens are exchanged.

Let the stages be $0,1,2,3,4,5$. Stage 0 represents arriving at the sanctuary entrance. Stage 1 represents visiting the first bird, stage 2 the second bird, and so on, with stage 5 representing leaving the sanctuary. Let the states be $0,1,2,3,4$ representing the entrance/exit, kite, lark, moorhen and nightjar respectively.\\
(i) Calculate how many minutes it takes to travel the route

$$( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 4 ) - ( 5 ; 0 ) .$$

The friends then realise that if they try to find the quickest route using dynamic programming with this (stage; state) formulation, they will get the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$, or this in reverse, taking 27 minutes.\\
(ii) Explain why the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$ is not a solution to the friends' problem.

Instead, the friends set up a dynamic programming tabulation with stages and states as described above, except that now the states also show, in brackets, any birds that have already been visited. So, for example, state $1 ( 234 )$ means that they are currently visiting the kite and have already visited the other three birds in some order. The partially completed dynamic programming tabulation is shown opposite.\\
(iii) For the last completed row, i.e. stage 2, state 1(3), action 4(13), explain where the value 18 and the value 6 in the working column come from.\\
(iv) Complete the table in the insert and hence find the order in which the birds should be visited to give a quickest route and find the corresponding minimum journey time.

\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Stage & State & Action & Working & Suboptimal minimum \\
\hline
\multirow{4}{*}{4} & 1(234) & 0 & 10 & 10 \\
\hline
 & 2(134) & 0 & 14 & 14 \\
\hline
 & 3(124) & 0 & 12 & 12 \\
\hline
 & 4(123) & 0 & 17 & 17 \\
\hline
\multirow{12}{*}{3} & 1(23) & 4(123) & $17 + 6 = 23$ & 23 \\
\hline
 & 1(24) & 3(124) & $12 + 2 = 14$ & 14 \\
\hline
 & 1(34) & 2(134) & $14 + 3 = 17$ & 17 \\
\hline
 & 2(13) & 4(123) & $17 + 4 = 21$ & 21 \\
\hline
 & 2(14) & 3(124) & $12 + 2 = 14$ & 14 \\
\hline
 & 2(34) & 1(234) & $10 + 3 = 13$ & 13 \\
\hline
 & 3(12) & 4(123) & $17 + 3 = 20$ & 20 \\
\hline
 & 3(14) & 2(134) & $14 + 2 = 16$ & 16 \\
\hline
 & 3(24) & 1(234) & $10 + 2 = 12$ & 12 \\
\hline
 & 4(12) & 3(124) & $12 + 3 = 15$ & 15 \\
\hline
 & 4(13) & 2(134) & $14 + 4 = 18$ & 18 \\
\hline
 & 4(23) & 1(234) & $10 + 6 = 16$ & 16 \\
\hline
\multirow{12}{*}{2} & 1(2) & 3(12) 4(12) & \(20 + 2 = 22\) & 21 \\
\hline
 & 1(3) & 2(13) 4(13) & $21 + 3 = 24 18 + 6 = 24$ & 24 \\
\hline
 & 1(4) &  &  &  \\
\hline
 & 2(1) &  &  &  \\
\hline
 & 2(3) &  &  &  \\
\hline
 & 2(4) &  &  &  \\
\hline
 & 3(1) &  &  &  \\
\hline
 & 3(2) &  &  &  \\
\hline
 & 3(4) &  &  &  \\
\hline
 & 4(1) &  &  &  \\
\hline
 & 4(2) &  &  &  \\
\hline
 & 4(3) &  &  &  \\
\hline
\multirow{4}{*}{1} & 1 &  &  &  \\
\hline
 & 2 &  &  &  \\
\hline
 & 3 &  &  &  \\
\hline
 & 4 &  &  &  \\
\hline
0 & 0 & \begin{tabular}{l}
1 \\
2 \\
3 \\
4 \\
\end{tabular} &  &  \\
\hline
\end{tabular}
\end{center}

\hfill \mbox{\textit{OCR D2 2011 Q5 [18]}}

This paper (6 questions)

View full paper

Q1 4 Q2 7 Q3 12 Q4 18 Q5 18 Q6 13