AQA Further Paper 3 Discrete (Further Paper 3 Discrete) 2022 June

The graph \(G\) has a subgraph isomorphic to \(K_5\), the complete graph with 5 vertices. Which of the following statements about \(G\) must be true? Tick \((\checkmark)\) one box. [1 mark] \(G\) is not connected \(G\) is not Hamiltonian \(G\) is not planar \(G\) is not simple

Graph \(A\) is a connected planar graph with 12 vertices, 18 edges and \(n\) faces. Find the value of \(n\) Circle your answer. [1 mark] 4 8 28 32

A company undertakes a project which consists of 12 activities, \(A\), \(B\), \(C\), \(\ldots\), \(L\) Each activity requires one worker. The resource histogram below shows the duration of each activity. Each activity begins at its earliest start time. The path \(ADGJL\) is critical. \includegraphics{figure_1} The company only has two workers available to work on the project. Which of the following could be a correctly levelled histogram? Tick \((\checkmark)\) one box. [1 mark] \includegraphics{figure_2} \includegraphics{figure_3} \includegraphics{figure_4} \includegraphics{figure_5}

Ben and Jadzia play a zero-sum game. The game is represented by the following pay-off matrix for Ben.

	Jadzia
Strategy	X	Y	Z
A	-3	2	3
Ben B	6	0	-4
C	7	-1	1
D	6	-2	1

1. State, with a reason, which strategy Ben should never play. [1 mark]
2. Determine whether or not the game has a stable solution. Fully justify your answer. [3 marks]
3. Ben knows that Jadzia will always play her play-safe strategy. Explain how Ben can maximise his expected pay-off. [2 marks]

A council wants to convert all of the street lighting in a village to use LED lighting. The network below shows each street in the village. Each node represents a junction and the weight of each arc represents the length, in metres, of the street. The street lights are only positioned on one side of each street in the village. \includegraphics{figure_6} The total length of all of the streets in the village is 2250 metres. In order to determine the total number of street lights in the village, a council worker is required to walk along every street in the village at least once, starting and finishing at the same junction. The shortest possible distance the council worker can walk in order to determine the total number of street lights in the village is \(x\) metres.

1. Find the value of \(x\) Fully justify your answer. [4 marks]
2. A new council regulation requires that the mean distance along a street between adjacent LED street lights in a village be less than 25 metres. The council worker counted 91 different street lights on their journey around the village. Determine whether or not the village will meet the new council regulation. [2 marks]

Bill Durrh Ltd undertake a construction project. The activity network for the project is shown below. The duration of each activity is given in weeks. \includegraphics{figure_7}

1. 1. Find the earliest start time and the latest finish time for each activity and show these values on the activity network above. [3 marks]
   2. Identify all of the critical activities. [1 mark]
2. The manager of Bill Durrh Ltd recruits some additional temporary workers in order to reduce the duration of one activity by 2 weeks. The manager wants to reduce the minimum completion time of the project by the largest amount. State, with a reason, which activity the manager should choose. [2 marks]

The group \(G\) has binary operation \(*\) and order \(p\), where \(p\) is a prime number.

1. Determine the number of distinct subgroups of \(G\) Fully justify your answer. [2 marks]
2. \(G\) contains an element \(g\) which has period \(p\)
   1. State the general name given to elements such as \(g\) [1 mark]
   2. State the name of a group that is isomorphic to \(G\) [1 mark]
3. \(G\) contains an element \(g^r\), where \(r < p\) Find, in terms of \(g\), \(r\) and \(p\), the inverse of \(g^r\) [2 marks]
4. In the case when \(p = 5\) and the binary operation \(*\) represents addition modulo 5, \(G\) contains the elements 0, 1, 2, 3 and 4
   1. Explain why \(G\) is closed. [1 mark]
   2. Complete the Cayley table for \((G, *)\) [1 mark]

      \(*\)

Figure 1 shows a network of gas pipes. The numbers on each arc represent the lower and upper capacity for each pipe in \(\text{m}^3 \text{s}^{-1}\) The numbers in the circles represent an initial feasible flow of 73 \(\text{m}^3 \text{s}^{-1}\) through the network. \includegraphics{figure_8}

1. On Figure 1 above, add a supersink \(T\) to the network. [2 marks]
2. Using flow augmentation, find the maximum flow through the network. You must indicate any flow augmenting paths clearly in the table below. You may use Figure 2, on the page opposite, in your solution. [4 marks]

   Augmenting Path	Flow

   Maximum flow \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
3. Prove that the flow found in part (b) is the maximum flow through the network. [2 marks]
4. A trainee engineer claims that increasing the upper capacity of the pipe \(AG\) will increase the maximum flow through the network, as the flow through this pipe cannot currently be increased. Comment on the validity of the trainee's claim. [2 marks]

The binary operation \(\oplus\) acts on the positive integers \(x\) and \(y\) such that $$x \oplus y = x + y + 8 \pmod{k^2 - 16k + 74}$$ where \(k\) is a positive integer.

1. 1. Show that \(\oplus\) is commutative. [1 mark]
   2. Determine whether or not \(\oplus\) is associative. Fully justify your answer. [2 marks]
2. Find the values of \(k\) for which 3 is an identity element for the set of positive integers under \(\oplus\) [3 marks]

Kira and Julian play a zero-sum game that does not have a stable solution. Kira has three strategies to choose from: \(\mathbf{K_1}\), \(\mathbf{K_2}\) and \(\mathbf{K_3}\) To determine her optimal mixed strategy, Kira begins by defining the following variables: \(v =\) value of the game for Kira \(p_1 =\) probability of Kira playing strategy \(\mathbf{K_1}\) \(p_2 =\) probability of Kira playing strategy \(\mathbf{K_2}\) \(p_3 =\) probability of Kira playing strategy \(\mathbf{K_3}\) Kira then formulates the following linear programming problem. Maximise \(v\) subject to \(7p_1 + p_2 + 8p_3 \geq v\) \(3p_1 + 7p_2 + 2p_3 \geq v\) \(9p_1 + 2p_2 + 4p_3 \geq v\) and \(p_1 + p_2 + p_3 \leq 1\) \(p_1, p_2, p_3 \geq 0\)

1. 1. Explain why the condition \(p_1 + p_2 + p_3 \leq 1\) is necessary in Kira's linear programming problem. [1 mark]
   2. Explain why the condition \(p_1, p_2, p_3 \geq 0\) is necessary in Kira's linear programming problem. [1 mark]
2. Julian has three strategies to choose from: \(\mathbf{J_1}\), \(\mathbf{J_2}\) and \(\mathbf{J_3}\) Complete the following pay-off matrix which represents the game for Kira. [3 marks]

   	Julian
   Strategy	\(\mathbf{J_1}\)	\(\mathbf{J_2}\)	\(\mathbf{J_3}\)
   \(\mathbf{K_1}\)	7
   Kira \(\mathbf{K_2}\)
   \(\mathbf{K_3}\)