OCR MEI D1 (Decision Mathematics 1) 2005 January

1 The bipartite graph in Fig. 1 represents a board game for two players. At each turn a player tosses a coin and moves their counter. The graph shows which square the counter is moved to if the coin shows heads, and which square if it shows tails. Each player starts with their counter on square 1. Play continues until one player gets their counter to square 9 and wins. \begin{figure}[h] \end{figure}

1. Draw a tree to show all of the possibilities for the player's first three moves.
2. Show how a player can win in 3 turns.
3. List all squares which it is possible for a counter to occupy after 3 turns.
4. Show that a game can continue indefinitely.

2 Answer this question on the insert provided.

1. Use Dijkstra's algorithm to find the least weight route from \(A\) to \(G\) in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_458_584_525_760} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
   \end{figure}
2. Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_421_533_1307_779} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.

3 The following algorithm finds the highest common factor of two positive integers. ("int (x)" stands for the integer part of x, e.g. int (7.8) = 7.) \begin{figure}[h] \end{figure}

1. Run the algorithm with \(\mathrm { A } = 84\) and \(\mathrm { B } = 660\), showing all of your calculations.
2. Run the algorithm with \(\mathrm { A } = 660\) and \(\mathrm { B } = 84\), showing as many calculations as are necessary.
3. The algorithm is run with \(\mathrm { A } = 30\) and \(\mathrm { B } = 42\), and the result is shown in Table 3.2 below. \begin{table}[h]

   A	B	Q	R 1	R 2
   30	42	1	12
   12	30	2		6
   			6
   6	12	2		0

   \captionsetup{labelformat=empty} \caption{Print 6}
   \end{table} Table 3.2 The first line of the table shows that \(12 = 42 - 1 \times 30\).
   Use the second line to obtain a similar expression for 6 in terms of 30 and 12.
   Hence express 6 in the form \(\mathrm { m } \times 30 - \mathrm { n } \times 42\), where m and n are integers.

4 Answer this question on the insert provided. The table shows activities involved in a "perm" in a hair salon, their durations and immediate predecessors. \begin{table}[h] \end{table}

1. Complete the activity-on-arc network in the insert to represent the precedences.
2. Perform a forward pass and a backward pass to find early and late event times. Give the critical activities and the time needed to complete the perm.
3. Give the total float time for the activity \(G\). Activities \(\mathrm { D } , \mathrm { F } , \mathrm { H } , \mathrm { K }\) and N require a stylist.
   Activities \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { E } , \mathrm { G } , \mathrm { J }\) and M are done by a trainee.
   Activities \(I\) and \(L\) require no-one in attendance.
   A stylist and a trainee are to give a perm to a customer.
4. Use the chart in the insert to show a schedule for the activities, assuming that all activities are started as early as possible.
5. Which activity would be better started at its latest start time?

5 There is an insert for use in parts (iii) and (iv) of this question.
This question concerns the simulation of cars passing through two sets of pedestrian controlled traffic lights. The time intervals between cars arriving at the first set of lights are distributed according to Table 5.1. \begin{table}[h] \end{table}

1. Give an efficient rule for using two-digit random numbers to simulate arrival intervals.
2. Use two-digit random numbers from the list below to simulate the arrival times of five cars at the first lights. The first car arrives at the time given by the first arrival interval. Random numbers: \(24,01,99,89,77,19,58,42\) The two sets of traffic lights are 23 seconds driving time apart. Moving cars are always at least 2 seconds apart. If there is a queue at a set of lights, then when the red light ends the first car in the queue moves off immediately, the second car 2 seconds later, the third 2 seconds after that, etc. In this simple model there is to be no consideration of accelerations or decelerations, and the lights are either red or green. Table 5.2 shows the times when the lights are red. \begin{table}[h]

   \multirow{2}{*}{ first set of lights }	red start time	14	50	105	155
   \cline { 2 - 6 }	red end time	29	65	120	170
   \multirow{2}{*}{ second set of lights }	red start time	10	55	105	150
   \cline { 2 - 6 }	red end time	25	70	120	165

   \captionsetup{labelformat=empty} \caption{Table 5.2}
   \end{table}
3. Complete the table in the insert to simulate the passage of 10 cars through both sets of traffic lights. Use the arrival times given there.
4. Find the mean delay experienced by these cars in passing through each set of lights.
5. How could the output from this simulation model be made more reliable?

6 A recipe for jam states that the weight of sugar used must be between the weight of fruit used and four thirds of the weight of fruit used. Georgia has 10 kg of fruit available and 11 kg of sugar.

1. Define two variables and formulate inequalities in those variables to model this information.
2. Draw a graph to represent your inequalities.
3. Find the vertices of your feasible region and identify the points which would represent the best mix of ingredients under each of the following circumstances.
   (A) There is to be as much jam as possible, given that the weight of jam produced is the sum of the weights of the fruit and the sugar.
   (B) There is to be as much jam as possible, given that it is to have the lowest possible proportion of sugar.
   (C) There is to be as much jam as possible, given that it is to have the highest possible proportion of sugar.
   (D) Fruit costs \(\pounds 1\) per kg, sugar costs 50 p per kg and the objective is to produce as much jam as possible within a budget of \(\pounds 15\).