4 P66804A 4. Sequences {xn} and {yn} for n ∈ , are defined by xn + 1 = 2yn + 3 and yn + 1 = 3xn + 1 – 4xn x1 = 1 and y1 = a where a is a constant. (a) Show that xn + 2 – 6xn + 1 + 8xn = 3 (1) (b) Solve the second‑order recurrence relation given in (a) to obtain an expression for xn in terms of a and n. (8) Given that x7 = 28 225 (c) find the value of a. (2) (Total for Question 4 is 11 marks) 5 Turn over P66804A 5. A S (4, 10) (10, 18) (5, 10) (0, 2) (5, 8) (3, 8) (2, 5) (2, 5) (12, 17) (4, 8) (0, 4) (3, 7) (20, 30) (1, 4) (1, 5) (0, 8) (18, 22) (7, 11) D E G F T B C2 C1 C C2 C1 (3, 6) Figure 1 Figure 1 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 and upper capacities for the corresponding pipes, in litres per second. (a) Calculate the capacity of (i) cut C1 (ii) cut C2 (2) (b) Using only the capacities of cuts C1 and C2 , state what can be deduced about the maximum flow through the system. (1) 6 P66804A A S 5 6 6 6 6 20 28 0 11 14 5 2 2 2 2 2 2 D E G T F B C 12 4 Figure 2 Figure 2 shows an initial flow through the same network. (c) State the value of the initial flow. (1) (d) By entering values along BC, CF and DT, complete the labelling procedure on Diagram 1 in the answer book. (2) (e) Use the labelling procedure to find a maximum flow through the network. You must list each flow‑augmenting route you use, together with its flow. (3) (f) Use your answer to (e) to find a maximum flow pattern for this system of pipes and draw it on Diagram 2 in the answer book. (1) (g) Prove that the answer to (f) is optimal. (3) A vertex restriction is now applied to B so that no more than 16 litres per second can flow through it. (h) (i) Complete Diagram 3 in the answer book to show this restriction. (ii) State the value of the maximum flow with this restriction. (3) (Total for Question 5 is 16 marks) 7 Turn over P66804A 6. A S 52 52 53 53 51 51 51 51 50 50 50 50 50 48 46 48 47 47 49 49 E G J T H D F I B C 53 52 46 Figure 3 The staged, directed network in Figure 3 represents a series of roads connecting 12 towns, S, A, B, C, D, E, F, G, H, I, J and T. The number on each arc shows the distance between these towns, in miles. Bradley is planning a four‑day cycle ride from S to T. He plans to leave his home at S. On the first night he will stay at A, B or C, on the second night he will stay at D, E, F or G, on the third night he will stay at H, I or J, and he will arrive at his friend’s house at T on the fourth day. Bradley decides that the maximum distance he will cycle on any one day should be as small as possible. (a) Write down the type of dynamic programming problem that Bradley needs to solve. (1) (b) Use dynamic programming to complete the table in the answer book. (9) (c) Hence write down the possible routes that Bradley could take. (2) (Total for Question 6 is 12 marks)