OCR MEI D1 (Decision Mathematics 1) 2015 June

1 The directed bipartite graph represents links between chairlifts and ski runs in one part of a ski resort. Chairlifts are represented by capital letters, and ski runs are represented by numbers. For example, chairlift A takes skiers to the tops of ski runs 1 and 2, whereas ski run 2 takes skiers to the bottom of chairlift B .
\includegraphics[max width=\textwidth, alt={}, center]{a27c868b-4fc4-4e82-b27f-d367b15b42c2-2_551_333_493_849}

1. The incomplete map in your answer book represents the three chairlifts and ski run 2 . Complete the map by drawing in the other 4 ski runs. Angus wants to ski all 5 ski runs, starting and finishing at the bottom of chairlift A .
2. Which chairlifts does Angus have to repeat, and why?
3. Which ski runs does Angus have to repeat, and why? The chairlifts and ski runs shown above form only part of the resort. In fact, chairlift C also takes skiers to the bottom of chairlift \(D\).
4. Why can this information not be represented in a bipartite graph?

2 The following algorithm operates on the equations of 3 straight lines, each in the form \(y = m _ { i } x + c _ { i }\).

1. Run the algorithm for the straight lines \(y = 2 x + 8 , y = 2 x + 5\) and \(y = 4 x + 3\) using the table given in your answer book. The first five steps have been completed, so you should continue from Step 6. [7]
2. Describe what the algorithm achieves.

3 Mary takes over a small café. She will sell two types of hot drink: tea and coffee.
A coffee filter costs her \(\pounds 0.10\), and makes one cup of coffee. A tea bag costs her \(\pounds 0.05\) and makes one cup of tea. She has a total weekly budget of \(\pounds 50\) to spend on coffee filters and tea bags. She anticipates selling at least 500 cups of hot drink per week. She estimates that between \(50 \%\) and \(75 \%\) of her sales of cups of hot drink will be for cups of coffee. Mary needs help to decide how many coffee filters and how many tea bags to buy per week.

1. Explain why the number of tea bags which she buys should be no more than the number of coffee filters, and why it should be no less than one third of the number of coffee filters.
2. Allocate appropriate variables, and draw a graph showing the feasible region for Mary's problem. Mary's partner suggests that she buys 375 coffee filters and 250 tea bags.
3. How does this suggestion relate to the estimated demand for coffee and tea?

4 The table defines a network on 6 nodes, the numbers representing distances between those nodes.

1. Use Dijkstra's algorithm to find the shortest routes from A to each of the other vertices. Give those routes and their lengths.
2. Jack wants to find a minimum spanning tree for the network.
   1. Apply Prim's algorithm to the network, draw the minimum spanning tree and give its length. Jill suggests the following algorithm is easier.
      Step 1 Remove an arc of longest length which does not disconnect the network
      Step 2 If there is an arc which can be removed without disconnecting the network then go to Step 1
      Step 3 Stop
   2. Show the order in which arcs are removed when Jill's algorithm is applied to the network.
   3. Explain why Jill's algorithm always produces a minimum spanning tree for a connected network.
   4. In a complete network on \(n\) vertices there are \(\frac { n ( n - 1 ) } { 2 }\) arcs. There are \(n - 1\) arcs to include when using Prim's algorithm. How many arcs are there to remove using Jill's algorithm? For what values of \(n\) does Jill have more arcs to remove than Prim has to include?

5 The table lists activities which are involved in framing a picture. The table also lists their durations and their immediate predecessors. Except for activities C and H, each activity is undertaken by one person. Activities C and H require no people.

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. A picture is to be framed as quickly as possible. Two people are available to do the job.
3. Produce a schedule to show how two people can complete the picture framing in the minimum time. To reduce the completion time an instant glue is to be used. This will reduce the time for activities C and H to 0 minutes.
4. Produce a schedule for two people to complete the framing in the new minimum completion time, and give that time.

6 Adrian and Kleo like to go out for meals, sometimes to a French restaurant, and sometimes to a Greek restaurant. If their last meal out was at the French restaurant, then the probability of their next meal out being at the Greek restaurant is 0.7 , whilst the probability of it being at the French restaurant is 0.3 . If their last meal out was at the Greek restaurant, then the probability of their next meal out being at the French restaurant is 0.6 , whilst the probability of it being at the Greek restaurant is 0.4 .

1. Construct two simulation rules, each using single-digit random numbers, to model their choices of where to eat.
2. Their last meal out was at the Greek restaurant. Use the random digits printed in your answer book to simulate their choices for the next 10 of their meals out. Hence estimate the proportion of their meals out which are at the French restaurant, and the proportion which are at the Greek restaurant. Adrian and Kleo find a Hungarian restaurant which they like. The probabilities of where they eat next are now given in the following table.

   \backslashbox{last meal out}{next meal out}	French	Greek	Hungarian
   French	\(\frac { 1 } { 5 }\)	\(\frac { 3 } { 5 }\)	\(\frac { 1 } { 5 }\)
   Greek	\(\frac { 1 } { 2 }\)	\(\frac { 3 } { 10 }\)	\(\frac { 1 } { 5 }\)
   Hungarian	\(\frac { 1 } { 3 }\)	\(\frac { 1 } { 3 }\)	\(\frac { 1 } { 3 }\)

3. Construct simulation rules, each using single-digit random numbers, to model this new situation.
4. Their last meal out was at the Greek restaurant. Use the random digits printed in your answer book to simulate their choices for the next 10 of their meals out. Hence estimate the proportion of their meals out which are at each restaurant. \section*{END OF QUESTION PAPER}