Moderate -0.8 This is a standard Further Discrete AS question testing routine application of bin-packing algorithms and understanding of online/offline terminology. Part (a) requires mechanical application of three algorithms, part (b) tests basic definitions, and part (c) involves some trial-and-error but no sophisticated insight. The question is straightforward for students who have practiced these algorithms, requiring mainly careful execution rather than problem-solving creativity.
Find the packing that results using each of these algorithms.
The next-fit method
The first-fit method
The first-fit decreasing method
A student claims that all three methods from part (a) can be used for both 'online' and 'offline' lists.
Explain why the student is wrong.
The bins of capacity 30 kg are replaced with bins of capacity \(M \mathrm {~kg}\), where \(M\) is an integer.
The item of size 23 kg can be split into two items, of sizes \(x \mathrm {~kg}\) and \(( 23 - x ) \mathrm { kg }\), where \(x\) may be any integer value you choose from 1 to 11. No other item can be split.
Determine the smallest value of \(M\) for which four bins are needed to pack these eight items.
Explain your reasoning carefully.
3 The diagram shows a simplified map of the main streets in a small town.
\includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_531_1127_301_246}
Some of the junctions have traffic lights, these junctions are labelled A to F .
There are no traffic lights at junctions X and Y .
The numbers show distances, in km, between junctions.
Alex needs to check that the traffic lights at junctions A to F are working correctly.
Find a route from A to E that has length 2.8 km .
Alex has started to construct a table of shortest distances between junctions A to F.
\includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_543_1173_1420_246}
For example, the shortest route from C to B has length 1.7 km , the shortest route from C to D has length 2.5 km and the shortest route from C to E has length 1.8 km .
Complete the copy of the table in the Printed Answer Booklet.
Use your table from part (b) to construct a minimum spanning tree for the complete graph on the six vertices A to F .
Beth starts from junction B and travels through every junction, including X and Y . Her route has length 5.1 km .
Write down the junctions in the order that Beth visited them.
Do not draw on your answer from part (c).
4 Li and Mia play a game in which they simultaneously play one of the strategies \(\mathrm { X } , \mathrm { Y }\) and Z .
The tables show the points won by each player for each combination of strategies.
A negative entry means that the player loses that number of points.
Mia
X
Y
Z
\multirow{3}{*}{Li}
X
5
- 6
0
\cline { 2 - 5 }
Y
- 2
3
4
\cline { 2 - 5 }
Z
- 1
4
8
\cline { 2 - 5 }
Mia
X
Y
Z
\multirow{2}{*}{Li}
X
4
\cline { 2 - 5 }
Y
11
5
\cline { 2 - 5 }
Z
10
5
1
\cline { 2 - 5 }
The game can be converted into a zero-sum game, this means that the total number of points won by Li and Mia is the same for each combination of strategies.
Complete the table in the Printed Answer Booklet to show the points won by Mia.
Convert the game into a zero-sum game, giving the pay-offs for Li .
Use dominance to reduce the pay-off matrix for the game to a \(2 \times 2\) table. You do not need to explain the dominance.
Mia knows that Li will choose his play-safe strategy.
Determine which strategy Mia should choose to maximise her points.
5 A linear programming problem is formulated as below.
Maximise \(\quad \mathrm { P } = 4 \mathrm { x } - \mathrm { y }\)
subject to \(2 x + 3 y \geqslant 12\)
\(x + y \leqslant 10\)
\(5 x + 2 y \leqslant 30\)
\(x \geqslant 0 , y \geqslant 0\)
Identify the feasible region by representing the constraints graphically and shading the regions where the inequalities are not satisfied.
Hence determine the maximum value of the objective.
The constraint \(x + y \leqslant 10\) is changed to \(x + y \leqslant k\), the other constraints are unchanged.
Determine, algebraically, the value of \(k\) for which the maximum value of \(P\) is 3 .
Do not draw on the graph from part (a) and do not use the spare grid.
Determine, algebraically, the other value of \(k\) for which there is a (non-optimal) vertex of the feasible region at which \(P = 3\).
Do not draw on the graph from part (a) and do not use the spare grid.
Ignore any extra lines (e.g. profit lines) or working for parts (b), (c)
Line 2x + 3y = 12
through (6, 0) and (0, 4)
Line x + y = 10
through at least two of (10, 0), (2, 8), (4, 6), (6, 4), (8, 2) and (0, 10)
Line 5x + 2y = 30
through at least two of (6, 0), (4, 5), (2, 10) and (0, 15)
Feasible region identified and correct
Answer
Marks
Guidance
5
(a)
(ii)
0 4 –4
0 10 –10
3.33 6.67 6.67
6 0 24
Answer
Marks
Maximum P = 24
M1
A1
Answer
Marks
[2]
3.1a
1.1
‘Determine’ so method must be seen, not implied
Checking at least two of their vertices
or sliding a profit line (a line of gradient 4 anywhere on graph or
indicating the vertex (6, 0))
24
Answer
Marks
Guidance
5
(b)
FR has boundaries x = 0, x + y = k, 2x + 3y = 12
x + y = k and 2x + 3y = 12 or 4x – y = 3
Profit line 4x – y = 3 cuts 2x + 3y = 12 at (1.5, 3)
Answer
Marks
k = 4.5
M1
M1
Answer
Marks
A1
3.4
3.1a
Answer
Marks
2.2a
Not graphical
Vertex where 2x + 3y = 12 and x + y = k or profit on line x + y = k
Calculate where profit = 3 on boundary 2x + 3y = 12 or (1.5, 3)
4.5
Alternative solution
Answer
Marks
Guidance
4x – (k – x) = 3 ⇒ 3x – k = 3
M1
Use x + y = k to substitute for y (or x) in 4x – y = 3
and 2x + 3(k – x) = 1 ⇒ 3k – x = 12
M1
Form a second simultaneous equation in the same unknowns
k = 4.5
A1
4.5
[3]
Answer
Marks
Guidance
x
y
P = 4x – y
5
(c)
Profit line 4x – y = 3 cuts 5x + 2y = 30
at
3 1
k =
13 , 13
141
Answer
Marks
13
M1
A1
Answer
Marks
[2]
3.1a
2.2a
Not graphical
Or or (2.7 to 2.8, 8.0 to 8.2)
1 1
Or or 10.8 to 10.9
2 1 3 , 8 1 3
11
10 13
Question 5:
5 | (a) | (i) | M1
M1
M1
A1
[4] | 1.1
1.1
1.1
1.1 | Ignore any extra lines (e.g. profit lines) or working for parts (b), (c)
Line 2x + 3y = 12
through (6, 0) and (0, 4)
Line x + y = 10
through at least two of (10, 0), (2, 8), (4, 6), (6, 4), (8, 2) and (0, 10)
Line 5x + 2y = 30
through at least two of (6, 0), (4, 5), (2, 10) and (0, 15)
Feasible region identified and correct
5 | (a) | (ii) | x y P = 4x – y
0 4 –4
0 10 –10
3.33 6.67 6.67
6 0 24
Maximum P = 24 | M1
A1
[2] | 3.1a
1.1 | ‘Determine’ so method must be seen, not implied
Checking at least two of their vertices
or sliding a profit line (a line of gradient 4 anywhere on graph or
indicating the vertex (6, 0))
24
5 | (b) | FR has boundaries x = 0, x + y = k, 2x + 3y = 12
x + y = k and 2x + 3y = 12 or 4x – y = 3
Profit line 4x – y = 3 cuts 2x + 3y = 12 at (1.5, 3)
k = 4.5 | M1
M1
A1 | 3.4
3.1a
2.2a | Not graphical
Vertex where 2x + 3y = 12 and x + y = k or profit on line x + y = k
Calculate where profit = 3 on boundary 2x + 3y = 12 or (1.5, 3)
4.5
Alternative solution
4x – (k – x) = 3 ⇒ 3x – k = 3 | M1 | Use x + y = k to substitute for y (or x) in 4x – y = 3
and 2x + 3(k – x) = 1 ⇒ 3k – x = 12 | M1 | Form a second simultaneous equation in the same unknowns
k = 4.5 | A1 | 4.5
[3]
x | y | P = 4x – y
5 | (c) | Profit line 4x – y = 3 cuts 5x + 2y = 30
at
3 1
k =
13 , 13
141
13 | M1
A1
[2] | 3.1a
2.2a | Not graphical
Or or (2.7 to 2.8, 8.0 to 8.2)
1 1
Or or 10.8 to 10.9
2 1 3 , 8 1 3
11
10 13
5
\begin{enumerate}[label=(\alph*)]
\item Find the packing that results using each of these algorithms.
\begin{enumerate}[label=(\roman*)]
\item The next-fit method
\item The first-fit method
\item The first-fit decreasing method
\end{enumerate}\item A student claims that all three methods from part (a) can be used for both 'online' and 'offline' lists.
Explain why the student is wrong.
The bins of capacity 30 kg are replaced with bins of capacity $M \mathrm {~kg}$, where $M$ is an integer.\\
The item of size 23 kg can be split into two items, of sizes $x \mathrm {~kg}$ and $( 23 - x ) \mathrm { kg }$, where $x$ may be any integer value you choose from 1 to 11. No other item can be split.
\item Determine the smallest value of $M$ for which four bins are needed to pack these eight items.
Explain your reasoning carefully.
3 The diagram shows a simplified map of the main streets in a small town.\\
\includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_531_1127_301_246}
Some of the junctions have traffic lights, these junctions are labelled A to F .\\
There are no traffic lights at junctions X and Y .\\
The numbers show distances, in km, between junctions.
Alex needs to check that the traffic lights at junctions A to F are working correctly.\\
(a) Find a route from A to E that has length 2.8 km .
Alex has started to construct a table of shortest distances between junctions A to F.\\
\includegraphics[max width=\textwidth, alt={}, center]{4db3fbc5-e664-4803-a5f2-05af376d2591-3_543_1173_1420_246}
For example, the shortest route from C to B has length 1.7 km , the shortest route from C to D has length 2.5 km and the shortest route from C to E has length 1.8 km .\\
(b) Complete the copy of the table in the Printed Answer Booklet.\\
(c) Use your table from part (b) to construct a minimum spanning tree for the complete graph on the six vertices A to F .
\begin{itemize}
\item Write down the total length of the minimum spanning tree.
\item List which arcs of the original network correspond to the arcs used in your minimum spanning tree.
\end{itemize}
Beth starts from junction B and travels through every junction, including X and Y . Her route has length 5.1 km .
\item Write down the junctions in the order that Beth visited them.
Do not draw on your answer from part (c).
4 Li and Mia play a game in which they simultaneously play one of the strategies $\mathrm { X } , \mathrm { Y }$ and Z .
The tables show the points won by each player for each combination of strategies.\\
A negative entry means that the player loses that number of points.
\begin{center}
\begin{tabular}{ c c | c | c | c }
\multicolumn{2}{c|}{\begin{tabular}{ c }
Points won \\
by Li \\
\end{tabular}} & \multicolumn{2}{|c}{Mia} & \\
& X & Y & Z & \\
\hline
\multirow{3}{*}{Li} & X & 5 & - 6 & 0 \\
\cline { 2 - 5 }
& Y & - 2 & 3 & 4 \\
\cline { 2 - 5 }
& Z & - 1 & 4 & 8 \\
\cline { 2 - 5 }
\end{tabular}
\end{center}
\begin{center}
\begin{tabular}{ c c | c | c | c }
\multicolumn{2}{c|}{\begin{tabular}{ c }
Points won \\
by Mia \\
\end{tabular}} & \multicolumn{3}{|c}{Mia} \\
& X & Y & Z & \\
\hline
\multirow{2}{*}{Li} & X & 4 & & \\
\cline { 2 - 5 }
& Y & 11 & & 5 \\
\cline { 2 - 5 }
& Z & 10 & 5 & 1 \\
\cline { 2 - 5 }
\end{tabular}
\end{center}
The game can be converted into a zero-sum game, this means that the total number of points won by Li and Mia is the same for each combination of strategies.\\
(a) (i) Complete the table in the Printed Answer Booklet to show the points won by Mia.\\
(ii) Convert the game into a zero-sum game, giving the pay-offs for Li .\\
(b) Use dominance to reduce the pay-off matrix for the game to a $2 \times 2$ table. You do not need to explain the dominance.
Mia knows that Li will choose his play-safe strategy.\\
(c) Determine which strategy Mia should choose to maximise her points.
5 A linear programming problem is formulated as below.
Maximise $\quad \mathrm { P } = 4 \mathrm { x } - \mathrm { y }$\\
subject to $2 x + 3 y \geqslant 12$\\
$x + y \leqslant 10$\\
$5 x + 2 y \leqslant 30$\\
$x \geqslant 0 , y \geqslant 0$\\
(a) (i) Identify the feasible region by representing the constraints graphically and shading the regions where the inequalities are not satisfied.\\
(ii) Hence determine the maximum value of the objective.
The constraint $x + y \leqslant 10$ is changed to $x + y \leqslant k$, the other constraints are unchanged.\\
(b) Determine, algebraically, the value of $k$ for which the maximum value of $P$ is 3 .
Do not draw on the graph from part (a) and do not use the spare grid.\\
(c) Determine, algebraically, the other value of $k$ for which there is a (non-optimal) vertex of the feasible region at which $P = 3$.\\
Do not draw on the graph from part (a) and do not use the spare grid.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete AS 2021 Q5 [11]}}