OCR Further Discrete (Further Discrete) 2023 June

1 The table below shows the activities involved in a project together with the immediate predecessors and the duration of each activity.

1. Model the project using an activity network.
2. Determine the minimum project completion time. The start of activity C is delayed by 2 hours.
3. Determine the minimum project completion time with this delay.

2 A graph is shown below.
\includegraphics[max width=\textwidth, alt={}, center]{c4755464-aa15-4720-8f33-5eb7169f4a20-2_522_810_1637_246}

1. Write down a cycle through all six vertices.
2. Write down a continuous route that uses every arc exactly once.
3. Use Kuratowski's theorem to show that the graph is not planar.
4. Show that the graph has thickness 2 .

3 An initial simplex tableau is given below.

1. Carry out two iterations of the simplex algorithm, choosing the first pivot from the \(x\) column. After three iterations the resulting tableau is as follows.

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	RHS
   1	3	- 1	0	1	0	20
   0	5	- 4	1	1	0	20
   0	2	- 1	0	0	1	6

2. State the values of \(P , x , y , z , s\) and \(t\) that result from these three iterations.
3. Explain why no further iterations are possible. The initial simplex tableau is changed to the following, where \(k\) is a positive real value.

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	RHS
   1	2	- 3	1	0	0	0
   0	5	\(k\)	1	1	0	20
   0	2	- 1	0	0	1	6

   After one iteration of the simplex algorithm the value of \(P\) is 500 .
4. Deduce the value of \(k\).

4 The first 20 consecutive positive integers include the 8 prime numbers \(2,3,5,7,11,13,17\) and 19. Emma randomly chooses 5 distinct numbers from the first 20 consecutive positive integers. The order in which Emma chooses the numbers does not matter.

1. Calculate the number of possibilities in which Emma's 5 numbers include exactly 2 prime numbers and 3 non-prime numbers.
2. Calculate the number of possibilities in which Emma's 5 numbers include at least 2 prime numbers. The pairs \(\{ 3,13 \}\) and \(\{ 7,17 \}\) each consist of numbers with a difference of exactly 10 .
3. Calculate the number of possibilities in which Emma's 5 numbers include at least one pair of prime numbers in which the difference between them is exactly 10 . A new set of 20 consecutive positive integers, each with at least two digits, is chosen. This set of 20 numbers contains 5 prime numbers.
4. Use the pigeonhole principle to show that there is at least one pair of these prime numbers for which the difference between them is exactly 10 .

5 A list of 8 values is given below. The list is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.

1. Carry out the first two passes of the sort. A different list of 8 values is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
2. 1. State the maximum number of passes that could be required.
   2. Find the minimum number of passes that could be required. The run-time for quick sort could be measured by counting the number of comparisons used. In the worst case, the run time for quick sort is \(\mathrm { O } \left( n ^ { 2 } \right)\). A computer takes at most 0.03 seconds to sort a list of 100 values into increasing order using quick sort.
3. Calculate an estimate for the time taken, in the worst case, to sort a list of 500 values using quick sort. A list of \(n\) values (where \(n > 10\) ) is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.
4. Explain why, in the best case, \(n - 3\) comparisons are used in the second pass.

6 A graph is shown in Fig. 1.1.
The graph is weighted to form the network represented by the weighted matrix in Fig. 1.2. The weights represent distances in km.
A dash (-) means that there is no direct arc between that pair of vertices. \begin{figure}[h] \end{figure} \begin{table}[h] \end{table} The shortest path from D to F has total weight 6.

1. Write down a path from D to F of total weight 6. The total weight of the 12 arcs in the network is 56.
2. Use the route inspection algorithm to calculate the total weight of the least weight route that covers every arc at least once, starting at vertex A.
3. Determine the total weight of the least weight route that covers every arc at least once, starting at vertex B but finishing at any vertex. Sasha wants to find a continuous route through every vertex, starting and finishing at vertex A, with the least total weight.
4. 1. Use an appropriate algorithm to find a lower bound for the total weight of Sasha's route.
   2. Use the Nearest Neighbour Algorithm, starting at vertex A, to find an upper bound for the total weight of Sasha's route. Sasha decides to use the route \(A - B - F - E - C - D - A\).
5. Comment on the suitability of this route as a solution to Sasha's problem.

7 Player 1 and player 2 are playing a two-person zero-sum game.
In each round of the game the players each choose a strategy and simultaneously reveal their choice. The number of points won in each round by player 1 for each combination of strategies is shown in the table below. Each player is trying to maximise the number of points that they win.
Player 2 Player 1

1. 1. Determine play-safe strategies for each player.
   2. Show that the game is not stable.
2. Show that the number of strategies available to player 1 cannot be reduced by dominance. You must make it clear which values are being compared. Player 1 intends to make a random choice between strategies \(\mathrm { X } , \mathrm { Y } , \mathrm { Z }\), choosing strategy X with probability \(x\), strategy Y with probability \(y\) and strategy Z with probability \(z\).
   Player 1 formulates the following LP problem so they can find the optimal values of \(x , y\) and \(z\) using the simplex algorithm. Maximise \(M = m - 4\)
   subject to \(m \leqslant 6 x + 4 y + 2 z\) $$\begin{aligned} & m \leqslant x + 5 y + 6 z
   & m \leqslant 7 y + 8 z
   & x + y + z \leqslant 1 \end{aligned}$$ and \(m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)
3. Explain how the inequality \(m \leqslant 6 x + 4 y + 2 z\) was formed. The problem is solved by running the simplex algorithm on a computer.
   The printout gives a solution in which \(\mathrm { x } + \mathrm { y } = 1\).
   This means that the LP problem can be reduced to the following formulation.
   Maximise \(M = m - 4\)
   subject to \(m \leqslant 4 + 2 x\)
   \(\mathrm { m } \leqslant 5 - 4 \mathrm { x }\)
   \(m \leqslant 7 - 7 x\)
   and \(m \geqslant 0 , x \geqslant 0\)
4. Solve this problem to find the optimal values of \(x , y\) and \(z\) and the corresponding value of the game to player 1.