Questions D2 - A-Level Maths

Day	From	To		Number of churches
Friday	J	Kayton	$K$	4
	J	Little Elling	$L$	5
Saturday	K	Moreton Emcombe	M	2
	K	Nether Ensleigh	$N$	0
	L	Nether Ensleigh	$N$	0
	L	Peacombe	$P$	4
Sunday	M	River Ardan	$R$	0
	N	River Ardan	$R$	4
	P	Seabury	$S$	3
	$P$	Teebury	$T$	2
Monday	$R$	Jeremy's home	$J$	4
	S	Jeremy's home	$J$	0
	$T$	Jeremy's home	$J$	0

\captionsetup{labelformat=empty} \caption{Table 1}

\end{table}

Represent the information in the table as a directed network in which the vertices represent the places. You may code the place names using the letters, as above. Jeremy wants to use dynamic programming to find the route on which he will pass the greatest number of churches. The (stage; state) variables will represent the places where he stays overnight. $J$ will have (stage; state) variable ( $0 ; 0$ ) at the start of the journey and ( $4 ; 0$ ) at the end. Table 2 shows the (stage; state) variables for all the other places. \begin{table}[h]
Place $K$ $L$ $M$ $N$ $P$ $R$ $S$ $T$
Stage variable 1 1 2 2 2 3 3 3
State variable 0 1 0 1 2 0 1 2
\captionsetup{labelformat=empty} \caption{Table 2}
\end{table}
Set up a dynamic programming tabulation, working backwards from Monday to Friday, to find the route that Jeremy should take to pass the greatest number of churches. Write down Jeremy's route. You may code the place names using the letters, as above. Write down the number of churches that he will be able to photograph on this route.

OCR D2 2015 June Q5

5 The diagram shows a flow through a network of directed arcs. The amount that can flow in each arc is limited by its upper capacity, and the lower capacity of each arc is 0 . The labelled arrows by the arcs show how much more (excess capacity) and how much less (potential backflow) could flow in each arc, in litres per second, and the objective is to find the maximum flow from $S$ to $T$.
\includegraphics[max width=\textwidth, alt={}, center]{b3a3d522-2ec9-46ec-bd99-a8c698e3d1c0-6_969_1363_459_351}

How many litres per second are currently flowing along the route SACHT?
How many litres per second are currently flowing from $S$ to $T$ ?
What is the maximum by which the flow along the route SBGIT can be increased? Use the copy of the network in your answer book to show what happens to the labels on the arrows when the flow along this route is augmented by this amount.
Find the maximum amount that can flow through the network. Explain, by using a cut, how you know that your flow is a maximum. The network had vertices $S , A , B , C , D , E , F , G , H , I$ and $T$. The single vertex $E$ is replaced by the pair of vertices $E _ { 1 }$ and $E _ { 2 }$, together with the $\operatorname { arc } E _ { 1 } E _ { 2 }$.
What does the $\operatorname { arc }$ joining $E _ { 1 }$ and $E _ { 2 }$ tell you about the flow at $E$ ?
Complete the diagram in your answer book to show the flow resulting after part (iii) on a directed network with vertices $S , A , B , C , D , E , F , G , H , I$ and $T$.

OCR D2 2015 June Q6

6 At the final battle in a war game, the two opposing armies, led by General Rose, $R$, and Colonel Cole, $C$, are facing each other across a wide river. Each army consists of four divisions. The commander of each army needs to send some of his troops North and send the rest South. Each commander has to decide how many divisions (1,2 or 3) to send North. Intelligence information is available on the number of thousands of soldiers that each army can expect to have remaining with each combination of strategies. Thousands of soldiers remaining in $R$ 's army $C$ 's choice
$R$ 's choice

	1	2	3
1	15	25	30
2	20	50	15
3	30	35	15

Thousands of soldiers remaining in $C$ 's army
$C$ 's choice
$R$ 's choice

	1	2	3
1	20	35	10
2	15	50	20
3	10	25	40

Construct a table to show the number of thousands of soldiers remaining in $R$ 's army minus the number of thousands of soldiers remaining in $C$ 's army (the excess for $R$ 's army) for each combination of strategies. The commander whose army has the greatest positive excess of soldiers remaining at the end of the game will be declared the winner.
Explain the meaning of the value in the top left cell of your table from part (i) (where each commander chooses strategy 1). Hence explain why this table may be regarded as representing a zero-sum game.
Find the play-safe strategy for $R$ and the play-safe strategy for $C$. If $C$ knows that $R$ will choose his play-safe strategy, which strategy should $C$ choose? One of the strategies is redundant for one of the commanders, because of dominance.
Draw a table for the reduced game, once the redundant strategy has been removed. Label the rows and columns to show how many divisions have been sent North. A mixed strategy is to be employed on the resulting reduced game. This leads to the following LP problem:
Maximise $\quad M = m - 25$
Subject to $\quad m \leqslant 15 x + 25 y + 35 z$
$m \leqslant 45 x + 20 y$
$x + y + z \leqslant 1$
and
Interpret what $x , y$ and $z$ represent and show how $m \leqslant 15 x + 25 y + 35 z$ was formed. A computer runs the Simplex algorithm to solve this problem. It gives $x = 0.5385 , y = 0$ and $z = 0.4615$.
Describe how this solution should be interpreted, in terms of how General Rose chooses where to send his troops. Calculate the optimal value for $M$ and explain its meaning. Elizabeth does not have access to a computer. She says that at the solution to the LP problem $15 x + 25 y + 35 z$ must equal $45 x + 20 y$ and $x + y + z$ must equal 1 . This simplifies to give $y + 7 z = 6 x$ and $x + y + z = 1$.
Explain why there can be no valid solution of $y + 7 z = 6 x$ and $x + y + z = 1$ with $x = 0$. Elizabeth tries $z = 0$ and gets the solution $x = \frac { 1 } { 7 }$ and $y = \frac { 6 } { 7 }$.
Explain why this is not a solution to the LP problem.

OCR D2 2016 June Q1

1 Josh is making a calendar. He has chosen six pictures, each of which will represent two months in the calendar. He needs to choose which picture to use for each two-month period. The bipartite graph in Fig. 1 shows for which months each picture is suitable. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_497_1246_488_415} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} Initially Josh chooses the sailing ships for March/April, the sunset for July/August, the snow scene for November/December and the swans for May/June. This incomplete matching is shown in Fig. 2 below. \begin{table}[h]

Sailing ships	(1)			January/February
Seascape	(2)	• ◯	(MA)	March/April
Snow scene	(3)	\includegraphics[max width=\textwidth, alt={}]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_54_381_1451_716}	(MJ)	May/June
Street scene		\includegraphics[max width=\textwidth, alt={}]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_59_38_1536_712}	(JA)	July/August
Sunset	(5)		(SO)	September/October
Swans	(6)		(ND)	November/December

\captionsetup{labelformat=empty} \caption{Fig. 2}

\end{table}

Write down the shortest possible alternating path that starts at (JF) and finishes at either (2) or (4). Hence write down a matching that only excludes (SO) and one of the pictures.
Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at (SO) and finishes at whichever of (2) and (4) has still not been matched. Hence write down a complete matching between the pictures and the months.
Explain why three of the arcs in Fig. 1 must appear in the graph of any complete matching. Hence find a second complete matching.

OCR D2 2016 June Q2

2 Water flows through pipes from an underground spring to a tap. The size of each pipe limits the amount that can flow. Valves restrict the direction of flow. The pipes are modelled as a network of directed arcs connecting a source at $S$ to a sink at $T$. Arc weights represent the (upper) capacities, in litres per second. Pipes may be empty. Fig. 3 shows a flow of 5 litres per second from $S$ to $T$. Fig. 4 shows the result of applying the labelling procedure to the network with this flow. The arrows in the direction of potential flow show excess capacities (how much more could flow in the arc, in that direction) and the arrows in the opposite direction show potential backflows (how much less could flow in the arc). \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{490ff276-6639-40a1-bffb-dc6967f3ab21-3_524_876_717_141} \captionsetup{labelformat=empty} \caption{Fig. 3}

\end{figure} \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{490ff276-6639-40a1-bffb-dc6967f3ab21-3_524_878_717_1046} \captionsetup{labelformat=empty} \caption{Fig. 4}

\end{figure}

Write down the capacity of $\operatorname { arc } F T$ and of $\operatorname { arc } D T$. Find the value of the cut that separates the vertices $S , A , B , C , D , E , F$ from the sink at $T$.
(a) Update the excess capacities and the potential backflows to show an additional flow of 2 litres per second along $S - C - B - F - T$.
(b) Write down a further flow augmenting route and the amount by which the flow can be augmented. You do not need to update the excess capacities and potential backflows a second time.
Show the flow that results from part (ii)(b) and find a cut that has the same value as your flow.

OCR D2 2016 June Q3

3 A theatre company needs to employ three technicians for a performance. One will operate the lights, one the sound system and one the flying trapeze mechanism. Four technicians have applied for these tasks. The table shows how much it will cost the theatre company, in £, to employ each technician for each task.

\multirow{2}{*}{}		Task
		Lighting	Sound	Trapeze
\multirow{4}{*}{Technician}	Amir	86	88	90
	Bex	92	94	95
	Caz	88	92	94
	Dee	98	100	98

The theatre company wants to employ the three technicians for whom the total cost is least.
The Hungarian algorithm is to be used to find the minimum cost allocation, but before this can be done the table needs to be modified.

Make the necessary modification to the table. Working from your modified table, construct a reduced cost matrix by first reducing rows and then reducing columns. You should show the amount by which each row has been reduced in the row reductions and the amount by which each column has been reduced in the column reductions. Cross through the 0 's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [You must ensure that the values in your table can still be read.]
Complete the application of the Hungarian algorithm to find a minimum cost allocation. Write a list showing which technician should be employed for each task. Calculate the total cost to the theatre company. Although Amir put in the lowest cost for operating the lighting, you should have found that he has not been allocated this task. Amir is particularly keen to be employed to operate the lights so is prepared to reduce his cost for this task.
Find a way to use two of Bex, Caz and Dee to operate the sound effects and the flying trapeze mechanism at the lowest cost. Hence find what Amir's new cost should be for the minimum total cost to the theatre company to be exactly $\pounds 1$ less than your answer from part (ii).

OCR D2 2016 June Q4

4 Rowan and Colin are playing a game of 'scissors-paper-rock'. In each round of this game, each player chooses one of scissors ( $\$$ ), paper ( $\square$ ) or rock ( $\bullet$ ). The players reveal their choices simultaneously, using coded hand signals. Rowan and Colin will play a large number of rounds. At the end of the game the player with the greater total score is the winner. The rules of the game are that scissors wins over paper, paper wins over rock and rock wins over scissors. In this version of the game, if a player chooses scissors they will score $+ 1,0$ or - 1 points, according to whether they win, draw or lose, but if they choose paper or rock they will score $+ 2,0$ or - 2 points. This gives the following pay-off tables.
\includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_476_773_667_239}
\includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_478_780_667_1071}

Use an example to show that this is not a zero-sum game.
Write down the minimum number of points that Rowan can win using each strategy. Hence find the strategy that maximises the minimum number of points that Rowan can win. Rowan decides to use random numbers to choose between the three strategies, choosing scissors with probability $p$, paper with probability $q$ and rock with probability $( 1 - p - q )$.
Find and simplify, in terms of $p$ and $q$, expressions for the expected number of points won by Rowan for each of Colin's possible choices. Rowan wants his expected winnings to be the same for all three of Colin's possible choices.
Calculate the probability with which Rowan should play each strategy.

OCR D2 2016 June Q5

5 The network below represents a project using activity on arc. The durations of the activities are not yet shown.
\includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-6_597_1257_340_386}

If $C$ were to turn out to be a critical activity, which two other activities would be forced to be critical?
Complete the table, in the Answer Book, to show the immediate predecessor(s) for each activity. In fact, $C$ is not a critical activity. Table 1 lists the activities and their durations, in minutes. \begin{table}[h]
Activity $A$ $B$ $C$ $D$ $E$ $F$ $G$ $H$ $I$ $J$
Duration 10 15 10 5 15 5 10 15 5 15
\captionsetup{labelformat=empty} \caption{Table 1}
\end{table}
Carry out a forward pass and a backward pass through the activity network, showing the early event time and late event time at each vertex of the network. State the minimum project completion time and list the critical activities. Each activity requires one person.
Draw a schedule to show how three people can complete the project in the minimum time, with each activity starting at its earliest possible time. Each box in the Answer Book represents 5 minutes. For each person, write the letter of the activity they are doing in each box, or leave the box blank if the person is resting for those 5 minutes.
Show how two people can complete the project in the minimum time. It is required to reduce the project completion time by 10 minutes. Table 2 lists those activities for which the duration could be reduced by 5 minutes, and the cost of making each reduction. \begin{table}[h]
Activity $A$ $B$ $C$ $E$ $G$ $H$ $J$
Cost $( \pounds )$ 200 400 100 600 100 500 500
New duration 5 10 5 10 5 10 10
\captionsetup{labelformat=empty} \caption{Table 2}
\end{table}
Explain why the cost of saving 5 minutes by reducing activity $A$ is more than $\pounds 200$. Find the cheapest way to complete the project in a time that is 10 minutes less than the original minimum project completion time. State which activities are reduced and the total cost of doing this.

OCR D2 2016 June Q6

6 The table below shows an incomplete dynamic programming tabulation to solve a maximum path problem.

Stage	State	Action	Working	Suboptimal maximum
\multirow[t]{2}{*}{3}	0	0	1	1
	1	0	2	2
\multirow[t]{4}{*}{2}	\multirow[t]{2}{*}{0}	0	$1 + 1 = 2$	\multirow[b]{2}{*}{3}
		1	$1 + 2 = 3$
	\multirow[t]{2}{*}{1}	0	$3 + 1 = 4$	\multirow[t]{2}{*}{4}
		1	$1 + 2 = 3$
\multirow[t]{4}{*}{1}	\multirow[t]{2}{*}{0}	0	$1 + =$	\multirow{4}{*}{}
		1	$0 + =$
	\multirow[t]{2}{*}{1}	0	$0 + =$
		1	$1 + =$
\multirow[t]{2}{*}{0}	\multirow[t]{2}{*}{0}	0	$2 + =$	\multirow{2}{*}{}
		1	$2 + =$

Complete the working and suboptimal maximum columns on the copy of the table in your Answer Book. Write down the weight of the maximum path and the corresponding route. Give your route using (stage; state) variables. Ken has entered a cake-making competition. The actions in the dynamic programming tabulation above represent the different types of cake that Ken could make. Each competitor must make one cake in each stage of the competition. The rules of the competition mean that, for each competitor, the actions representing their four cakes must form a route from $( 0 ; 0 )$ to $( 4 ; 0 )$. The weights in the tabulation are the number of points that Ken can expect to get by making each of the cakes. Each cake is also judged for how well it has been decorated. The number of points that Ken expects to get for decorating each cake is shown below. Ken is not very good at decorating the cakes. He expects to get 0 points for decorating for the cakes that are not listed below.
Cake (0; 0) to (1; 0) (1; 0) to (2; 1) (1; 1) to (2; 0) (2; 0) to (3; 0) (2; 0) to (3; 1) (2; 1) to (3; 0) (2; 1) to (3; 1)
Decorating points 1 1 2 1 1 1 1
Calculate the number of decorating points that Ken can expect if he makes the cakes given in the solution to part (i). When Ken meets the other competitors he realises that he is not good enough to win the competition, so he decides instead to try to win the judges' special award. For each cake, the absolute difference between the score for cake-making and the score for decorating is calculated. The award is given to the person whose biggest absolute difference is least. (Note: to find the absolute difference, calculate larger number-smaller number, or 0 if they are the same.)
Draw the graph that the dynamic programming tabulation represents. Label the vertices using (stage; state) labels with $( 0 ; 0 )$ at the left hand side and $( 4 ; 0 )$ at the right hand side. Make the graph into a network by weighting the arcs with the absolute differences.
Use a dynamic programming tabulation to find the minimax route for the absolute differences.

OCR D2 Specimen Q1

1 [Answer this question on the insert provided.]
Six neighbours have decided to paint their houses in bright colours. They will each use a different colour.

Arthur wants to use lavender, orange or tangerine.
Bridget wants to use lavender, mauve or pink.
Carlos wants to use pink or scarlet.
Davinder wants to use mauve or pink.
Eric wants to use lavender or orange.
Ffion wants to use mauve.

Arthur chooses lavender, Bridget chooses mauve, Carlos chooses pink and Eric chooses orange. This leaves Davinder and Ffion with colours that they do not want.

Draw a bipartite graph on the insert, showing which neighbours ( $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }$ ) want which colours (L, M, O, P, S, T). On a separate diagram on the insert, show the incomplete matching described above.
By constructing alternating paths obtain the complete matching between the neighbours and the colours. Give your paths and show your matching on the insert.
Fill in the table on the insert to show how the Hungarian algorithm could have been used to find the complete matching. (You do not need to carry out the Hungarian algorithm.)

OCR D2 Specimen Q2

2 A company has organised four regional training sessions to take place at the same time in four different cities. The company has to choose four of its five trainers, one to lead each session. The cost ( $\pounds 1000$ 's) of using each trainer in each city is given in the table.

\multirow{7}{*}{Trainer}	\multirow{2}{*}{}	City
		London	Glasgow	Manchester	Swansea
	Adam	4	3	2	4
	Betty	3	5	4	2
	Clive	3	6	3	3
	Dave	2	6	4	3
	Eleanor	2	5	3	4

Convert this into a square matrix and then apply the Hungarian algorithm, reducing rows first, to allocate the trainers to the cities at minimum cost.
Betty discovers that she is not available on the date set for the training. Find the new minimum cost allocation of trainers to cities.

OCR D2 Specimen Q3

3 [Answer this question on the insert provided.]
A flying doctor travels between islands using small planes. Each flight has a weight limit that restricts how much he can carry. A plague has broken out on Farr Island and the doctor needs to take several crates of medical supplies to the island. The crates must be carried on the same planes as the doctor. The diagram shows a network with (stage; state) variables at the vertices representing the islands, arcs representing flight routes that can be used, and weights on the arcs representing the number of crates that the doctor can carry on each flight. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{09279013-7088-4db2-99dd-098b32fbcad7-03_506_1084_671_477} \captionsetup{labelformat=empty} \caption{Stage 0}

\end{figure} Stage 1 Stage 2

It is required to find the route from ( $0 ; 0$ ) to ( $3 ; 0$ ) for which the minimum number of crates that can be carried on any stage is a maximum (the maximin route). The insert gives a dynamic programming tabulation showing stages, states and actions, together with columns for working out the route minimum at each stage and for indicating the current maximin. Complete the table on the insert sheet and hence find the maximin route and the maximum number of crates that can be carried.
It is later found that the number of crates that can be carried on the route from ( $2 ; 0$ ) to ( $3 ; 0$ ) has been recorded incorrectly and should be 15 instead of 5 . What is the maximin route now, and how many crates can be carried?

OCR D2 Specimen Q4

4 Henry is planning a surprise party for Lucinda. He has left the arrangements until the last moment, so he will hold the party at their home. The table below lists the activities involved, the expected durations, the immediate predecessors and the number of people needed for each activity. Henry has some friends who will help him, so more than one activity can be done at a time.

Activity	Duration (hours)	Preceded by	Number of people
A: Telephone other friends	2	-	3
$B$ : Buy food	1	A	2
C: Prepare food	4	B	5
D: Make decorations	3	A	3
$E$ : Put up decorations	1	D	3
$F$ : Guests arrive	1	C, E	1

Draw an activity network to represent these activities and the precedences. Carry out forward and reverse passes to determine the minimum completion time and the critical activities. If Lucinda is expected home at 7.00 p.m., what is the latest time that Henry or his friends can begin telephoning the other friends?
Draw a resource histogram showing time on the horizontal axis and number of people needed on the vertical axis, assuming that each activity starts at its earliest possible start time. What is the maximum number of people needed at any one time?
Now suppose that Henry’s friends can start buying the food and making the decorations as soon as the telephoning begins. Construct a timetable, with a column for 'time' and a column for each person, showing who should do which activity when, in order than the party can be organised in the minimum time using a total of only six people (Henry and five friends). When should the telephoning begin with this schedule?

OCR D2 Specimen Q5

5 [Answer this question on the insert provided.]
Fig. 1 shows a directed flow network. The weight on each arc shows the capacity in litres per second. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{09279013-7088-4db2-99dd-098b32fbcad7-05_620_1082_424_502} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure}

Find the capacity of the cut $\mathscr { C }$ shown.
Deduce that there is no possible flow from $S$ to $T$ in which both arcs leading into $T$ are saturated. Explain your reasoning clearly. Fig. 2 shows a possible flow of 160 litres per second through the network. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{09279013-7088-4db2-99dd-098b32fbcad7-05_499_1084_1471_500} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure}
On the diagram in the insert, show the excess capacities and potential backflows for this flow.
Use the labelling procedure to augment the flow as much as possible. Show your working clearly, but do not obscure your answer to part (iii).
Show the final flow that results from part (iv). Explain clearly how you know that this flow is maximal.

OCR D2 Specimen Q6

6 Rose is playing a game against a computer. Rose aims a laser beam along a row, $A , B$ or $C$, and, at the same time, the computer aims a laser beam down a column, $X , Y$ or $Z$. The number of points won by Rose is determined by where the two laser beams cross. These values are given in the table. The computer loses whatever Rose wins.

	Computer
\cline { 2 - 5 }		$X$	$Y$	$Z$
\cline { 2 - 5 } Rose	$A$	1	3	4
$B$	4	3	2
$C$	3	2	1
\cline { 2 - 5 }

Find Rose's play-safe strategy and show that the computer's play-safe strategy is $Y$. How do you know that the game does not have a stable solution?
Explain why Rose should never choose row $C$ and hence reduce the game to a $2 \times 3$ pay-off matrix.
Rose intends to play the game a large number of times. She decides to use a standard six-sided die to choose between row $A$ and row $B$, so that row $A$ is chosen with probability $a$ and row $B$ is chosen with probability $1 - a$. Show that the expected pay-off for Rose when the computer chooses column $X$ is $4 - 3 a$, and find the corresponding expressions for when the computer chooses column $Y$ and when it chooses column $Z$. Sketch a graph showing the expected pay-offs against $a$, and hence decide on Rose's optimal choice for $a$. Describe how Rose could use the die to decide whether to play $A$ or $B$. The computer is to choose $X , Y$ and $Z$ with probabilities $x , y$ and $z$ respectively, where $x + y + z = 1$. Graham is an AS student studying the D1 module. He wants to find the optimal choices for $x , y$ and $z$ and starts off by producing a pay-off matrix for the computer.
Graham produces the following pay-off matrix.
3 1 0
0 1 2
Write down the pay-off matrix for the computer and explain what Graham did to its entries to get the values in his pay-off matrix.
Graham then sets up the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = p - 4 ,
\text { subject to } & p - 3 x - y \leqslant 0 ,
& p - y - 2 z \leqslant 0 ,
& x + y + z \leqslant 1 ,
\text { and } & p \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$ The Simplex algorithm is applied to the problem and gives $x = 0.4$ and $y = 0$. Find the values of $z , p$ and $P$ and interpret the solution in the context of the game. \href{http://physicsandmathstutor.com}{physicsandmathstutor.com}

OCR MEI D2 2005 June Q1

1 The switching circuit in Fig. 1.1 shows switches, $s$ for a car's sidelights, $h$ for its dipped headlights and f for its high-intensity rear foglights. It also shows the three sets of lights. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{ab28be76-9329-41c8-90fe-ff1bdb28f788-2_284_917_404_580} \captionsetup{labelformat=empty} \caption{Fig. 1.1}

\end{figure} (Note: $s$ and $h$ are each "ganged" switches. A ganged switch consists of two connected switches sharing a single switch control, so that both are either on or off together.)

1. Describe in words the conditions under which the foglights will come on. Fig. 1.2 shows a combinatorial circuit. \begin{figure}[h]
  \includegraphics[alt={},max width=\textwidth]{ab28be76-9329-41c8-90fe-ff1bdb28f788-2_367_1235_1183_431} \captionsetup{labelformat=empty} \caption{Fig. 1.2}
  \end{figure}
2. Write the output in terms of a Boolean expression involving $s , h$ and $f$.
3. Use a truth table to prove that $\mathrm { s } \wedge \mathrm { h } \wedge \mathrm { f } = \sim ( \sim \mathrm { s } \vee \sim \mathrm { h } ) \wedge \mathrm { f }$.
A car's first gear can be engaged ( g ) if either both the road speed is low ( r ) and the clutch is depressed ( d ), or if both the road speed is low ( r ) and the engine speed is the correct multiple of the road speed (m).
1. Draw a switching circuit to represent the conditions under which first gear can be engaged. Use two ganged switches to represent $r$, and single switches to represent each of $\mathrm { d } , \mathrm { m }$ and g .
2. Draw a combinatorial circuit to represent the Boolean expression $\mathrm { r } \wedge ( \mathrm { d } \vee \mathrm { m } ) \wedge \mathrm { g }$.
3. Use Boolean algebra to prove that $\mathrm { r } \wedge ( \mathrm { d } \vee \mathrm { m } ) \wedge \mathrm { g } = ( ( \mathrm { r } \wedge \mathrm { d } ) \vee ( \mathrm { r } \wedge \mathrm { m } ) ) \wedge \mathrm { g }$.
4. Draw another switching circuit to represent the conditions under which first gear can be selected, but without using a ganged switch.

OCR MEI D2 2005 June Q2

2 Karl is considering investing in a villa in Greece. It will cost him 56000 euros ( € 56000 ). His alternative is to invest his money, $\pounds 35000$, in the United Kingdom. He is concerned with what will happen over the next 5 years. He estimates that there is a $60 \%$ chance that a house currently worth $€ 56000$ will appreciate to be worth $€ 75000$ in that time, but that there is a $40 \%$ chance that it will be worth only $€ 55000$. If he invests in the United Kingdom then there is a $50 \%$ chance that there will be $20 \%$ growth over the 5 years, and a $50 \%$ chance that there will be $10 \%$ growth.

Given that $\pounds 1$ is worth $€ 1.60$, draw a decision tree for Karl, and advise him what to do, using the EMV of his investment (in thousands of euros) as his criterion. In fact the $\pounds / €$ exchange rate is not fixed. It is estimated that at the end of 5 years, if there has been $20 \%$ growth in the UK then there is a $70 \%$ chance that the exchange rate will stand at 1.70 euros per pound, and a $30 \%$ chance that it will be 1.50 . If growth has been $10 \%$ then there is a $40 \%$ chance that the exchange rate will stand at 1.70 and a $60 \%$ chance that it will be 1.50 .
Produce a revised decision tree incorporating this information, and give appropriate advice. A financial analyst asks Karl a number of questions to determine his utility function. He estimates that for $x$ in cash (in thousands of euros) Karl's utility is $x ^ { 0.8 }$, and that for $y$ in property (in thousands of euros), Karl's utility is $y ^ { 0.75 }$.
Repeat your computations from part (ii) using utility instead of the EMV of his investment. Does this change your advice?
Using EMVs, find the exchange rate (number of euros per pound) which will make Karl indifferent between investing in the UK and investing in a villa in Greece.
Show that, using Karl's utility function, the exchange rate would have to drop to 1.277 euros per pound to make Karl indifferent between investing in the UK and investing in a villa in Greece.

OCR MEI D2 2005 June Q3

3 The distance and route matrices shown in Fig. 3.1 are the result of applying Floyd's algorithm to the incomplete network on 4 vertices shown in Fig. 3.2. Distance Matrix \begin{center} \begin{tabular}{ | c | c | c | c | c | } \multicolumn{1}{l}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$
\hline $\mathbf { 1 }$ & 4 & 2 & 3 & 9
\hline $\mathbf { 2 }$ & 2 & 2 & $\mathbf { 1 }$ & 7
\hline $\mathbf { 3 }$ & 3 & $\mathbf { 1 }$ & 2 & 6
\hline

OCR MEI D2 2005 June Q4

$\mathbf { 4 }$ & 9 & 7 & 6 & 12
\hline \end{tabular} \end{center} Route Matrix

	$\mathbf { 1 }$	$\mathbf { 2 }$	$\mathbf { 3 }$	$\mathbf { 4 }$
$\mathbf { 1 }$	2	2	2	2
$\mathbf { 2 }$	$\mathbf { 1 }$	3	3	3
$\mathbf { 3 }$	2	2	2	4
$\mathbf { 4 }$	3	3	3	3

Fig. 3.1 \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{ab28be76-9329-41c8-90fe-ff1bdb28f788-4_296_310_918_904} \captionsetup{labelformat=empty} \caption{Fig. 3.2}

\end{figure}

Draw the complete network of shortest distances.
Explain how to use the route matrix to find the shortest route from vertex 4 to vertex 1 in the original incomplete network. A new vertex, vertex 5, is added to the original network. Its distances from vertices to which it is connected are shown in Fig. 3.3. \begin{table}[h]
\cline { 2 - 5 } \multicolumn{1}{c|}{} 1 2 3 4
5 - 3 - 1
\captionsetup{labelformat=empty} \caption{Fig. 3.3}
\end{table}
Draw the extended network and the complete 5 -node network of shortest distances. (You are not required to use an algorithm to find the shortest distances.)
Produce the shortest distance matrix and the route matrix for the extended 5-node network.
Apply the nearest neighbour algorithm to your $5 \times 5$ distance matrix, starting at vertex 1. Give the length of the cycle produced, together with the actual cycle in the original 5-node network.
By deleting vertex 1 and its arcs, and by using Prim's algorithm on the reduced distance matrix, produce a lower bound for the solution to the practical travelling salesperson problem in the original 5-node network. Show clearly your use of the matrix form of Prim's algorithm.
In the original 5-node network find a shortest route starting at vertex $\mathbf { 1 }$ and using each of the 6 arcs at least once. Give the length of your route. 4 Kassi and Theo are discussing how much oil and how much vinegar to use to dress their salad. They agree to use between 5 and 10 ml of oil and between 3 and 6 ml of vinegar and that the amount of oil should not exceed twice the amount of vinegar. Theo prefers to have more oil than vinegar. He formulates the following problem to maximise the proportion of oil: $$\begin{array} { l c } \text { Maximise } & \frac { x } { x + y }
\text { subject to } & 0 \leqslant x \leqslant 10 ,
& 0 \leqslant y \leqslant 6 ,
& x - 2 y \leqslant 0 . \end{array}$$
Explain why this problem is not an LP.
Use the simplex method to solve the following LP. $$\begin{array} { l c } \text { Maximise } & x - y
\text { subject to } & 0 \leqslant x \leqslant 10
& 0 \leqslant y \leqslant 6
& x - 2 y \leqslant 0 \end{array}$$
Kassi prefers to have more vinegar than oil. She formulates the following LP. $$\begin{array} { l l } \text { Maximise } & y - x
\text { subject to } & 5 \leqslant x \leqslant 10 ,
& 3 \leqslant y \leqslant 6 ,
& x - 2 y \leqslant 0 . \end{array}$$ Draw separate graphs to show the feasible regions for this problem and for the problem in part (ii).
Explain why the formulation in part (ii) produced a solution for Theo's problem, and why it is more difficult to use the simplex method to solve Kassi's problem in part (iii).
Produce an initial tableau for using the two-stage simplex method to solve Kassi's problem. Explain briefly how to proceed.

OCR MEI D2 2006 June Q1

Use a truth table to prove $\sim ( \sim \mathrm { T } \Rightarrow \sim \mathrm { S } ) \Leftrightarrow ( \sim \mathrm { T } \wedge \mathrm { S } )$.
Prove that $( \mathrm { A } \Rightarrow \mathrm { B } ) \Leftrightarrow ( \sim \mathrm { A } \vee \mathrm { B } )$ and hence use Boolean algebra to prove that $$\sim ( \sim \mathrm { T } \Rightarrow \sim \mathrm {~S} ) \Leftrightarrow ( \sim \mathrm { T } \wedge \mathrm {~S} ) .$$
A teacher wrote on a report "It is not the case that if Joanna doesn't try then she won't succeed." He meant to say that if Joanna were to try then she would have a chance of success. By letting T be "Joanna will try" and S be "Joanna will succeed", find the real meaning of what the teacher wrote.

OCR MEI D2 2006 June Q3

3 Emma has won a holiday worth $\pounds 1000$. She is wondering whether or not to take out an insurance policy which will pay out $\pounds 1000$ if she should fall ill and be unable to go on the holiday. The insurance company tells her that this happens to 1 in 200 people. The insurance policy costs $\pounds 10$. Thus Emma's monetary value if she buys the insurance and does not fall ill is $\pounds 990$.

Draw a decision tree for Emma's problem. Use the EMV criterion in your calculations.
Interpret your tree and say what the maximum cost of the insurance would have to be for Emma to consider buying it if she uses the EMV criterion. Suppose that Emma's utility function is given by utility $= \sqrt [ 3 ] { \text { monetary value } }$.
Using expected utility as the criterion, should Emma purchase the insurance? Under this criterion what is the cost at which she will be indifferent to buying or not buying it? Emma could pay for a blood pressure check to help her to make her decision. Statistics show that $75 \%$ of checks are positive, and that when a check is positive the chance of missing a holiday through ill heath is 0.001 . However, when a check is negative the chance of cancellation through ill health is 0.017.
Draw a decision tree to help Emma decide whether or not to pay for the check. Use EMV, not expected utility, in your calculations and assume that the insurance policy costs $\pounds 10$. What is the maximum amount that she should pay for the blood pressure check?

OCR MEI D2 2006 June Q4

Explain how this formulation models the problem, and say why the analyst has not simplified the last inequality to $a + b + c \leqslant 15$.
The final constraint is different from the others in that the resource is integer valued. Explain why that does not impose an additional difficulty for this problem.
Solve this problem using the simplex algorithm. Interpret your solution and say what resources are left over. On a particular day an order is received for two Cuddly Cats, and the extra constraint $c \geqslant 2$ is added to the formulation.
Set up an initial simplex tableau to deal with the modified problem using either the big-M approach or two-phase simplex. Do not perform any iterations on your tableau.
Show that the solution given by $a = 8 , b = 2$ and $c = 5$ uses all of the resources, but that $a = 6 , b = 6$ and $c = 2$ gives more profit. What resources are left over from the latter solution?

OCR MEI D2 2007 June Q1

A joke has it that army recruits used to be instructed: "If it moves, salute it. If it doesn't move, paint it." Assume that this instruction has been carried out completely in the local universe, so that everything that doesn't move has been painted.
1. A recruit encounters something which is not painted. What should he do, and why?
2. A recruit encounters something which is painted. Do we know what he or she should do? Justify your answer.
Use a truth table to prove $( ( ( m \Rightarrow s ) \wedge ( \sim m \Rightarrow p ) ) \wedge \sim p ) \Rightarrow s$.
You are given the following two rules. $$\begin{aligned} & 1 \quad ( a \Rightarrow b ) \Leftrightarrow ( \sim b \Rightarrow \sim a )
& 2 \quad ( x \wedge ( x \Rightarrow y ) ) \Rightarrow y \end{aligned}$$ Use Boolean algebra to prove that $( ( ( m \Rightarrow s ) \wedge ( \sim m \Rightarrow p ) ) \wedge \sim p ) \Rightarrow s$.

OCR MEI D2 2007 June Q2

2 Bill is at a horse race meeting. He has $\pounds 2$ left with two races to go. He only ever bets $\pounds 1$ at a time. For each race he chooses a horse and then decides whether or not to bet on it. In both races Bill's horse is offered at "evens". This means that, if Bill bets $\pounds 1$ and the horse wins, then Bill will receive back his $\pounds 1$ plus $\pounds 1$ winnings. If Bill's horse does not win then Bill will lose his $\pounds 1$.

Draw a decision tree to model this situation. Show Bill's payoffs on your tree, i.e. how much money Bill finishes with under each possible outcome. Assume that in each race the probability of Bill's horse winning is the same, and that it has value $p$.
Find Bill's EMV when
(A) $p = 0.6$,
(B) $p = 0.4$. Give his best course of action in each case.
Suppose that Bill uses the utility function utility $= ( \text { money } ) ^ { x }$, to decide whether or not to bet $\pounds 1$ on one race. Show that, with $p = 0.4$, Bill will not bet if $x = 0.5$, but will bet if $x = 1.5$.

OCR MEI D2 2007 June Q3

3 Floyd's algorithm is applied to the following network:
\includegraphics[max width=\textwidth, alt={}, center]{483a681e-011a-464f-b7cb-007d894d1516-3_398_394_331_833} At the end of the third iteration of the algorithm the distance and route matrices are as follows: \begin{center} \begin{tabular}{ | c | c | c | c | c | } \cline { 2 - 5 } \multicolumn{1}{c|}{} & $\mathbf { 1 }$ & $\mathbf { 2 }$ & $\mathbf { 3 }$ & $\mathbf { 4 }$
\hline $\mathbf { 1 }$ & 6 & 3 & 10 & 5
\hline $\mathbf { 2 }$ & 3 & 6 & 7 & 2
\hline $\mathbf { 3 }$ & 10 & 7 & 14 & 1
\hline

Place	\(K\)	\(L\)	\(M\)	\(N\)	\(P\)	\(R\)	\(S\)	\(T\)
Stage variable	1	1	2	2	2	3	3	3
State variable	0	1	0	1	2	0	1	2

Activity	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)	\(I\)	\(J\)
Duration	10	15	10	5	15	5	10	15	5	15

	Computer
\cline { 2 - 5 }		\(X\)	\(Y\)	\(Z\)
\cline { 2 - 5 } Rose	\(A\)	1	3	4
\(B\)	4	3	2
\(C\)	3	2	1
\cline { 2 - 5 }

	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)
\(\mathbf { 1 }\)	2	2	2	2
\(\mathbf { 2 }\)	\(\mathbf { 1 }\)	3	3	3
\(\mathbf { 3 }\)	2	2	2	4
\(\mathbf { 4 }\)	3	3	3	3

Cake	(0; 0) to (1; 0)	(1; 0) to (2; 1)	(1; 1) to (2; 0)	(2; 0) to (3; 0)	(2; 0) to (3; 1)	(2; 1) to (3; 0)	(2; 1) to (3; 1)
Decorating points	1	1	2	1	1	1	1

Stage	State	Action	Working	Suboptimal maximum
\multirow[t]{2}{*}{3}	0	0	1	1
	1	0	2	2
\multirow[t]{4}{*}{2}	\multirow[t]{2}{*}{0}	0	\(1 + 1 = 2\)	\multirow[b]{2}{*}{3}
		1	\(1 + 2 = 3\)
	\multirow[t]{2}{*}{1}	0	\(3 + 1 = 4\)	\multirow[t]{2}{*}{4}
		1	\(1 + 2 = 3\)
\multirow[t]{4}{*}{1}	\multirow[t]{2}{*}{0}	0	\(1 + =\)	\multirow{4}{*}{}
		1	\(0 + =\)
	\multirow[t]{2}{*}{1}	0	\(0 + =\)
		1	\(1 + =\)
\multirow[t]{2}{*}{0}	\multirow[t]{2}{*}{0}	0	\(2 + =\)	\multirow{2}{*}{}
		1	\(2 + =\)

Questions D2 (547 questions)

Browse by module

Browse by board

OCR D2 2015 June Q4

OCR D2 2015 June Q5

OCR D2 2015 June Q6

OCR D2 2016 June Q1

OCR D2 2016 June Q2

OCR D2 2016 June Q3

OCR D2 2016 June Q4

OCR D2 2016 June Q5

OCR D2 2016 June Q6

OCR D2 Specimen Q1

OCR D2 Specimen Q2

OCR D2 Specimen Q3

OCR D2 Specimen Q4

OCR D2 Specimen Q5

OCR D2 Specimen Q6

OCR MEI D2 2005 June Q1

OCR MEI D2 2005 June Q2

OCR MEI D2 2005 June Q3

OCR MEI D2 2005 June Q4

OCR MEI D2 2006 June Q1

OCR MEI D2 2006 June Q3

OCR MEI D2 2006 June Q4

OCR MEI D2 2007 June Q1

OCR MEI D2 2007 June Q2

OCR MEI D2 2007 June Q3