OCR MEI D1 (Decision Mathematics 1) 2009 June

1 The numbers on opposite faces of the die shown (a standard die) add up to 7. The adjacency graph for the die is a graph which has vertices representing faces. In the adjacency graph two vertices are joined with an arc if they share an edge of the die. For example, vertices 2 and 6 are joined by an arc because they share an edge of the die.
\includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-2_246_213_488_1608}

1. List the pairs of numbers which are opposite each other.
2. Draw the adjacency graph.
3. Identify and sketch a solid which has the following adjacency graph.
   \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-2_287_307_1027_879}

2 In this question INT( \(m\) ) means the integer part of \(m\). Thus INT(3.5) \(= 3\) and INT(4) \(= 4\).
A game for two players starts with a number, \(n\), of counters. Players alternately pick up a number of counters, at least 1 and not more than half of those left. The player forced to pick up the last counter is the loser. Arif programs his computer to play the game, using the rule "pick up INT(half of the remaining counters), or the last counter if forced".

1. You are to play against Arif's computer with \(n = 5\) and with Arif's computer going first. What happens at each turn?
2. You are to play against Arif's computer with \(n = 6\) and with Arif's computer going first. What happens at each turn?
3. Now play against Arif's computer with \(n = 7\) and with Arif's computer going first. Describe what happens.

3 Consider the following linear programming problem:
Maximise \(\quad 3 x + 4 y\)
subject to \(\quad 2 x + 5 y \leqslant 60\)
\(x + 2 y \leqslant 25\)
\(x + y \leqslant 18\)

1. Graph the inequalities and hence solve the LP.
2. The right-hand side of the second inequality is increased from 25 . At what new value will this inequality become redundant?

4 The diagram represents a very simple maze with two vertices, A and B. At each vertex a rat either exits the maze or runs to the other vertex, each with probability 0.5 . The rat starts at vertex A .
\includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-4_79_930_534_571}

1. Describe how to use 1-digit random numbers to simulate this situation.
2. Use the random digits provided in your answer book to run 10 simulations, each starting at vertex A. Hence estimate the probability of the rat exiting at each vertex, and calculate the mean number of times it runs between vertices before exiting. The second diagram represents a maze with three vertices, A, B and C. At each vertex there are three possibilities, and the rat chooses one, each with probability \(1 / 3\). The rat starts at vertex A.
   \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-4_566_889_1082_589}
3. Describe how to use 1-digit random numbers to simulate this situation.
4. Use the random digits provided in your answer book to run 10 simulations, each starting at vertex A. Hence estimate the probability of the rat exiting at each vertex.

5 The diagram represents canals connecting five cities. Canal lengths (shown on the arcs) are in km.
\includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-5_410_990_306_539}

1. Draw a network in your answer book with nodes representing the five cities and arcs representing direct canal connections, i.e. canal connections which do not involve passing through another city. The company operating the canal system wishes to close some canals to save money, whilst preserving the connectivity.
2. Starting at A, use Prim's algorithm on your answer to part (i) to find a minimum connector for the network. Give the order in which you include arcs. Draw your minimum connector and give its total length. Consider the original network together with an extra vertex, X , at the junction of four arcs.
   \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-5_405_987_1361_539}
3. Draw the minimum connector which results from applying Prim's algorithm, starting at A , to this network. Give the length of that minimum connector. Hence advise the company on which canals to close.
4. Give a reason why the company might face objections to such closures.

6 Joan and Keith have to clear and tidy their garden. The table shows the jobs that have to be completed, their durations and their precedences.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities.
3. Each job is to be done by one person only. Joan and Keith are equally able to do all jobs. Draw a cascade chart indicating how to organise the jobs so that Joan and Keith can complete the project in the least time. Give that least time and explain why the minimum project completion time is shorter.