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

1 Which one of the following sets forms a group under the given binary operation?
Tick ( ✓ ) one box.

2 A student is trying to find the solution to the travelling salesperson problem for a network. They correctly find two lower bounds for the solution: 15 and 19 They also correctly find two upper bounds for the solution: 48 and 51 Based on the above information only, which of the following pairs give the best lower bound and best upper bound for the solution of this problem? Tick ( ✓ ) one box. The simple-connected graph \(G\) has the adjacency matrix Which one of the following statements about \(G\) is true?
Tick ( ✓ ) one box.
\(G\) is a tree □
\(G\) is complete □
\(G\) is Eulerian □ G is planar □

4 Daniel and Jackson play a zero-sum game. The game is represented by the following pay-off matrix for Daniel. Neither player has any strategies which can be ignored due to dominance. 4

1. Prove that the game does not have a stable solution.
   Fully justify your answer.
   4
2. Determine the play-safe strategy for each player. Play-safe strategy for Daniel \(\_\_\_\_\) Play-safe strategy for Jackson \(\_\_\_\_\)

5

1. 1. Determine the electrical connections that should be installed.
      5
2. (ii) Find the minimum possible total time needed to install the required electrical connections.
   5
3. Following the installation of the electrical connections, some of the car parks have an indirect connection to the stadium's main electricity power supply. Give one limitation of this installation.

6
A company delivers parcels to houses in a village, using a van. The network below shows the roads in the village. Each node represents a road junction and the weight of each arc represents the length, in miles, of the road between the junctions.
\includegraphics[max width=\textwidth, alt={}, center]{8d4db82a-0daf-487a-a6eb-be3ce8e59141-08_1208_1193_502_407} The total length of all of the roads in the village is 31.4 miles. On one particular day, the driver is due to make deliveries to at least one house on each road, so the van must travel along each road at least once. However, the driver has forgotten to add fuel to the van and it only has 4.5 litres of fuel to use to make its deliveries. The van uses, on average, 1 litre of fuel to travel 7.8 miles along the roads of this village. Whilst making each delivery, the driver turns off the van's engine so it does not use any fuel. Determine whether the van has enough fuel for the driver to make all of the deliveries to houses on each road of the village, starting and finishing at the same junction. Fully justify your answer.
\includegraphics[max width=\textwidth, alt={}, center]{8d4db82a-0daf-487a-a6eb-be3ce8e59141-09_2489_1778_175_107}

7

1. By considering associativity, show that the set of integers does not form a group under the binary operation of subtraction. Fully justify your answer.
   7
2. The group G is formed by the set $$\{ 1,7,8,11,12,18 \}$$ under the operation of multiplication modulo 19 7
3. 1. Complete the Cayley table for \(G\)

      \({ } ^ { \times } 19\)	1	7	8	11	12	18
      1	1	7	8	11	12	18
      7	7	11
      8	8		7
      11	11			7
      12	12				11
      18	18					1

      7
4. (ii) State the inverse of 11 in \(G\)
   7
5. 1. State, with a reason, the possible orders of the proper subgroups of \(G\) 7
6. (ii) Find all the proper subgroups of \(G\)
   Give your answers in the form \(\left( \langle g \rangle , \mathrm { x } _ { 19 } \right)\) where \(g \in G\)
   7
7. (iii) The group \(H\) is such that \(G \cong H\) State a possible name for \(H\)

8
Figure 1 shows a network of water pipes. The number on each arc represents the upper capacity for each pipe in litres per second. The numbers in the circles represent an initial feasible flow of 103 litres per second. \begin{figure}[h] \end{figure} 8

1. On Figure 1 above, add a supersource \(S\) and a supersink \(T\) to the network. 8
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 opposite page, in your solution.

   Augmenting Path	Extra Flow

   Maximum Flow \(\_\_\_\_\) litres per second \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{8d4db82a-0daf-487a-a6eb-be3ce8e59141-13_960_1074_315_466}
   \end{figure} 8
3. While the flow through the network is at its maximum value, the pipe EG develops a leak. To repair the leak, an engineer turns off the flow of water through EG
   The engineer claims that the maximum flow of water through the network will reduce by 31 litres per second. Comment on the validity of the engineer's claim.

9 Janet and Samantha play a zero-sum game. The game is represented by the following pay-off matrix for Janet. \begin{table}[h] \end{table} \(\mathbf { 9 }\) (a) Explain why Janet should never play strategy \(\mathbf { J } _ { \mathbf { 4 } }\) 9 (b) Janet wants to maximise her winnings from the game.
She defines the following variables.
\(p _ { 1 } =\) the probability of Janet playing strategy \(\mathbf { J } _ { \mathbf { 1 } }\)
\(p _ { 2 } =\) the probability of Janet playing strategy \(\mathbf { J } _ { 2 }\)
\(p _ { 3 } =\) the probability of Janet playing strategy \(\mathbf { J } _ { \mathbf { 3 } }\)
\(v =\) the value of the game for Janet
Janet then formulates her situation as the following linear programming problem. $$\begin{array} { l l } \text { Maximise } & P = v
\text { subject to } & 2 p _ { 1 } + 5 p _ { 2 } + 4 p _ { 3 } \geq v
& 7 p _ { 1 } + 5 p _ { 2 } + 3 p _ { 3 } \geq v
& 6 p _ { 1 } + p _ { 2 } + 8 p _ { 3 } \geq v
\text { and } & p _ { 1 } + p _ { 2 } + p _ { 3 } \leq 1
& p _ { 1 } , p _ { 2 } , p _ { 3 } \geq 0 \end{array}$$ 9 (b) (i) Complete the initial Simplex tableau for Janet's situation in the grid below. Find the probability of Janet playing strategy \(\mathbf { J } _ { \mathbf { 3 } }\) when she is playing to maximise her winnings from the game.
\includegraphics[max width=\textwidth, alt={}, center]{8d4db82a-0daf-487a-a6eb-be3ce8e59141-17_2491_1755_173_123} A project is undertaken by Higton Engineering Ltd. The project is broken down into 11 separate activities \(A , B , \ldots , K\)
Figure 3 below shows a completed activity network for the project, along with the earliest start time, duration, latest finish time and the number of workers required for each activity. All times and durations are given in days. \begin{figure}[h] \end{figure}

10

1. Write down the critical path. 10
2. Using Figure 4 below, draw a resource histogram for the project to show how the project can be completed in the minimum possible time. Assume that each activity is to start as early as possible. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{8d4db82a-0daf-487a-a6eb-be3ce8e59141-19_760_1707_568_153}
   \end{figure} 10
3. Higton Engineering Ltd only has four workers available to work on the project. Find the minimum completion time for the project. Use Figure 5 below in your answer. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{8d4db82a-0daf-487a-a6eb-be3ce8e59141-19_510_1703_1786_155}
   \end{figure} Minimum completion time \(\_\_\_\_\)
   \includegraphics[max width=\textwidth, alt={}, center]{8d4db82a-0daf-487a-a6eb-be3ce8e59141-20_2491_1755_173_123} Additional page, if required.
   Write the question numbers in the left-hand margin. number
   .....
   \section*{Additional page, if required. Write the question numbers in the left-hand margin.
   \includegraphics[max width=\textwidth, alt={}]{8d4db82a-0daf-487a-a6eb-be3ce8e59141-22_67_195_233_644}} □ - box box \section*{Additional page, if required. Write the question numbers in the left-hand margin.}
   \includegraphics[max width=\textwidth, alt={}]{8d4db82a-0daf-487a-a6eb-be3ce8e59141-24_2484_1748_178_130}