OCR Further Discrete (Further Discrete) 2024 June

1 At the end of each year the workers at an office take part in a gift exchange.
Each worker randomly chooses the name of one other worker and buys a small gift for that person. Each worker's name is chosen by exactly one of the others.
A worker cannot choose their own name. In the first year there were four workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D .
There are 9 ways in which A, B, C and D can choose the names for the gift exchange. One of these is already given in the table in the Printed Answer Booklet.

1. Complete the table in the Printed Answer Booklet to show the remaining 8 ways in which the names can be chosen. During the second year, worker D left and was replaced with worker E.
   The organiser of the gift exchange wants to know whether it is possible for the event to happen for another 3 years (starting with the second year) with none of the workers choosing a name they have chosen before, assuming that there are no further changes in the workers.
2. Classify the organiser's problem as an existence, construction, enumeration or optimisation problem. After the second year, the organiser drew a graph showing who each worker chose in the first two years of the gift exchange.
   None of the workers chose the same name in the first and second years.
   The vertices of the graph represented the workers, A, B, C, D and E, and the arcs showed who had been chosen by each worker.
3. Explain why the graph must be a digraph.
4. State the number of arcs in the digraph that shows the choices for the first two years.
5. Assuming that the digraph created in part (d) is planar, use Euler's formula to calculate how many regions it has.

2 A linear programming problem is Maximise \(\mathrm { P } = 2 \mathrm { x } - \mathrm { y } + \mathrm { z }\)
subject to
\(3 x - 4 y - z \leqslant 30\)
\(x - y \leqslant 6\)
\(x - 3 y + 2 z \geqslant - 2\)
and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)

1. Complete the table in the Printed Answer Booklet to represent the problem as an initial simplex tableau.
2. Carry out one iteration of the simplex algorithm.
3. State the values of \(x , y\) and \(z\) that result from your iteration. After two iterations the resulting tableau is

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	RHS
   1	0	0	-2	0	2.5	0.5	16
   0	0	0	-2	1	-2.5	0.5	16
   0	1	0	-1	0	1.5	0.5	10
   0	0	1	-1	0	0.5	0.5	4

   The boundaries of the feasible region are planes, with edges each defined by two of \(x , y , z , s , t , u\) being zero.
   At each vertex of the feasible region there are three basic variables and three non-basic variables.
4. Interpret the second iteration geometrically by stating which edge of the feasible region is being moved along. As part of your geometrical interpretation, you should state the beginning vertex and end vertex of the second iteration.

3 Amir and Beth play a zero-sum game.
The table shows the pay-off for Amir for each combination of strategies, where these values are known. \begin{table}[h] \end{table} You are given that \(\mathrm { a } < 0 < \mathrm { b } < \mathrm { c }\).
Amir's play-safe strategy is R.

1. Determine the range of possible values of \(a\). Beth's play-safe strategy is Y.
2. Determine the range of possible values of \(b\).
3. Determine whether or not the game is stable.

4 A project is represented by the activity network below. The activity durations are given in hours.
\includegraphics[max width=\textwidth, alt={}, center]{f20391b2-e3c1-4021-9a87-47fd4ea7c490-5_346_1033_351_244}

1. By carrying out a forward pass, determine the minimum project completion time.
2. By carrying out a backward pass, determine the (total) float for each activity.
3. For each non-critical activity, determine the independent float and the interfering float.
4. Construct a cascade chart showing all the critical activities on one row and each non-critical activity on a separate row, starting at its earliest start time, and using dashed lines to indicate (total) float. You may not need to use all the grid. Each activity requires exactly one worker.
5. Construct a schedule to show how exactly two workers can complete the project as quickly as possible. You may not need to use all the grid. Issues with deliveries delay the earliest possible start of activity D by 3 hours.
6. Construct a schedule to show how exactly two workers can complete the project with this delay as quickly as possible. You may not need to use all the grid.

5

1. Write down a way in which the nearest neighbour method can fail to solve the problem of finding a least weight cycle through all the vertices of a network.
2. Explain why, when trying to find a least weight cycle through all the vertices of a network, an ad hoc method may be preferable to an algorithmic approach. The distance matrix below represents a network connecting six viewpoints \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F . The distance matrix shows the direct distances between each pair of viewpoints where a direct route exists.
   The distances are measured in km.
   A blank shows that there is no direct route between the two viewpoints.

   	A	B	C	D	E	F
   A		6		4
   B	6		5	2	9
   C		5		15	7	6
   D	4	2	15		5
   E		9	7	5
   F			6

3. Draw the network on the vertices given in the Printed Answer Booklet.
4. Apply the nearest neighbour method, starting from A. A hiker wants to travel between the six viewpoints, starting and finishing at A.
   The hiker must visit every viewpoint at least once, but may visit a viewpoint more than once.
5. Show that the hiker does not need to travel as far as 50 km .
6. Use an appropriate algorithm to find the shortest distance from F to each of the other viewpoints.
7. Complete the table in the Printed Answer Book to show the shortest distance between each pair of viewpoints.
8. Use your answer to part (g) to find a lower bound for the distance the hiker must travel by initially deleting vertex A.

6 Sasha is making three identical bead bracelets using amber, brown and red coloured beads. Sasha has 20 amber beads, 12 brown beads and 10 red beads. Each bracelet must use exactly 12 beads.
The profit from selling a bracelet is 6 pence for each amber bead used plus 2 pence for each brown bead used plus 3 pence for each red bead used. Sasha wants to maximise the total profit from selling the three bracelets.

1. Express Sasha's problem as a linear programming formulation in two variables \(a\) and \(b\), where \(a\) represents the number of amber beads in each bracelet and \(b\) represents the number of brown beads in each bracelet.
2. Determine how many beads of each colour will be used in each bracelet.
3. By listing all the feasible solutions, identify an aspect of the optimal solution, other than the profit, that is different from all the other feasible solutions. The beads that are not used in making the bracelets can be sold. The profit from selling each amber bead is \(k\) pence, where \(k\) is an integer, but nothing for each brown or red bead sold. All the previous constraints still apply. Instead of maximising the profit from the bracelets, Sasha wants to maximise the total profit from selling the bracelets and any left over beads. You are given that the optimal solution to the earlier problem does not maximise the total profit from selling the bracelets and any left over beads.
4. Determine the least possible value of Sasha’s maximum total profit.
5. Why might Sasha not achieve this maximum profit?