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

1 The simple-connected graph \(G\) is shown below.
\includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-02_271_515_632_762} The graph \(G\) has \(n\) faces. State the value of \(n\) Circle your answer. 2345

2 Jonathan and Hoshi play a zero-sum game.
The game is represented by the following pay-off matrix for Jonathan. The game does not have a stable solution.
Which strategy should Jonathan never play?
Circle your answer.
[0pt] [1 mark]
\(\mathbf { J } _ { \mathbf { 1 } }\)
\(\mathbf { J } _ { \mathbf { 2 } }\)
\(\mathbf { J } _ { \mathbf { 3 } }\)
\(\mathbf { J } _ { \mathbf { 4 } }\)

3 A student is solving a maximising linear programming problem. The graph below shows the constraints, feasible region and objective line for the student's linear programming problem.
\includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-03_1248_1184_502_427} Which vertex is the optimal vertex? Circle your answer.
\(A\)
B
C
D

4 The network below represents a system of water pipes in a geothermal power station. The numbers on each arc represent the lower and upper capacity for each pipe in gallons per second.
\includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-04_837_1413_493_312} The water is taken from a nearby river at node \(A\)
The water is then pumped through the system of pipes and passes through one of three treatment facilities at nodes \(H , I\) and \(J\) before returning to the river. 4

1. The senior management at the power station want all of the water to undergo a final quality control check at a new facility before it returns to the river. Using the language of networks, explain how the network above could be modified to include the new facility. 4
2. Find the value of the cut \(\{ A , B , C , D , E \} \{ F , G , H , I , J \}\) 4
3. Tim, a trainee engineer at the power station, correctly calculates the value of the cut \(\{ A , B , C , D , E , F \} \{ G , H , I , J \}\) to be 106 gallons per second. Tim then claims that the maximum flow through the network of pipes is 106 gallons per second. Comment on the validity of Tim's claim.

5 A student is solving the following linear programming problem. $$\begin{array} { l r } \text { Minimise } & Q = - 4 x - 3 y
\text { subject to } & x + y \leq 520
& 2 x - 3 y \leq 570
\text { and } & x \geq 0 , y \geq 0 \end{array}$$ 5

1. The student wants to use the simplex algorithm to solve the linear programming problem. They modify the linear programming problem by introducing the objective function $$P = 4 x + 3 y$$ and the slack variables \(r\) and \(s\) State one further modification that must be made to the linear programming problem so that it can be solved using the simplex algorithm. 5
2. 1. Complete the initial simplex tableau for the modified linear programming problem.
      [0pt] [2 marks]

      \(P\)	\(x\)	\(y\)	\(r\)	\(S\)	value

      5
3. (ii) Hence, perform one iteration of the simplex algorithm.

   \(P\)	\(x\)	\(y\)	\(r\)	\(s\)	value

   5
4. The student performs one further iteration of the simplex algorithm, which results in the following correct simplex tableau.

   \(P\)	\(x\)	\(y\)	\(r\)	\(s\)	value
   1	0	0	\(\frac { 18 } { 5 }\)	\(\frac { 1 } { 5 }\)	1986
   0	0	1	\(\frac { 2 } { 5 }\)	\(- \frac { 1 } { 5 }\)	94
   0	1	0	\(\frac { 3 } { 5 }\)	\(\frac { 1 } { 5 }\)	426

   5
5. 1. Explain how the student can tell that the optimal solution to the modified linear programming problem can be determined from the above simplex tableau.
      5
6. (ii) Find the optimal solution of the original linear programming problem.

6 A council wants to grit all of the roads on a housing estate. The network shows the roads on a housing estate. Each node represents a junction between two or more roads and the weight of each arc represents the length, in metres, of the road.
\includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-08_1145_1458_539_292} The total length of all of the roads on the housing estate is 9175 metres.
In order to grit all of the roads, the council requires a gritter truck to travel along each road at least once. The gritter truck starts and finishes at the same junction. 6

1. The gritter truck starts gritting the roads at 7:00 pm and moves with an average speed of 5 metres per second during its journey. Find the earliest time for the gritter truck to have gritted each road at least once and arrived back at the junction it started from, giving your answer to the nearest minute. Fully justify your answer.
   [0pt] [6 marks]

   6	Explain how a refinement to the council's requirement, that the gritter truck must start and finish at the same junction, could reduce the time taken to grit all of the roads at least once. [2 marks] \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\)

   The planning involves producing an activity network for the project, which is shown in Figure 1 below. The duration of each activity is given in weeks. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-10_965_1600_559_221}
   \end{figure}

7

1. 1. Find the earliest start time and the latest finish time for each activity and write these values on the activity network in Figure 1 7
2. (ii) Write down the critical path. 7
3. On Figure 2 below, draw a cascade diagram (Gantt chart) for the planned building project, assuming that each activity starts as early as possible. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-11_1127_1641_539_201}
   \end{figure} 7
4. During further planning of the building project, Nova Merit Construction find that activity \(F\) is not necessary and they remove it from the project. Explain the effect removing activity \(F\) has on the minimum completion time of the project.

8 The graph \(G\) is shown below.
\includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-12_301_688_351_676} 8

1. 1. State, with a reason, whether or not \(G\) is simple. 8
2. (ii) A student states that \(G\) is Eulerian.
   Explain why the student is correct. 8
3. The graph \(H\) has 8 vertices with degrees 2, 2, 4, 4, 4, 4, 4 and 4 Comment on whether \(H\) is isomorphic to \(G\)
   8
4. The formula \(v - e + f = 2\), where
   \(v =\) number of vertices
   \(e =\) number of edges
   \(f =\) number of faces
   can be used with graphs which satisfy certain conditions. Prove that \(G\) does not satisfy the conditions for the above formula to apply.

9 The group \(\left( C , + _ { 4 } \right)\) contains the elements \(0,1,2\) and 3 9

1. 1. Show that \(C\) is a cyclic group.
      9
2. (ii) State the group of symmetries of a regular polygon that is isomorphic to \(C\)
   9
3. The group ( \(V , \otimes\) ) contains the elements (1, 1), (1, -1), (-1, 1) and (-1, -1) The binary operation \(\otimes\) between elements of \(V\) is defined by $$( a , b ) \otimes ( c , d ) = ( a \times c , b \times d )$$ 9
4. 1. Find the element in \(V\) that is the inverse of \(( - 1,1 )\)
      Fully justify your answer.
      [0pt] [2 marks]
      9
5. (ii) Determine, with a reason, whether or not \(C \cong V\)
   \(\mathbf { 9 }\) (c) The group \(G\) has order 16
   Rachel claims that as \(1,2,4,8\) and 16 are the only factors of 16 then, by Lagrange's theorem, the group \(G\) will have exactly 5 distinct subgroups, including the trivial subgroup and \(G\) itself. Comment on the validity of Rachel's claim.
   \includegraphics[max width=\textwidth, alt={}, center]{5ff6e3bb-6392-49cf-b64d-23bc595cd92e-16_2493_1721_214_150}