OCR Further Discrete (Further Discrete) 2022 June

1 Four children, A, B, C and D, discuss how many of the 23 birthday parties held by their classmates they had gone to. Each party was attended by at least one of the four children. The results are shown in the Venn diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-2_387_618_589_246}

1. Construct a complete graph \(\mathrm { K } _ { 4 }\), with vertices representing the four children and arcs weighted to show the number of parties each pair of children went to.
2. State a piece of information about the number of parties the children went to that is shown in the Venn diagram but is not shown in the graph. A fifth child, E, also went to some of the 23 parties shown in the Venn diagram.
   Every party that E went to was also attended by at least one of \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D .
   • A was at 8 of these parties, B at 7, C at 5 and D at 8 .
   • These include 5 parties attended by both A and \(\mathrm { B } , 2\) by both A and \(\mathrm { C } , 3\) by both A and \(\mathrm { D } , 3\) by both B and D and 4 by both C and D .
   • These include 1 party attended by \(\mathrm { A } , \mathrm { B }\) and D and 1 party attended by \(\mathrm { A } , \mathrm { C }\) and D .
   • Use the inclusion-exclusion principle to determine the number of parties that E went to.

2 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.
3. Calculate the total float for each non-critical activity.

3 A para relay team of 4 swimmers needs to be chosen from a group of 7 swimmers.

1. How many ways are there to choose 4 swimmers from 7? There are no restrictions on how many men and how many women are in the team. The group of 7 swimmers consists of 5 men and 2 women.
2. How many ways are there to choose a team with more men than women? The physical impairment of each swimmer is given a score.
   The scores for the swimmers are
   \(\begin{array} { l l l l l l l } 3 & 4 & 4 & 6 & 7 & 8 & 9 \end{array}\) The total score for the team must be 20 or less.
3. How many different valid teams are possible? The order of the swimmers in the team is now taken into consideration.
4. In total, how many different arrangements are there of valid teams?
5. In how many of these valid teams are the scores of the swimmers in increasing order? For example, 3, 4, 4, 8 but not 4, 3, 4, 8 .

4 A connected graph is shown below.
\includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-4_442_954_296_246}

1. Write down a path through exactly 7 of the vertices.
2. Write down a cycle through exactly 6 of the vertices.
3. Explain why Ore's theorem cannot be used to decide whether or not this graph is Hamiltonian.
4. Prove that the graph is not Hamiltonian. The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, (1) and (2). STEP 1 Choose a vertex and assign it colour (1).
   STEP 2 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (2) to each vertex that is adjacent to a vertex with colour (1).
   STEP 3 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (1) to each vertex that is adjacent to a vertex with colour (2).
   STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.
   STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite, output the word "bipartite".
   Otherwise the graph is not bipartite, output the words "not bipartite".
5. Use this algorithm, starting at vertex A, to determine whether the graph is bipartite, or not. [2
6. Explain what Kuratowski's theorem tells you about the graph.
7. Show that the graph has thickness 2 .

5 In each turn of a game between two players they simultaneously each choose a strategy and then calculate the points won using the table below. They are each trying to maximise the number of points that they win. In each cell the first value is the number of points won by player 1 and the second value is the number of points won by player 2 .

1. Find the play-safe strategy for each player.
2. Explain why player 2 would never choose strategy Z .
3. Find the Nash equilibrium solution(s) or show that there is no Nash equilibrium solution. Player 2 chooses strategy X with probability \(p\) and strategy Y with probability \(1 - p\). You are given that when player 1 chooses strategy A, the expected number of points won by each player is the same.
4. 1. Calculate the value of \(p\).
   2. Determine which player expects to win the greater number of points when player 1 chooses strategy B.

6 A linear programming problem is
Maximise \(\mathrm { P } = 2 \mathrm { x } - \mathrm { y }\)
subject to $$\begin{aligned} 3 x + y - 4 z & \leqslant 24
5 x - 3 z & \leqslant 60
- x + 2 y + 3 z & \leqslant 12 \end{aligned}$$ and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)

1. 1. Represent this problem as an initial simplex tableau.
   2. Carry out one iteration of the simplex algorithm. After two iterations the resulting tableau is

      \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	RHS
      1	0	\(\frac { 5 } { 11 }\)	0	\(- \frac { 6 } { 11 }\)	\(\frac { 8 } { 11 }\)	0	\(30 \frac { 6 } { 11 }\)
      0	1	\(- \frac { 3 } { 11 }\)	0	\(- \frac { 3 } { 11 }\)	\(\frac { 4 } { 11 }\)	0	\(15 \frac { 3 } { 11 }\)
      0	0	\(- \frac { 5 } { 11 }\)	1	\(- \frac { 5 } { 11 }\)	\(\frac { 3 } { 11 }\)	0	\(5 \frac { 5 } { 11 }\)
      0	0	\(\frac { 34 } { 11 }\)	0	\(\frac { 12 } { 11 }\)	\(- \frac { 5 } { 11 }\)	1	\(10 \frac { 10 } { 11 }\)

2. 1. Write down the basic variables after two iterations.
   2. Write down the exact values of the basic feasible solution for \(x , y\) and \(z\) after two iterations.
   3. State what you can deduce about the optimal value of the objective for the original problem. You are now given that, in addition to the constraints above, \(\mathrm { x } + \mathrm { y } + \mathrm { z } = 9\).
3. Use the additional constraint to rewrite the original constraints in terms of \(x\) and \(y\) but not \(z\).
4. Explain why the simplex algorithm cannot be applied to this new problem without some modification.

7 A building has 7 CCTV cameras, A to G, at the junctions of some of the corridors.
The cameras at the junctions and the lengths of the 11 corridors between them, in metres, are shown in the table below.

1. Model this information as a network.
2. Use an appropriate algorithm to calculate the minimum distance from A to each of the other vertices. The run-time of an algorithm for finding this minimum distance is proportional to the total number of comparisons used. For a network with \(n\) vertices, the worst case is when the algorithm is applied to a network based on the complete graph \(\mathrm { K } _ { n }\). In each pass
   • A vertex is made permanent and the temporary label at all adjacent vertices that are not yet permanent are updated. This uses 1 comparison for every such vertex (adjacent to the permanent label) that previously already had a temporary label.
   • The best temporary labels at all vertices that do not yet have permanent labels are then compared to determine the next vertex to become permanent. If there are \(k\) such vertices this involves \(k - 1\) comparisons.
   • By considering the number of comparisons of each type in each iteration, show that the algorithm uses a total of 6 comparisons when it is applied to a network based on the complete graph \(\mathrm { K } _ { 4 }\).
   You are given that the total number of comparisons used when the algorithm is applied to a network based on \(\mathrm { K } _ { n }\) is \(( n - 1 ) ( n - 2 )\). A computer takes 0.03 seconds to apply this algorithm on a network based on \(\mathrm { K } _ { 7 }\).
3. Calculate, to \(\mathbf { 1 }\) decimal place, how many seconds it will take the computer to apply the algorithm to a network based on \(\mathrm { K } _ { 70 }\). \section*{Question 7 continues on the next page} The manager wants to construct a tour (a closed route) that passes each camera.
4. 1. Find a lower bound for the length of this tour by initially deleting D .
   2. Find an upper bound for the length of this tour by using the nearest neighbour algorithm starting from D.
   3. Deduce the length of the shortest possible tour. Briefly explain your reasoning. \section*{END OF QUESTION PAPER}