OCR Further Discrete (Further Discrete) 2020 November

1 This question is about the planar graph shown below.
\includegraphics[max width=\textwidth, alt={}, center]{cc58fb7a-efb6-4548-a8e1-e40abe1eb722-2_567_1317_395_374}

1. 1. Apply Kuratowski's theorem to verify that the graph is planar.
   2. Use Euler's formula to calculate the number of regions in a planar representation of the graph.
2. 1. Write down a Hamiltonian cycle for the graph.
   2. By finding a suitable pair of vertices, show that Ore's theorem cannot be used to prove that the graph, as shown above, is Hamiltonian.
3. 1. Draw the graph formed by using the contractions AB and CF .
   2. Use Ore's theorem to show that this contracted graph is Hamiltonian.

2 Annie and Brett play a two-person, simultaneous play game. The table shows the pay-offs for Annie and Brett in the form ( \(a , b\) ). So, for example, if Annie plays strategy K and Brett plays strategy S, Annie wins 2 points and Brett wins 6 points.

1. 1. Determine the play-safe strategy for Annie.
   2. Show that the play-safe strategy for Brett is T.
2. 1. If Annie knows that Brett is planning on playing strategy T, which strategy should Annie play to maximise her points?
   2. If Brett knows that Annie is planning on playing the strategy identified in part (b)(i), which strategy should Brett play to maximise his points?
3. Show that, for Brett, strategy R is weakly dominated.
4. Using a graphical method, determine the optimal mixed strategy for Brett.
5. Show that the game has no Nash equilibrium points.

3 An initial simplex tableau is shown below.

1. Write down the objective for the problem that is represented by this initial tableau. Variables \(s\) and \(t\) are slack variables.
2. Use the final row of the initial tableau to explain what a slack variable is.
3. Carry out one iteration of the simplex algorithm and hence:
   • give the pivot column used and the value of the pivot element
   • write down the value of \(P\) after this iteration
   • find the values of \(x , y\) and \(z\) after this iteration
   • describe the effect of the iteration geometrically.

4

1. Show that there are 127 ways to partition a set of 8 distinct elements into two non-empty subsets. A group of 8 people ( \(\mathrm { A } , \mathrm { B } , \ldots\) ) have 8 reserved seats ( \(1,2 , \ldots\) ) on a coach. Seat 1 is reserved for person A , seat 2 for person B , and so on. The reserved seats are labelled but the individual people do not know which seat has been reserved for them. The first 4 people, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , choose their seats at random from the 8 reserved seats.
2. Determine how many different arrangements there are for the seats chosen by \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . The group organiser moves \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D to their correct seats (A in seat \(1 , \mathrm {~B}\) in seat \(2 , \mathrm { C }\) in seat 3 and D in seat 4).
   The other 4 people ( \(\mathrm { E } , \mathrm { F } , \mathrm { G }\) and H ) then choose their seats at random from the remaining 4 reserved seats ( \(5,6,7\) and 8 ).
3. List the 9 derangements of \(\{ \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } \}\), where none of these four people is in the seat that has been reserved for them. Suppose, instead, that the 8 people had chosen their seats at random from the 8 reserved seats, without the organiser intervening.
4. Determine the total number of ways in which the seats can be chosen so that 4 of the people are in their correct seats and 4 are not in their correct seats.

5 The manager of a farm shop wants to pave routes on the farm so that, after visiting the shop, customers can visit the animals in fields A, B, C, D and E.
The table shows the cost, in \(\pounds\), of making a paved path between each pair of fields.
A river means that it is not possible to make a paved path between C and E .

1. Determine the minimum cost of connecting the fields.
2. 1. By applying the lower bound algorithm to each vertex in turn, determine a best lower bound for \(P\), the minimum cost of making a circular tour (cycle) of paved paths that visits each field once.
   2. By applying the nearest neighbour algorithm, starting at each vertex in turn, find a best upper bound for \(P\). You do not need to attempt any route improvements.
   3. Give the order in which the fields are visited in a circular tour of paved paths that corresponds to the best upper bound found in part (b)(ii).
3. Give a practical reason why the total cost of paving for the project might be more than the best upper bound found in part (b)(ii). It becomes possible to use an existing bridge to make a paved route between C and E . Using this bridge, there is a new indirect route from A to D that costs less than \(\pounds 900\) to pave.
4. When this bridge is used, what can be determined about the minimum cost of
   1. paving the route between C and E
   2. connecting all the fields?

6 A project is represented by the activity on arc network below.
\includegraphics[max width=\textwidth, alt={}, center]{cc58fb7a-efb6-4548-a8e1-e40abe1eb722-7_410_1095_296_486} The duration of each activity (in minutes) is shown in brackets, apart from activity I.

1. Suppose that the minimum completion time for the project is 15 minutes.
   1. By calculating the early event times, determine the range of values for \(x\).
   2. By calculating the late event times, determine which activities must be critical. The table shows the number of workers needed for each activity.

      Activity	A	B	C	D	E	F	G	H	I	J	K
      Workers	2	1	1	2	\(n\)	1	2	1	1	1	4

2. Determine the maximum possible value for \(n\) if 5 workers can complete the project in 15 minutes. Explain your reasoning. The duration of activity F is reduced to 1.5 minutes, but only 4 workers are available. The minimum completion time is no longer 15 minutes.
3. Determine the minimum project completion time in this situation.
4. Find the maximum possible value for \(x\) for this minimum project completion time.
5. Find the maximum possible value for \(n\) for this minimum project completion time.