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

1 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.
\(G\) is not connected
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-03_104_108_872_973}
\(G\) is not Hamiltonian
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-03_108_108_1005_973} G is not planar
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-03_108_108_1142_973}
\(G\) is not simple □

2 Graph \(A\) is a connected planar graph with 12 vertices, 18 edges and \(n\) faces.
Find the value of \(n\) Circle your answer. 4
8
28
32 Turn over for the next question

4
8
28
32 Turn over for the next question 3 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 \(A D G J L\) is critical. Number of workers
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-04_504_1145_719_548} 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. Number of workers
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-05_510_1145_502_459} Number of workers
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-05_515_1145_1059_459} Number of workers
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-05_517_1147_1619_459} Number of workers
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-05_517_1149_2179_458} 4 Ben and Jadzia play a zero-sum game. The game is represented by the following pay-off matrix for Ben. 4

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

5 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[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-08_1036_1514_616_264} 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. 5

1. Find the value of \(x\)
   Fully justify your answer.
   [0pt] [4 marks] 5
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.

6

1. 1. Find the earliest start time and the latest finish time for each activity and show these values on the activity network above. 6
2. (ii) Identify all of the critical activities. 6
3. 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.

8
28
32 Turn over for the next question 3 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 \(A D G J L\) is critical. Number of workers
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-04_504_1145_719_548} 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. Number of workers
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-05_510_1145_502_459} Number of workers
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-05_515_1145_1059_459} Number of workers
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-05_517_1147_1619_459} Number of workers
\includegraphics[max width=\textwidth, alt={}, center]{bcb1dd40-4e54-4ac7-a623-3a4b46e3ea9d-05_517_1149_2179_458} 4 Ben and Jadzia play a zero-sum game. The game is represented by the following pay-off matrix for Ben. 4

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

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

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

10 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. $$\begin{array} { l l } \text { Maximise } & v
\text { subject to } & 7 p _ { 1 } + p _ { 2 } + 8 p _ { 3 } \geq v
& 3 p _ { 1 } + 7 p _ { 2 } + 2 p _ { 3 } \geq v
& 9 p _ { 1 } + 2 p _ { 2 } + 4 p _ { 3 } \geq v \end{array}$$ and $$\begin{array} { r } p _ { 1 } + p _ { 2 } + p _ { 3 } \leq 1
p _ { 1 } , p _ { 2 } , p _ { 3 } \geq 0 \end{array}$$ 10

1. 1. Explain why the condition \(p _ { 1 } + p _ { 2 } + p _ { 3 } \leq 1\) is necessary in Kira's linear programming problem. 10
2. (ii) Explain why the condition \(p _ { 1 } , p _ { 2 } , p _ { 3 } \geq 0\) is necessary in Kira's linear programming problem. 10
3. 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.

   	Julian
   \cline { 2 - 5 }	Strategy	\(\mathbf { J } _ { 1 }\)	\(\mathbf { J } _ { 2 }\)	\(\mathbf { J } _ { 3 }\)
   \multirow{3}{*}{Kira}	\(\mathbf { K } _ { 1 }\)	7
   \cline { 2 - 5 }	\(\mathbf { K } _ { 2 }\)
   \cline { 2 - 5 }	\(\mathbf { K } _ { 3 }\)