OCR D2 (Decision Mathematics 2) 2010 June

1 The famous fictional detective Agatha Parrot is investigating a murder. She has identified six suspects: Mrs Lemon \(( L )\), Prof Mulberry \(( M )\), Mr Nutmeg \(( N )\), Miss Olive \(( O )\), Capt Peach \(( P )\) and Rev Quince \(( Q )\). The table shows the weapons that could have been used by each suspect.

1. Draw a bipartite graph to represent this information. Put the weapons on the left-hand side and the suspects on the right-hand side. Agatha Parrot is convinced that all six suspects were involved, and that each used a different weapon. She originally thinks that the axe handle was used by Prof Mulberry, the broomstick by Miss Olive, the drainpipe by Mrs Lemon, the fence post by Mr Nutmeg and the golf club by Capt Peach. However, this would leave the hammer for Rev Quince, which is not a possible pairing.
2. Draw a second bipartite graph to show this incomplete matching.
3. Construct the shortest possible alternating path from \(H\) to \(Q\) and hence find a complete matching. Write down which suspect used each weapon.
4. Find a different complete matching in which none of the suspects used the same weapon as in the matching from part (iii).

2 In an investigation into a burglary, Agatha has five suspects who were all known to have been near the scene of the crime, each at a different time of the day. She collects evidence from witnesses and draws up a table showing the number of witnesses claiming sight of each suspect near the scene of the crime at each possible time. Suspect \begin{table}[h] \end{table}

1. Use the Hungarian algorithm on a suitably modified table, reducing rows first, to find the matchings for which the total number of claimed sightings is maximised. Show your working clearly. Write down the resulting matchings between the suspects and the times. Further enquiries show that the burglary took place at 5 pm , and that Dr Silverbirch was not the burglar.
2. Who should Agatha suspect?

3

1. Set up a dynamic programming tabulation to find the minimum weight route from ( \(0 ; 0\) ) to ( \(4 ; 0\) ) on the following directed network.
   \includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-03_707_1342_1594_443} Give the route and its total weight.
2. Explain carefully how the route is obtained directly from the values in the table, without referring to the network.

4 Euan and Wai Mai play a zero-sum game. Each is trying to maximise the total number of points that they score in many repeats of the game. The table shows the number of points that Euan scores for each combination of strategies.

1. Explain what the term 'zero-sum game' means.
2. How many points does Wai Mai score if she chooses \(X\) and Euan chooses \(A\) ?
3. Why should Wai Mai never choose strategy \(Z\) ?
4. Delete the column for \(Z\) and find the play-safe strategy for Euan and the play-safe strategy for Wai Mai on the table that remains. Is the resulting game stable or not? State how you know. The value 3 in the cell corresponding to Euan choosing \(D\) and Wai Mai choosing \(X\) is changed to - 5 ; otherwise the table is unchanged. Wai Mai decides that she will choose her strategy by making a random choice between \(X\) and \(Y\), choosing \(X\) with probability \(p\) and \(Y\) with probability \(1 - p\).
5. Write down and simplify an expression for the expected score for Wai Mai when Euan chooses each of his four strategies.
6. Using graph paper, draw a graph showing Wai Mai's expected score against \(p\) for each of Euan's four strategies and hence calculate the optimum value of \(p\).

5 Answer this question on the insert provided. The network represents a system of irrigation channels along which water can flow. The weights on the arcs represent the maximum flow in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-05_597_1553_479_296}

1. Calculate the capacity of the cut that separates \(\{ S , B , C , E \}\) from \(\{ A , D , F , G , H , T \}\).
2. Explain why neither arc \(S C\) nor arc \(B C\) can be full to capacity. Explain why the arcs \(E F\) and \(E H\) cannot both be full to capacity. Hence find the maximum flow along arc \(H T\). When arc \(H T\) carries its maximum flow, what is the flow along arc \(H G\) ?
3. Show a flow of 58 litres per second on the diagram in the insert, and find a cut of capacity 58. The direction of flow in \(H G\) is reversed.
4. Use the diagram in the insert to show the excess capacities and potential backflows for your flow from part (iii) in this case.
5. Without augmenting the labels from part (iv), write down flow augmenting routes to enable an additional 2 litres per second to flow from \(S\) to \(T\).
6. Show your augmented flow on the diagram in the insert. Explain how you know that this flow is maximal.

6 Answer parts (i), (ii) and (iii) of this question on the insert provided. The activity network for a project is shown below. The durations are in minutes. The events are numbered 1, 2, 3, etc. for reference.
\includegraphics[max width=\textwidth, alt={}, center]{406831f5-74a3-415e-8849-2c381bfe47f4-06_747_1249_482_447}

1. Complete the table in the insert to show the immediate predecessors for each activity.
2. Explain why the dummy activity is needed between event 2 and event 3, and why the dummy activity is needed between event 4 and event 5 .
3. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Record your early event times and late event times in the table in the insert. Write down the minimum project completion time and the critical activities. Suppose that the duration of activity \(K\) changes to \(x\) minutes.
4. Find, in terms of \(x\), expressions for the early event time and the late event time for event 9 .
5. Find the maximum duration of activity \(K\) that will not affect the minimum project completion time found in part (iii). \section*{ADVANCED GCE
   MATHEMATICS} Decision Mathematics 2
   INSERT for Questions 5 and 6
6. Dummy activity is needed between event 2 and event 3 because \(\_\_\_\_\)
   Dummy activity is needed between event 4 and event 5 because \(\_\_\_\_\)

7. Event	1	2	3	4	5	6	7	8	9	10
   Early event time
   Late event time

   Minimum project completion time = \(\_\_\_\_\) minutes Critical activities: \(\_\_\_\_\) \section*{Answer part (iv) and part (v) in your answer booklet.} OCR
   RECOGNISING ACHIEVEMENT