OCR Further Discrete AS (Further Discrete AS) 2021 November

1 A set consists of five distinct non-integer values, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E . The set is partitioned into non-empty subsets and there are at least two subsets in each partition.

1. Show that there are 15 different partitions into two subsets.
2. Show that there are 25 different partitions into three subsets.
3. Calculate the total number of different partitions. The numbers 12, 24, 36, 48, 60, 72, 84 and 96 are marked on a number line. The number line is then cut into pieces by making cuts at \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E , where \(0 < \mathrm { A } < \mathrm { B } < \mathrm { C } < \mathrm { D } < \mathrm { E } < 100\).
4. Explain why there must be at least one piece with two or more of the numbers 12, 24, 36, 48, 60, 72, 84 and 96.

2 Seven items need to be packed into bins. Each bin has capacity 30 kg . The sizes of the items, in kg, in the order that they are received, are as follows.
12
23
15
18
8
7
5

1. Find the packing that results using each of these algorithms.
   1. The next-fit method
   2. The first-fit method
   3. The first-fit decreasing method
2. 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.
3. 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.

1. 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 .
2. Complete the copy of the table in the Printed Answer Booklet.
3. Use your table from part (b) to construct a minimum spanning tree for the complete graph on the six vertices A to F .
   • Write down the total length of the minimum spanning tree.
   • List which arcs of the original network correspond to the arcs used in your minimum spanning tree.
   Beth starts from junction B and travels through every junction, including X and Y . Her route has length 5.1 km .
4. Write down the junctions in the order that Beth visited them. Do not draw on your answer from part (c).

5

1. Find the packing that results using each of these algorithms.
   1. The next-fit method
   2. The first-fit method
   3. The first-fit decreasing method
2. 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.
3. 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.
4. 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 .
5. Complete the copy of the table in the Printed Answer Booklet.
6. Use your table from part (b) to construct a minimum spanning tree for the complete graph on the six vertices A to F .
   • Write down the total length of the minimum spanning tree.
   • List which arcs of the original network correspond to the arcs used in your minimum spanning tree.
   Beth starts from junction B and travels through every junction, including X and Y . Her route has length 5.1 km .
7. 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. Question 18 1 marks View details 18 8 7 5 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 . Write down the total length of the minimum spanning tree. List which arcs of the original network correspond to the arcs used in your minimum spanning tree. 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. 6 Sarah is having some work done on her garden. The table below shows the activities involved, their durations and their immediate predecessors. These durations and immediate predecessors are known to be correct. Activity Immediate predecessors Duration (hours) A Clear site - 4 B Mark out new design A 1 C Buy materials, turf, plants and trees - 3 D Lay paths B, C 1 E Build patio B, C 2 F Plant trees D 1 G Lay turf D, E 1 H Finish planting F, G 1 Use a suitable model to determine the following. The minimum time in which the work can be completed The activities with zero float [0pt] (ii) State one practical issue that could affect the minimum completion time in part (a)(i). [1] Sarah needs the work to be completed as quickly as possible. There will be at least one activity happening at all times, but it may not always be possible to do all the activities that are needed at the same time. Determine the earliest and latest times at which building the patio (activity E) could start. There needs to be a 2-hour break after laying the paths (activity D). During this time other activities that do not depend on activity D can still take place. Describe how you would adapt your model to incorporate the 2-hour break.