OCR Further Discrete (Further Discrete) Specimen

1 Fiona is a mobile hairdresser. One day she needs to visit five clients, A to E, starting and finishing at her own house at F . She wants to find a suitable route that does not involve her driving too far.

1. Which standard network problem does Fiona need to solve? The shortest distances between clients, in km, are given in the matrix below.

   	A	B	C	D	E
   A	-	12	8	6	4
   B	12	-	10	8	10
   C	8	10	-	13	10
   D	6	8	13	-	10
   E	4	10	10	10	-

2. Use the copy of the matrix in the Printed Answer Booklet to construct a minimum spanning tree for these five client locations.
   State the algorithm you have used, show the order in which you build your tree and give its total weight. Draw your minimum spanning tree. The distance from Fiona's house to each client, in km, is given in the table below.

   	A	B	C	D	E
   F	2	11	9	7	5

3. Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route.
4. (a) Find all the cycles that result from using the nearest neighbour method, starting at F .
   (b) Use these to find an upper bound for the length of Fiona's route.
5. Fiona wants to drive less than 35 km . Using the information in your answers to parts (iii) and (iv) explain whether or not a route exists which is less than 35 km in length.

2 Kirstie has bought a house that she is planning to renovate. She has broken the project into a list of activities and constructed an activity network, using activity on arc. \includegraphics[max width=\textwidth, alt={}, center]{0c9513fe-a471-427e-ba30-b18df11271e3-3_887_1751_1030_207}

1. Construct a cascade chart for the project, showing the float for each non-critical activity.
2. Calculate the float for remodelling the internal layout stating how much of this is independent float and how much is interfering float. Kirstie needs to supervise the project. This means that she cannot allow more than three activities to happen on any day.
3. Describe how Kirstie should organise the activities so that the project is completed in the minimum project completion time and no more than three activities happen on any day.

3 Bob has been given a pile of five letters addressed to five different people. He has also been given a pile of five envelopes addressed to the same five people. Bob puts one letter in each envelope at random.

1. How many different ways are there to pair the letters with the envelopes?
2. Find the number of arrangements with exactly three letters in the correct envelopes.
3. (a) Show that there are two derangements of the three symbols A , B and C .
   (b) Hence find the number of arrangements with exactly two letters in the correct envelopes. Let \(\mathrm { D } _ { n }\) represent the number of derangements of \(n\) symbols.
4. Explain why \(\mathrm { D } _ { n } = ( n - 1 ) \times \left( \mathrm { D } _ { n - 1 } + \mathrm { D } _ { n - 2 } \right)\).
5. Find the number of ways in which all five letters are in the wrong envelopes.

4 The table shows the pay-off matrix for player \(A\) in a two-person zero-sum game between \(A\) and \(B\). Player \(A\)
Player \(B\)

1. Find the play-safe strategy for player \(A\) and the play-safe strategy for player \(B\). Use the values of the play-safe strategies to determine whether the game is stable or unstable.
2. If player \(B\) knows that player \(A\) will use their play-safe strategy, which strategy should player \(B\) use?
3. Suppose that the value in the cell where both players use their play-safe strategies can be changed, but all other entries are unchanged. Show that there is no way to change this value that would make the game stable.
4. Suppose, instead, that the value in one cell can be changed, but all other entries are unchanged, so that the game becomes stable. Identify a suitable cell and write down a new pay-off value for that cell which would make the game stable.
5. Show that the zero-sum game in the table above has a Nash equilibrium and explain what this means for the players.

5 A garden centre sells tulip bulbs in mixed packs. The cost of each pack and the number of tulips of each colour are given in the table. Dirk is designing a floral display in which he will need the number of red tulips to be at most 50 more than the number of white tulips, and the number of white tulips to be less than or equal to twice the number of pink tulips. He has a budget of \(\pounds 240\) and wants to find out which packs to buy to maximise the total number of bulbs. Dirk uses the variables \(x , y\) and \(z\) to represent, respectively, how many of pack A , pack B and pack C he buys. He sets up his problem as an initial simplex tableau, which is shown below. Initial tableau
Row 1
Row 2
Row 3
Row 4

1. Show how the constraint on the number of red tulips leads to one of the rows of the tableau. The tableau that results after the first iteration is shown below.
   After first iteration
   Row 5
   Row 6
   Row 7
   Row 8

   \(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	RHS
   1	0	- 0.04	0.06	0	0	0.02	4.8
   0	0	1	- 1	1	0	0	5
   0	0	10.8	7.3	0	1	0.1	24
   0	1	0.96	1.06	0	0	0.02	4.8

2. Which cell was used as the pivot?
3. Explain why row 2 and row 6 are the same.
4. (a) Read off the values of \(x , y\) and \(z\) after the first iteration.
   (b) Interpret this solution in terms of the original problem.
5. Identify the variable that has become non-basic. Use the pivot row of the initial tableau to eliminate \(x\) algebraically from the equation represented by Row 1 of the initial tableau. The feasible region can be represented graphically in three dimensions, with the variables \(x , y\) and \(z\) corresponding to the \(x\)-axis, \(y\)-axis and \(z\)-axis respectively. The boundaries of the feasible region are planes. Pairs of these planes intersect in lines and at the vertices of the feasible region these lines intersect.
6. The planes defined by each of the new basic variables being set equal to 0 intersect at a point. Show how the equations from part (v) are used to find the values \(P\) and \(x\) at this point. A planar graph \(G\) is described by the adjacency matrix below. \(\quad\)
   \(A\)
   \(B\)
   \(C\)
   \(D\)
   \(E\)
   \(F\) \(\left( \begin{array} { c c c c c c } A & B & C & D & E & F
   0 & 1 & 0 & 0 & 1 & 1
   1 & 0 & 1 & 0 & 1 & 0
   0 & 1 & 0 & 1 & 0 & 0
   0 & 0 & 1 & 0 & 1 & 1
   1 & 1 & 0 & 1 & 0 & 0
   1 & 0 & 0 & 1 & 0 & 0 \end{array} \right)\)
7. Draw the graph \(G\).
8. Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it.
9. Explain why graph \(G\) cannot have a Hamiltonian cycle that includes the edge \(A B\). Deduce how many Hamiltonian cycles graph \(G\) has. A colouring algorithm is given below. STEP 1: Choose a vertex, colour this vertex using colour 1. STEP 2: If all vertices are coloured, STOP. Otherwise use colour 2 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 1 . STEP 3: If all vertices are coloured, STOP. Otherwise use colour 1 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 2 . STEP 4: Go back to STEP 2.
10. Apply this algorithm to graph \(G\), starting at \(E\). Explain how the colouring shows you that graph \(G\) is not bipartite. By removing just one edge from graph \(G\) it is possible to make a bipartite graph.
11. Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph. Graph \(G\) is augmented by the addition of a vertex \(X\) joined to each of \(A , B , C , D , E\) and \(F\).
12. Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2.