OCR MEI D1 (Decision Mathematics 1) 2012 January

1 A graph is obtained from a solid by producing a vertex for each exterior face. Vertices in the graph are connected if their corresponding faces in the original solid share an edge. The diagram shows a solid followed by its graph. The solid is made up of two cubes stacked one on top of the other. This solid has 10 exterior faces, which correspond to the 10 vertices in the graph. (Note that in this question it is the exterior faces of the cubes that are being counted.)
\includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_455_309_571_653}
\includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_444_286_573_1135}

1. Draw the graph for a cube.
2. Obtain the number of vertices and the number of edges for the graph of three cubes stacked on top of each other.
   \includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_643_305_1302_881}

2 The following is called the '1089' algorithm. In steps 1 to 4 numbers are to be written with exactly three digits; for example 42 is written as 042. Step 1 Choose a 3-digit number, with no digit being repeated.
Step 2 Form a new number by reversing the order of the three digits.
Step 3 Subtract the smaller number from the larger and call the difference D. If the two numbers are the same then \(\mathrm { D } = 000\). Step 4 Form a new number by reversing the order of the three digits of D , and call it R .
Step 5 Find the sum of D and R .

1. Apply the algorithm, choosing 427 for your 3-digit number, and showing all of the steps.
2. Apply the algorithm to a 3-digit number of your choice, showing all of the steps.
3. Investigate what happens if digits may be repeated in the 3 -digit number in step 1 .

3 Solve the following LP problem graphically.
Maximise \(2 x + 3 y\)
subject to \(\quad x + y \leqslant 11\) $$\begin{aligned} 3 x + 5 y & \leqslant 39
x + 6 y & \leqslant 39 . \end{aligned}$$

4 The table defines a network in which the numbers represent lengths.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest paths from A to each of the other vertices. Give the paths and their lengths.
3. Draw a new network containing all of the edges in your shortest paths, and find the total length of the edges in this network.
4. Find a minimum connector for the original network, draw it, and give the total length of its edges.
5. Explain why the method defined by parts (i), (ii) and (iii) does not always give a minimum connector.

5 Five gifts are to be distributed among five people, A, B, C, D and E. The gifts are labelled from 1 to 5. Each gift is allocated randomly to one of the five people. A person can receive more than one gift.

1. Use one-digit random numbers to simulate this process. One-digit random numbers are provided in your answer book. Explain how your simulation works. Produce a table, showing how many gifts each person receives.
2. Carry out four more simulations showing, in each case, how many gifts each person receives.
3. Use your simulation to estimate the probabilities of a person receiving \(0,1,2,3,4\) and 5 gifts.
4. Describe what you would have to do differently if there were six people and six gifts.

6 The table shows the tasks involved in making a salad, their durations and their precedences.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early and late times for each event. Give the minimum completion time and the critical activities.
3. Given that each task can only be done by one person, how many people are needed to prepare the salad in the minimum time? What is the minimum time required to prepare the salad if only one person is available?
4. Show how two people can prepare the salad as quickly as possible.