OCR MEI D1 (Decision Mathematics 1) 2014 June

1 The diagram shows the layout of a Mediterranean garden. Thick lines represent paths.
\includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-2_961_1093_440_468}

1. Draw a graph to represent this information using the vertices listed below, and with arcs representing the 18 paths. Vertices: patio (pa); pool (po); top steps (ts); orange tree (or); fig tree (fi); pool door (pd); back door (bd); front door (fd); front steps (fs); gate (gat); olive tree (ol); garage (gar). [2] Joanna, the householder, wants to walk along all of the paths.
2. Explain why she cannot do this without repeating at least one path.
3. Write down a route for Joanna to walk along all of the paths, repeating exactly one path. Write down the path which must be repeated. Joanna has a new path constructed which links the pool directly to the top steps.
4. Describe how this affects Joanna's walk, and where she can start and finish. (You are not required to give a new route.)

2 Honor either has coffee or tea at breakfast. On one third of days she chooses coffee, otherwise she has tea. She can never remember what she had the day before.

1. Construct a simulation rule, using one-digit random numbers, to model Honor's choices of breakfast drink.
2. Using the one-digit random numbers in your answer book, simulate Honor's choice of breakfast drink for 10 days. Honor also has either coffee or tea at the end of her evening meal, but she does remember what she had for breakfast, and her choice depends on it. If she had coffee at breakfast then the probability of her having coffee again is 0.55 . If she had tea for breakfast, then the probability of her having tea again is 0.15 .
3. Construct a simulation rule, using two-digit random numbers, to model Honor's choice of evening drink given that she had coffee at breakfast. Construct a simulation rule, using two-digit random numbers, to model Honor's choice of evening drink given that she had tea at breakfast.
4. Using your breakfast simulation from part (ii), and the two-digit random numbers in your answer book, simulate Honor's choice of evening drink for 10 days.
5. Use your results from parts (ii) and (iv) to estimate the proportion of Honor's drinks, breakfast and evening meal combined, which are coffee. \section*{Question 3 begins on page 4}

3 Six remote villages are linked by a set of roads. Two villages are connected directly if there is a road between them which does not pass through another village. The table gives the lengths in miles of all direct connections.

1. Why might it be thought surprising that the direct distance between A and D is as long as 12 miles? Give a possible reason why the distance is longer than might have been expected.
2. Use the tabular form of Prim's algorithm, starting at A , to find a minimum connector for these villages. Draw your connector and give its total length.

4 The table lists tasks which are involved in adding a back door to a garage. The table also lists the duration and immediate predecessor(s) for each task. Each task is undertaken by one person.

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. Produce a schedule to show how two people can complete the project in the minimum time. Soon after starting activity D , the marble step breaks. Getting a replacement step adds 4 hours to the duration of activity D.
4. How does this delay affect the minimum completion time, the critical activities and the minimum time needed for two people to complete the project? \section*{Question 5 begins on page 6}

5

1. The following instructions operate on positive integers greater than 4.
   Step 10 Choose any positive integer greater than 4, and call it \(n\).
   Step 15 Write down \(n\).
   Step 20 If \(n\) is even then let \(n = \frac { n } { 2 }\) and write down the result.
   Step 30 If \(n\) is odd then let \(n = 3 n + 1\) and write down the result.
   Step 40 Go to Step 20.
   1. Apply the instructions with 6 as the chosen integer, stopping when a sequence repeats itself.
   2. Apply the instructions with 256 as the chosen integer, stopping when a sequence repeats itself.
   3. Add an instruction to stop the process when \(n\) becomes 1 .
   4. It is not known if, when modified to stop cycling through \(4,2,1\), the instructions form an algorithm. What would need to be known for it to be an algorithm?
2. Six items with weights given in the table are to be packed into boxes each of which has a capacity of 10 kg .

   Item	A	B	C	D	E	F
   Weight \(( \mathrm { kg } )\)	2	1	6	3	3	5

   The first-fit algorithm is as follows.
   \includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-7_809_1280_660_356}
   1. Use the first-fit algorithm to pack the items in the order given, and state how many boxes are needed.
   2. Place the items in increasing order of weight, and then apply the first-fit algorithm.
   3. Place the items in decreasing order of weight, and then apply the first-fit algorithm. An optimal solution is one which uses the least number of boxes.
   4. Find a set of weights for which placing in decreasing order of weight, and then applying the firstfit algorithm, does not give an optimal solution. Show both the results of first-fit decreasing and an optimal solution.
   5. First-fit decreasing has quadratic complexity. If it takes a person 30 seconds to apply first-fit decreasing to 6 items, about how long would it take that person to apply it to 60 items?

6 Ian the chef is to make vegetable stew and vegetable soup for distribution to a small chain of vegetarian restaurants. The recipes for both of these require carrots, beans and tomatoes. 10 litres of stew requires 1.5 kg of carrots, 1 kg of beans and 1.5 kg of tomatoes.
10 litres of soup requires 1 kg of carrots, 0.75 kg of beans and 1.5 kg of tomatoes. Ian has available 100 kg of carrots, 70 kg of beans and 110 kg of tomatoes.

1. Identify appropriate variables and write down three inequalities corresponding to the availabilities of carrots, beans and tomatoes.
2. Graph your inequalities and identify the region corresponding to feasible production plans. The profit on a litre of stew is \(\pounds 5\), and the profit on a litre of soup is \(\pounds 4\).
3. Find the most profitable production plan, showing your working. Give the maximum profit. Ian can buy in extra tomatoes at \(\pounds 2.50\) per kg .
4. What extra quantity of tomatoes should Ian buy? How much extra profit would be generated by the extra expenditure? \section*{END OF QUESTION PAPER} \section*{OCR}