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

1 Deanna and Will play a zero-sum game.
The game is represented by the following pay-off matrix for Deanna. Which strategy is Deanna's play-safe strategy?
Circle your answer.
A
B
C
D

2 The graph \(D\) is shown in the diagram below.
\includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_115_150_1756_945} Which of the graphs below is a subdivision of \(D\) ?
Circle your answer.
\includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_218_154_2124_534}
\includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_208_150_2129_808}
\includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_208_154_2129_1082}
\includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-02_208_149_2129_1361}

3 The Simplex tableau below is optimal. 3

1. Deduce the range of values that \(k\) must satisfy.
   3
2. Write down the value of the variable \(s\) which corresponds to the optimal value of \(P\).

4 The connected planar graph \(P\) has the adjacency matrix 4

1. Draw \(P\) 4
2. Using Euler's formula for connected planar graphs, show that \(P\) has exactly 5 faces. 4
3. Ore's theorem states that a simple graph with \(n\) vertices is Hamiltonian if, for every pair of vertices \(X\) and \(Y\) which are not adjacent, $$\text { degree of } X + \text { degree of } Y \geq n$$ where \(n \geq 3\)
   Using Ore's theorem, prove that the graph \(P\) is Hamiltonian.
   Fully justify your answer.

5 The set \(S\) is defined as $$S = \{ A , B , C , D \}$$ where
\(A = \left[ \begin{array} { l l } 1 & 0
0 & 1 \end{array} \right] \quad B = \left[ \begin{array} { c c } 0 & - 1
1 & 0 \end{array} \right] \quad C = \left[ \begin{array} { c c } - 1 & 0
0 & - 1 \end{array} \right] \quad D = \left[ \begin{array} { c c } 0 & 1
- 1 & 0 \end{array} \right]\) The group \(G\) is formed by \(S\) under matrix multiplication.
The group \(H\) is defined as \(H = ( \langle \mathrm { i } \rangle , \times )\), where \(\mathrm { i } ^ { 2 } = - 1\)
5

1. 1. Prove that \(B\) is a generator of \(G\).
      Fully justify your answer.
      5
2. (ii) Show that \(G \cong H\).
   Fully justify your answer.
   5
3. 1. Explain why \(H\) has no subgroups of order 3
      Fully justify your answer.
      5
4. (ii) Find all of the subgroups of \(H\).

6 A council wants to monitor how long cars are being parked for in short-stay parking bays in a town centre. They employ a traffic warden to walk along the streets in the town centre and issue fines to drivers who park for longer than the stated time. The network below shows streets in the town centre which have short-stay parking bays. Each node represents a street corner and the weight of each arc represents the length, in metres, of the street. The short-stay parking bays are positioned along only one side of each street.
\includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-08_483_1108_733_466} The council assumes that the traffic warden will walk at an average speed of 4.8 kilometres per hour when not issuing fines. 6

1. To monitor all of the parking bays, the traffic warden needs to walk along every street in the town centre at least once, starting and finishing at the same street corner. Find the shortest possible time, to the nearest minute, it can take the traffic warden to monitor all of the parking bays. Fully justify your answer.
   6
2. Explain why the actual time for the traffic warden to walk along every street in the town centre at least once may be different to the value found in part (a).

7 Figure 1 shows a system of water pipes in a manufacturing complex. 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 38 litres of water per second. \begin{figure}[h] \end{figure} 7

1. 1. Calculate the value of the cut \(\{ S , A , B , C \} \{ D , E , F , G , H , T \}\). 7
2. (ii) Explain, in the context of the question, what can be deduced from your answer to part (a)(i). 7
3. 1. Using the initial feasible flow shown in Figure 1, indicate on Figure 2 potential increases and decreases in the flow along each arc. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{22f11ce2-8d07-4f51-9326-b578d1e454f9-11_997_1554_475_242}
      \end{figure} 7
4. (ii) Use flow augmentation on Figure 2 to find the maximum flow through the manufacturing complex. You must indicate any flow augmenting paths clearly in the table and modify the potential increases and decreases of the flow on Figure 2.

   Augmenting Path	Flow

   Maximum Flow \(=\) \(\_\_\_\_\) 7
5. The management of the manufacturing complex want to increase the maximum amount of water which can flow through the system of pipes. To do this they decide to upgrade one of the water pipes by replacing it with a larger capacity pipe. Explain which pipe should be upgraded.
   Deduce what effect this upgrade will have on the maximum amount of water which can flow through the system of pipes.
   \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-13_2488_1716_219_153}

8 A motor racing team is undertaking a project to build next season's racing car. The project is broken down into 12 separate activities \(A , B , \ldots , L\), as shown in the precedence table below. Each activity requires one member of the racing team. 8

1. 1. Complete the activity network for the project on Figure 3. 8
2. (ii) Find the earliest start time and the latest finish time for each activity and show these values on Figure 3. 8
3. Write down the critical path(s).
   \section*{Figure 3} Figure 3
   \includegraphics[max width=\textwidth, alt={}, center]{22f11ce2-8d07-4f51-9326-b578d1e454f9-15_469_1360_356_338} 8
4. 1. Using Figure 4, draw a resource histogram for the project to show how the project can be completed in the shortest 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]{22f11ce2-8d07-4f51-9326-b578d1e454f9-16_698_1534_541_251}
      \end{figure} 8
5. (ii) The racing team's boss assigns two members of the racing team to work on the project. Explain the effect this has on the minimum completion time for the project.
   You may use Figure 5 in your answer. \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Figure 5} \includegraphics[alt={},max width=\textwidth]{22f11ce2-8d07-4f51-9326-b578d1e454f9-16_704_1539_1695_248}
   \end{figure}