1 Hussain wants to travel by train from Edinburgh to Southampton, leaving Edinburgh after 9 am and
arriving in Southampton by 4 pm. He wants to leave
... [Show More] Edinburgh as late as possible.
Hussain rings the train company to find out about the train times. Write down a question he might ask that
leads to
(A) an existence problem,
(B) an optimisation problem. [2]
2 Some of the activities that may be involved in making a cup of tea are listed below.
A: Boil water.
B: Put teabag in teapot, pour on boiled water and let tea brew.
C: Get cup from cupboard.
D: Pour tea into cup.
E: Add milk to cup.
F: Add sugar to cup.
Activity A must happen before activity B.
Activities B and C must happen before activity D.
Activities E and F cannot happen until after activity C.
Other than that, the activities can happen in any order.
(i) Lisa does not take milk or sugar in her tea, so she only needs to use activities A, B, C and D. In how
many different orders can activities A, B, C and D be arranged, subject to the restrictions above? [1]
(ii) Mick takes milk but no sugar, so he needs to use activities A, B, C, D and E. Explain carefully why
there are exactly nine different orders for these activities, subject to the restrictions above. [3]
(iii) Find the number of different orders for all six activities, subject to the restrictions above. Explain your
reasoning carefully. [3]
3 A zero-sum game is being played between two players, X and Y. The pay-off matrix for X is given below.
Player Y
Player X
(i) Find an optimal mixed strategy for player X. [5]
(ii) Give one assumption that must be made about the behaviour of Y in order to make the mixed strategy
of Player X valid. [1]
Strategy R Strategy S
Strategy P 4 –2
Strategy Q –3 1
3
© OCR 2017 Y534 Turn over
4 Two graphs are shown below. Each has exactly five vertices with vertex orders 2, 3, 3, 4, 4.
Graph 1 Graph 2
(i) Write down a semi-Eulerian route for graph 1. [1]
(ii) Explain how the vertex orders show that graph 2 is also semi-Eulerian. [1]
(iii) By referring to specific vertices, explain how you know that these graphs are not simple. [2]
(iv) By referring to specific vertices, explain how you know that these graphs are not isomorphic. [2]
5 There are three non-isomorphic trees on five vertices.
(i) Draw an example of each of these trees. [1]
(ii) State three properties that must be satisfied by the vertex orders of a tree on six vertices. [3]
(iii) List the five different sets of possible vertex orders for trees on six vertices. [2]
(iv) Draw an example of each type listed in part (iii) [Show Less]