OCR MEI D1 (Decision Mathematics 1) 2008 January

1 The graph shows routes that are available to an international lorry driver. The solid arcs represent motorways and the broken arcs represent ferry crossings.
\includegraphics[max width=\textwidth, alt={}, center]{dfe6db33-33d0-4dff-95f7-fbf097e3963e-2_668_1131_587_466}

1. Give a route from Milan to Chania involving exactly two ferry crossings. How many such routes are there?
2. Give a route from Milan to Chania involving exactly three ferry crossings. How many such routes are there?
3. Give a route from Milan to Chania using as many ferry crossings as possible, without repeating any arc.
   [0pt]
4. Give a route leaving Piraeus and finishing elsewhere which uses every arc once and only once.[3]

2 Consider the following linear programming problem.
Maximise $$\mathrm { P } = 6 x + 7 y$$ subject to $$\begin{aligned} & 2 x + 3 y \leqslant 9
& 3 x + 2 y \leqslant 12
& x \geqslant 0
& y \geqslant 0 \end{aligned}$$

1. Use a graphical approach to solve the problem.
2. Give the optimal values of \(x , y\) and P when \(x\) and \(y\) are integers.

3 The following algorithm (J. M. Oudin, 1940) claims to compute the date of Easter Sunday in the Gregorian calendar system.
The algorithm uses the year, y, to give the month, m, and day, d, of Easter Sunday.
All variables are integers and all remainders from division are dropped. For example, 7 divided by 3 is 2 remainder 1 . The remainder is dropped, giving the answer 2. $$\begin{aligned} & c = y / 100
& n = y - 19 \times ( y / 19 )
& k = ( c - 17 ) / 25
& i = c - ( c / 4 ) - ( c - k ) / 3 + ( 19 \times n ) + 15
& i = i - 30 \times ( i / 30 )
& i = i - ( i / 28 ) \times ( 1 - ( i / 28 ) \times ( 29 / ( i + 1 ) ) \times ( ( 21 - n ) / 11 ) )
& j = y + ( y / 4 ) + i + 2 - c + ( c / 4 )
& j = j - 7 \times ( j / 7 )
& p = i - j
& m = 3 + ( p + 40 ) / 44
& d = p + 28 - 31 \times ( m / 4 ) \end{aligned}$$ For example, for 2008:
\(\mathrm { y } = 2008\)
\(\mathrm { c } = 2008 / 100 = 20\)
\(n = 2008 - 19 \times ( 2008 / 19 ) = 2008 - 19 \times ( 105 ) = 13\), etc.
Complete the calculation for 2008.

4 In a population colonizing an island 40\% of the first generation (parents) have brown eyes, \(40 \%\) have blue eyes and \(20 \%\) have green eyes. Offspring eye colour is determined according to the following rules. \section*{Eye colours of parents Eye colour of offspring} (1) both brown
(2) one brown and one blue \(50 \%\) brown and \(50 \%\) blue
(3) one brown and one green blue
(4) both blue \(25 \%\) brown, \(50 \%\) blue and \(25 \%\) green
(5) one blue and one green 50\% blue and \(50 \%\) green
(6) both green green

1. Give an efficient rule for using 1-digit random numbers to simulate the eye colour of a parent randomly selected from the colonizing population.
2. Give an efficient rule for using 1-digit random numbers to simulate the eye colour of offspring born of parents both of whom have blue eyes. The table in your answer book shows an incomplete simulation in which parent eye colours have been randomly selected, but in which offspring eye colours remain to be determined or simulated.
3. Complete the table using the given random numbers where needed. (You will need your own rules for cases \(( 2 )\) and 5 .)
   Each time you use a random number, explain how you decide which eye colour for the offspring. \(\square\)

5 The table shows some of the activities involved in building a block of flats. The table gives their durations and their immediate predecessors.

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. Each of the tasks E, F, H and J can be speeded up at extra cost. The maximum number of weeks by which each task can be shortened, and the extra cost for each week that is saved, are shown in the table below.

   Task	E	F	H	J
   Maximum number of weeks by which task may be shortened	3	3	1	3
   Cost per week of shortening task (in thousands of pounds)	30	15	6	20

3. Find the new shortest time for the flats to be completed.
4. List the activities which will need to be speeded up to achieve the shortest time found in part (iii), and the times by which each must be shortened.
5. Find the total extra cost needed to achieve the new shortest time.

6 The diagram shows routes between points in a town. The distances are in kilometres.
\includegraphics[max width=\textwidth, alt={}, center]{dfe6db33-33d0-4dff-95f7-fbf097e3963e-6_817_1219_319_422}

1. Use an appropriate algorithm to find a set of connecting arcs of minimum total length. Indicate your connecting arcs on the copy of the diagram in your answer book, and give their total length.
2. Give the name of the algorithm you have used, and describe it briefly.
3. Using the second diagram in your answer book, apply Dijkstra's algorithm to find the shortest distances from A to each of the other points. List the connections that are used, and give their total length.