5 P62682RA Turn over 4. The complementary function for the second order recurrence relation un + 2 + αun + 1 + βun = 20 (−3) n    n  0 is given by un = A (2) n + B (−1) n where A and B are arbitrary non-zero constants. (a) Find the value of α and the value of β. (2) Given that 2u0 = u1 and u4 = 164 (b) find the solution of this second order recurrence relation to obtain an expression for un in terms of n. (6) (Total for Question 4 is 8 marks) 6 P62682RA 5. C1 C1 A D C B E F G H J (5, 8) (5, 7) (6, 10) (1, 2) (0, 2) (4, 6) (4, 8) (1, 6) (1, 1) (0, 4) (2, 3) (3, 6) (4, 6) (3, 7) (4, 5) (2, 5) (5, 7) Figure 2 Figure 2 shows a capacitated, directed network. The network represents a system of pipes through which fluid can flow. The weights on the arcs show the lower capacities and upper capacities for the corresponding pipes, in litres per second. (a) State the source node. (1) (b) Explain why the sink node must be G. (1) (c) Calculate the capacity of the cut C1 (1) (d) Assuming that a feasible flow exists, (i) explain why arc JH must be at its upper capacity, (ii) explain why arcs AD and CD must be at their lower capacities. (2) (e) Use Diagram 1 in the answer book to show a flow of 18 litres per second through the system. (2) (f) Prove that the answer to (e) is the maximum flow through the system. (3) (Total for Question 5 is 10 marks) 7 P62682RA Turn over 6. Player B Option X Option Y Option Z Player A Option Q 1 5 3 Option R 4 −3 1 Option S 2 −4 −2 Option T 3 −2 0 A two person zero-sum game is represented by the pay-off matrix for player A, shown above. (a) Explain, with justification, why this matrix may be reduced to a 3 × 3 matrix by removing option S from player A’s choices. (2) (b) Verify that there is no stable solution to the reduced game. (3) Player A intends to make a random choice between options Q, R and T, choosing option Q with probability p1, option R with probability p2 and option T with probability p3 Player A wants to find the optimal values of p1, p2 and p3 using the Simplex algorithm. Player A formulates the following linear programme, writing the constraints as inequalities. Maximise P = V, where V = the value of original game + 3 subject to V  4p1 + 7p2 + 6p3 V  8p1 + p3 V  6p1 + 4p2 + 3p3 p1 + p2 + p3  1 p1  0, p2  0, p3  0, V  0 (c) Explain why V cannot exceed any of the following expressions 4p1 + 7p2 + 6p3            8p1 + p3            6p1 + 4p2 + 3p3 (1) (d) Explain why it is necessary to use the constraint p1 + p2 + p3  1 (1) The Simplex algorithm is used to solve the linear programming problem. Given that the optimal value of p1 = 7 11 and the optimal value of p3 = 0 (e) calculate the value of the game to player A. (3) Player B intends to make a random choice between options X, Y and Z, choosing option X with probability q1, option Y with probability q2 and option Z with probability q3 (f) Determine the optimal strategy for player B, making your working clear. (4) (Total for Question 6 is 14 marks)