Questions - OCR D2 - A-Level Maths

Calculate how many minutes it takes to travel the route $$( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 4 ) - ( 5 ; 0 ) .$$ The friends then realise that if they try to find the quickest route using dynamic programming with this (stage; state) formulation, they will get the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$, or this in reverse, taking 27 minutes.
Explain why the route $( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )$ is not a solution to the friends' problem. Instead, the friends set up a dynamic programming tabulation with stages and states as described above, except that now the states also show, in brackets, any birds that have already been visited. So, for example, state $1 ( 234 )$ means that they are currently visiting the kite and have already visited the other three birds in some order. The partially completed dynamic programming tabulation is shown opposite.
For the last completed row, i.e. stage 2, state 1(3), action 4(13), explain where the value 18 and the value 6 in the working column come from.

Complete the table in the insert and hence find the order in which the birds should be visited to give a quickest route and find the corresponding minimum journey time.

Stage

State

$21 + 3 = 24 18 + 6 = 24$

OCR D2 2012 January Q1

1 Five film studies students need to review five different films for an assignment, but only have one evening left before the assignment is due in. They decide that they will share the work out so that each of them reviews just one film. Jack $( J )$ wants to review a horror movie; Karen $( K )$ wants to review an animated film; Lee $( L )$ wants to review a film that is suitable for family viewing; Mark ( $M$ ) wants to review an action adventure film and Nikki ( $N$ ) wants to review anything that is in 3D. The film "Somewhere" ( $S$ ) has been classified as a horror movie and is being shown in 3D; "Tornado Terror" ( $T$ ) has been classified as an action adventure film that is suitable for family viewing; "Underwater" $( U )$ is an animated action adventure film; "Vampires" ( $V$ ) is an animated horror movie that is suitable for family viewing and "World" ( $W$ ) is an animated film.

Draw a bipartite graph to show which student ( $J , K , L , M , N$ ) wants to review which films ( $S , T , U$, $V , W$ ). Initially Jack says that he will review "Somewhere", Karen then chooses "Underwater" and Lee chooses "Tornado Terror", but this would leave both Mark and Nikki with films that they do not want.
Write down the shortest possible alternating path starting from Nikki, and hence write down an improved, but still incomplete, matching.
From this incomplete matching, write down the shortest possible alternating path starting from "World", and hence write down a complete matching between the students and the films.
Show that this is the only possible complete matching between the students and the films.

OCR D2 2012 January Q2

2 The table lists the durations (in minutes), immediate predecessors and number of workers required for each activity in a project to decorate a room.

Activity	Duration (minutes)	Immediate predecessors	Number of workers
A Cover furniture with dust sheets	20	-	1
B Repair any cracks in the plaster	100	A	1
C Hang wallpaper	60	B	1
D Paint feature wall	90	B	1
$E$ Paint woodwork	120	C, D	1
$F$ Put up shelves	30	C	2
G Paint ceiling	60	A	1
$H$ Clean paintbrushes	10	$E , G$	1
I Tidy room	20	$F , H$	2

Draw an activity network, using activity on arc, to represent the project. Your network will require a dummy activity.
Carry out a forward pass and a backward pass through the activity network, showing the early event time and the late event time at each vertex of your network. State the minimum project completion time and list the critical activities.
Draw a resource histogram to show the number of workers required at each time when each activity begins at its earliest possible start time. Suppose that there is only one worker available at the start of the project, but another two workers are available later.
Find the latest possible time for the other workers to start and still have the project completed on time. Which activities could happen at the same time as painting the ceiling if the other two workers arrive at this latest possible time?
[0pt] [Do not change your resource histogram from part (iii).]

OCR D2 2012 January Q3

3 The famous fictional detective Agatha Parrot has been called in to investigate the theft of some jewels. Each thief is known to have taken just one item of jewellery. Agatha has invented a scoring system based on motive, opportunity and past experience. The table shows the score for each of four suspects with each of three items of jewellery. The higher the score the more likely the suspect is to have stolen that item of jewellery. Suspect

	Pearl necklace	Ruby ring	Sapphire bracelet
Butler	80	100	20
Cook	40	35	60
Gardener	60	45	30
Handyman	20	100	80

Assuming that three of these four suspects are the thieves, find who is most likely to have stolen each item of jewellery for the total score to be maximised. State how each table of working was calculated. Write down the two possible solutions for who should be suspected of stealing each item of jewellery and who should be thought to be innocent. Further evidence shows that the butler stole the sapphire bracelet.
Using this additional information, find out which suspect should be thought to be innocent. Explain your reasoning.

OCR D2 2012 January Q4

4 The diagram represents a system of roads through which traffic flows from a source, $S$, to a sink, $T$. The weights on the arcs show the capacities of the roads in cars per minute.
\includegraphics[max width=\textwidth, alt={}, center]{3a47bac8-0067-4acb-a3c7-7d8512403cca-5_414_1080_349_488}

(a) The cut $\alpha$ partitions the vertices into the sets $\{ S , A , B , C \} , \{ D , E , F , T \}$. Calculate the capacity of cut $\alpha$.
(b) The cut $\beta$ partitions the vertices into the sets $\{ S , A , B , D \} , \{ C , E , F , T \}$. Calculate the capacity of cut $\beta$.
(c) Using only the capacities of cuts $\alpha$ and $\beta$, what can you deduce about the maximum possible flow through the system?
Explain why partitioning the vertices into sets $\{ S , A , D , T \} , \{ B , C , E , F \}$ does not give a cut.
What do the double arcs between $D$ and $E$ and between $E$ and $F$ represent?
Explain why the maximum possible flow along $C F$ must be less than 45 cars per minute.
(a) Show how a flow of 60 cars per minute along $F T$ can be achieved.
(b) Show that 60 cars per minute is the maximum possible flow through the system. An extra road is opened linking $S$ to $C$. Let the capacity of this road be $x$ cars per minute.
Find the maximum possible flow through the new system, in terms of $x$ where necessary, for the different possible values of $x$.

OCR D2 2012 January Q5

2 marks

5 Henry is doing a sponsored cycle ride for charity. He needs to finish at noon on Sunday. He can ride up to 50 miles each day, except Sunday when he can ride at most 20 miles if he is to finish on time. The total length of the ride is 95 miles so Henry has allowed 3 days for the ride. Henry will start his ride at $A$ and travel through $B , C , D$ and $E$, in that order, and finish on Sunday at $F$. He will stay overnight on Friday and Saturday at two of the places $B , C , D$ and $E$. The distances between the places along the route are: $$A - B = 30 \text { miles } , \quad B - C = 15 \text { miles } , \quad C - D = 35 \text { miles } , \quad D - E = 12 \text { miles } , \quad E - F = 3 \text { miles. }$$ To reach $F$ on Sunday he must have reached at least $D$ by Saturday night (since the distance from $D$ to $F$ is less than 20 miles but $C$ to $F$ is more than 20 miles.) Henry wants to use dynamic programming to minimise the maximum distance that he cycles on any day.
The stages will be the days. The places where Henry stays overnight will be the states. Henry starts on Friday morning at $A$ which has the (stage; state) label ( $0 ; 0$ ). On Friday night he can either stay at $B ( 1 ; 0 )$ or at $C ( 1 ; 1 )$. Depending on where he stays on Friday night, he can spend Saturday night at $D ( 2 ; 0 )$ or $E ( 2 ; 1 )$. On Sunday he arrives at $F ( 3 ; 0 )$.
[0pt]

Use this information and the table below to draw a network, labelled with stages and states, to show the possible transitions between states. The arc weights should be the distances between the states. [2] Henry uses dynamic programming, working backwards from stage 3, to find where he should stay overnight to give the route for which the maximum on any day is a minimum. His tabulation is shown below.

Stage	State	Action	Working	Suboptimal minimax
\multirow[t]{2}{*}{2}	0	0	15	15
	1	0	3	3
\multirow{3}{*}{1}	0	0	$\max ( 50,15 )$	50
	\multirow[t]{2}{*}{1}	0	$\max ( 35,15 )$	\multirow[t]{2}{*}{35}
		1	$\max ( 47,3 )$
\multirow[t]{2}{*}{0}	\multirow[t]{2}{*}{0}	0	$\max ( 30,50 )$	\multirow[b]{2}{*}{45}
		1	max(45, 35)

(a) In the last row of the table, the action value is 1 . Explain what this tells you.
(b) In the last row of the table, the working column is $\max ( 45,35 )$. Explain where each of the values 45 and 35 comes from and how they relate to the (stage; state) values for this row and for a row from the next stage.

Use the table to deduce where Henry should make his overnight stops to minimise the maximum distance that he cycles on any day. Explain how you obtained this solution from the table. Henry is so pleased with his ride that he decides to do a longer ride. Again he will cycle up to 50 miles each day, except the last day when he will cycle at most 20 miles. He wants to complete the ride in five days, and he wants to minimise the maximum distance that he rides on any one day. He will start at $A$ and travel through $B , C , D , E , F , G , H , I , J$ and $K$, in that order, and finish at $L$.
He will stay overnight on Wednesday, Thursday, Friday and Saturday at four of $B , C , D , E , F , G , H , I , J$ and $K$. The distances between the places along the route are:

$A - B = 30$ miles,	$B - C = 15$ miles,	$C - D = 35$ miles,	$D - E = 12$ miles,
$E - F = 3$ miles,	$F - G = 30$ miles,	$G - H = 10$ miles,	$H - I = 25$ miles,
$I - J = 10$ miles,	$J - K = 10$ miles,	$K - L = 5$ miles.

(a) Which is the furthest place from $L$ that Henry must reach by Saturday night if he is to finish on time?
(b) Work backwards to deduce the furthest place from $L$ that Henry must reach by Friday night, Thursday night and Wednesday night.
Find out where Henry could stay each night, and hence define appropriate states for each of stages 1, 2, 3 and 4 . (Note that not every place need correspond to a (stage; state) label.)
Set up a dynamic programming tabulation, working backwards from stage 5, to minimise the maximum distance that Henry must ride on any one day. Where should he make his overnight stops?

OCR D2 2012 January Q6

6 Rowena and Colin play a game in which each chooses a letter. The table shows how many points Rowena wins for each combination of letters. In each case the number of points that Colin wins is the negative of the entry in the table. Both Rowena and Colin are trying to win as many points as possible. Colin's letter \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Rowena's letter}

	$N$	$P$	$Q$	$T$
$W$	4	- 1	1	- 2
$X$	1	3	- 1	1
$Y$	5	1	2	- 1
$Z$	0	- 1	1	1

\end{table}

Write down Colin's play-safe strategy, showing your working. What is the maximum number of points that Colin can win if he plays safe?
Explain why Rowena would never choose the letter $W$. Rowena uses random numbers to choose between her three remaining options, so that she chooses $X , Y$ and $Z$ with probabilities $x , y$ and $z$, respectively. Rowena then models the problem of which letter she should choose as the following LP. $$\begin{array} { c l } \text { Maximise } & M = m - 1
\text { subject to } & m \leqslant 2 x + 6 y + z ,
& m \leqslant 4 x + 2 y ,
& m \leqslant 3 y + 2 z ,
& m \leqslant 2 x + 2 z ,
& x + y + z \leqslant 1
\text { and } & m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
Show how the expression $2 x + 6 y + z$ was formed. The Simplex algorithm is used to solve the LP problem. The solution has $x = 0.3 , y = 0.2$ and $z = 0.5$.
Show that the optimal value of $M$ is 0.6 . Colin then models the problem of which letter he should choose in a similar way. When Rowena plays using her optimal solution, from above, Colin finds that he should never choose the letter $N$. Letting $p , q$ and $t$ denote the probabilities that he chooses $P , Q$ and $T$, respectively, Colin obtains the following equations. $$- 3 p + q - t = - 0.6 \quad - p - 2 q + t = - 0.6 \quad p - q - t = - 0.6 \quad p + q + t = 1$$
Explain how the equation $- 3 p + q - t = - 0.6$ is obtained.
Use the third and fourth equations to find the value of $p$. Hence find the values of $q$ and $t$.

OCR D2 2013 January Q1

1 A TV soap opera has five main characters, Alice ( $A$ ), Bob ( $B$ ), Charlie ( $C$ ), Dylan ( $D$ ) and Etty ( $E$ ). A different character is scheduled to play the lead in each of the next five episodes. Alice, Dylan and Etty are all in the episode about the fire ( $F$ ), but Bob and Charlie are not. Alice and Bob are the only main characters in the episode about the gas leak ( $G$ ). Alice, Charlie and Etty are the only main characters in the episode about the house break-in (H). The episode about the icy path (I) stars Alice and Charlie only. The episode about the jail break ( $J$ ) does not star any of the main characters who were in the episodes about the fire or the house break-in.

Draw a bipartite graph to show which main characters ( $A , B , C , D , E$ ) are in which of the next five episodes $( F , G , H , I , J )$. The writer initially decides to make Alice play the lead in the episode about the fire, Bob in the episode about the gas leak and Charlie in the episode about the house break-in.
Write down the shortest possible alternating path starting from Dylan. Hence draw the improved, but still incomplete, matching that results.
From this incomplete matching, write down the shortest possible alternating path starting from the character who still has no leading part allocated. Hence draw the complete matching that results.
By starting with the episode about the jail break, explain how you know that this is the only possible complete matching between the characters and the episodes.

OCR D2 2013 January Q2

2 A project is represented by this activity network. The weights (in brackets) on the arcs represent activity durations, in minutes.
\includegraphics[max width=\textwidth, alt={}, center]{fc01c62e-64bd-4fbc-ac1e-cdfa47c07228-3_645_1235_356_415}

Complete the table in the answer book to show the immediate predecessors for each activity.
Carry out a forward pass and a backward pass through the activity network, showing the early event time and the late event time at each vertex of your network. State the minimum project completion time and list the critical activities. Suppose that the start of one activity is delayed by 2 minutes.
List each activity which could be delayed by 2 minutes with no change to the minimum project completion time.
Without altering your diagram from part (ii), state the effect that a delay of 2 minutes on activity $A$ would have on the minimum project completion time. Name another activity which could be delayed by 2 minutes, instead of $A$, and have the same effect on the minimum project completion time.
Without altering your diagram from part (ii), state what effect a delay of 2 minutes on activity $C$ would have on the minimum project completion time.

OCR D2 2013 January Q3

3 Agatha Parrot is in her garden and overhears her neighbours talking about four new people who have moved into her village. Each of the new people has a different job, and Agatha's neighbours are guessing who has which job. Using the information she has overheard, Agatha counts how many times she heard it guessed that each person has each job.

	Nurse	Police officer	Radiographer	Teacher
Jill Jenkins	7	8	8	8
Kevin Keast	8	4	5	7
Liz Lomax	5	1	0	4
Mike Mitchell	8	3	4	4

Agatha wants to find the allocation of people to jobs that maximises the total number of correct guesses. She intends to use the Hungarian algorithm to do this. She starts by subtracting each value in the table from 10.

Write down the table which Agatha gets after she has subtracted each value from 10. Explain why she did a subtraction.
Apply the Hungarian algorithm, reducing rows first, to find which job Agatha concludes each person has. State how each table of working was calculated from the previous one. Agatha later meets Liz Lomax and is surprised to find out that she is the radiographer.
Using this additional information, but without formally using the Hungarian algorithm, find which job Agatha should now conclude each person has. Explain how you know that there is no better solution in which Liz is the radiographer.

OCR D2 2013 January Q4

4 The diagram represents a system of pipes through which fluid can flow from two sources, $S _ { 1 }$ and $S _ { 2 }$, to a sink, $T$. Most of the pipes have valves which restrict the flow to one direction only. However, the flow in arc $D E$ can be in either direction. The weights on the arcs show the lower capacities and the upper capacities of the pipes in litres per second.
\includegraphics[max width=\textwidth, alt={}, center]{fc01c62e-64bd-4fbc-ac1e-cdfa47c07228-5_565_1130_447_463}

Add a supersource, $S$, to the copy of the diagram in the answer book, and weight the arcs attached to it with appropriate lower and upper capacities.
The cut $\alpha$ partitions the vertices into the sets $\left\{ S , S _ { 1 } , S _ { 2 } , A , C \right\} , \{ B , D , E , T \}$. By considering the cut arcs only, calculate the maximum and minimum capacities of cut $\alpha$.
Show that the maximum capacity of the cut $\left\{ S , S _ { 1 } , S _ { 2 } , A , E \right\} , \{ B , C , D , T \}$ is 47 litres per second. A flow is set up in which the arcs $S _ { 1 } A , S _ { 1 } B , S _ { 2 } C , A E , C E$ and $D T$ are all at their lower capacities.
Show the flow in each arc on the diagram in the answer book, indicating the direction of the flow in $\operatorname { arc } D E$.
What is the maximum amount, in litres per second, by which the flow can be augmented using the routes $S _ { 1 } A D T$ and $S _ { 2 } C E T$ ?
Find the maximum possible flow through the system, explaining how you know both that this is feasible and that it cannot be exceeded.

OCR D2 2013 January Q5

5 Rose and Colin are playing a game in which they each have four cards. Each player chooses a card from those in their hand, and simultaneously they show each other the cards they have chosen. The table below shows how many points Rose wins for each combination of cards. In each case the number of points that Colin wins is the negative of the entry in the table. Both Rose and Colin are trying to win as many points as possible.

		Colin's card
		$\circ$	$\square$	$\diamond$	$\triangle$
\cline { 2 - 6 }	$\bullet$	- 2	3	- 4	1
\cline { 2 - 6 } Rose's	$\square$	4	- 3	4	5
\cline { 2 - 6 } card	$\diamond$	2	- 5	- 2	- 1
\cline { 2 - 6 }	$\triangle$	- 6	5	- 5	- 3
\cline { 2 - 6 }

What is the greatest number of points that Colin can win when Rose chooses and which card does Colin need to choose to achieve this?
Explain why Rose should never choose and find the card that Colin should never choose. Hence reduce the game to a $3 \times 3$ pay-off matrix.
Find the play-safe strategy for each player on the reduced game and show whether or not the game is stable. Rose makes a random choice between her cards, choosing with probability $x$ with probability $y$, and with probability $z$. She formulates the following LP problem to be solved using the Simplex algorithm:
maximise $\quad M = m - 6$,
subject to $\quad m \leqslant 4 x + 10 y$,
$n \leqslant 9 x + 3 y + 11 z$,
$n \leqslant 2 x + 10 y + z$,
$x + y + z \leqslant 1$,
and
$x \geqslant 0 , y \geqslant 0 , z \geqslant 0 , m \geqslant 0$.
(You are not required to solve this problem.)
Explain how $9 x + 3 y + 11 z$ was obtained. The Simplex algorithm is used to solve the LP problem. The solution has $x = \frac { 7 } { 48 } , y = \frac { 27 } { 48 } , z = \frac { 14 } { 48 }$.
Calculate the optimal value of $M$.

OCR D2 2013 January Q6

6 Simon makes playhouses which he sells through an agent. Each Sunday the agent orders the number of playhouses she will need Simon to deliver at the end of each day. The table below shows the order for the coming week.

Simon can make up to 3 houses each day, except for Wednesday when he can make at most 2 houses. Because of limited storage space, Simon can store at most 2 houses overnight from one day to the next, although the number in store does not restrict how many houses Simon can make the next day. The process is modelled by letting the stages be the days and the states be the numbers of houses stored overnight. Simon starts the week, on Monday morning, with no houses in storage. This means that the start of Monday morning has (stage; state) label ( $0 ; 0$ ). Simon wants to end the week on Friday afternoon with no houses in storage, so the start of Saturday morning will have (stage; state) label ( $5 ; 0$ ).

Explain why the (stage; state) label ( $4 ; 0$ ) is not needed. Simon wants to draw up a production plan showing how many houses he needs to make each day. He prefers not to have to make several houses on the same day so he assigns a 'cost' that is the square of the number of houses made that day, apart from Monday when the 'cost' is the cube of the number of houses made. So, for example, if he makes 3 houses one day the cost is 9 units, unless it is Monday when the cost is 27 units.
Complete the diagram in the answer book to show all the possible production plans and weight the arcs with the costs. Simon wants to find a production plan that minimises the sum of the costs.
Set up a dynamic programming tabulation, working backwards from ( $5 ; 0$ ), to find a production plan that solves Simon's problem.
Write down the number of houses that he should make each day with this plan.

OCR D2 2005 June Q1

1 [Answer this question on the insert provided.]
The network below represents a system of pipelines through which fluid flows from $S$ to $T$. The capacities of the pipelines, in litres per second, are shown as weights on the arcs.
\includegraphics[max width=\textwidth, alt={}, center]{0403a37e-46dd-4346-afc6-e48a34417c48-2_863_1201_486_477}

Write down the arcs from $\{ S , A , C , E \}$ to $\{ B , D , F , T \}$. Hence find the capacity of the cut that separates $\{ S , A , C , E \}$ from $\{ B , D , F , T \}$.
On the diagram in the insert show the excess capacities and potential backflows when 5 litres per second flow along SADT and 6 litres per second flow along SCFT.
Give a flow-augmenting path of capacity 2 . On the second diagram in the insert show the new capacities and potential backflows.
Use the maximum flow - minimum cut theorem to show that the maximum flow from $S$ to $T$ is 13 litres per second.
$E B$ is replaced by a pipeline with capacity 2 litres per second from $B$ to $E$. Find the new maximum flow from $S$ to $T$. You should show the flow on the third diagram in the insert and explain how you know that this is a maximum.

OCR D2 2005 June Q2

2 A talent contest has five contestants. In the first round of the contest each contestant must sing a song chosen from a list. No two contestants may sing the same song. Adam (A) chooses to sing either song 1 or song 2; Bex (B) chooses 2 or 4; Chris (C) chooses 3 or 5; Denny (D) chooses 1 or 3; Emma (E) chooses 3 or 4.

Draw a bipartite graph to show this information. Put the contestants (A, B, C, D and E) on the left hand side and the songs ( $1,2,3,4$ and 5 ) on the right hand side. The contest organisers propose to give Adam song 1, Bex song 2 and Chris song 3.
Explain why this would not be a satisfactory way to allocate the songs.
Construct the shortest possible alternating path that starts from song 5 and brings Denny (D) into the allocation. Hence write down an allocation in which each of the five contestants is given a song that they chose.
Find a different allocation in which each of the five contestants is given a song that they chose. Emma is knocked out of the contest after the first round. In the second round the four remaining contestants have to act in a short play. They will each act a different character in the play, chosen from a list of five characters. The table below shows how suitable each contestant is for each character as a score out of 10 (where 0 means that the contestant is completely unsuitable and 10 means that they are perfect to play that character).
\multirow{2}{*}{} Character
Fire Chief Gardener Handyman Juggler King
Adam 4 9 7 0 7
Bex 6 8 3 8 0
Chris 7 4 5 2 7
Denny 6 6 2 7 1
The Hungarian Algorithm is to be used to find the matching with the greatest total score. Before the Hungarian Algorithm can be used, each score is subtracted from 10 and then a dummy row of zeroes is added at the bottom of the table.
Explain why the scores could not be used as given in the table and explain why a dummy row is needed.
Apply the Hungarian Algorithm, showing your working carefully, to match the contestants to characters.

OCR D2 2005 June Q3

3 The table lists the activities involved in preparing for a cycle ride, their expected durations and their immediate predecessors.

Activity	Duration (minutes)	Preceded by
A: Check weather	8	-
B: Get maps out	4	-
C: Make sandwiches	12	-
D: Check bikes over	20	$A$
E: Plan route	12	A, B
$F$ : Pack bike bags	4	A, B, $C$
G: Get bikes out ready	2	$D , E , F$
$H$ : Change into suitable clothes	12	E, F

Draw an activity network to represent the information in the table. Show the activities on the arcs and indicate the direction of each activity and dummy activity. You are advised to make your network quite large.
Carry out a forward pass and a backward pass to determine the minimum completion time for preparing for the ride. List the critical activities.
Construct a cascade chart, showing each activity starting at its earliest possible time. Two people, John and Kerry, are intending to go on the cycle ride. Activities $A , B , F$ and $G$ will each be done by just one person (either John or Kerry), but both are needed (at the same time) for activities $C , D$ and $E$. Also, each of John and Kerry must carry out activity $H$, although not necessarily at the same time. All timings and precedences in the original table still apply.
Draw up a schedule showing which activities are done by each person at which times in order to complete preparing for the ride in the shortest time possible. The schedule should have three columns, the first showing times in 4-minute intervals, the second showing which activities John does and the third showing which activities Kerry does.

OCR D2 2005 June Q4

4 Henry often visits a local garden to view the exotic and unusual plants. His brother Giles is coming to visit and Henry wants to plan a route through the garden that will enable Giles to see the maximum number of plants in travelling along five paths from the garden entrance to the exit. Henry has used a plan of the paths through the garden to label where sections of paths meet using (stage; state) labels. He labelled the garden entrance as ( $5 ; 0$ ) and the exit as ( $0 ; 0$ ). He then counted the numbers of plants along paths. These numbers are shown below.

Stage 5	(5;0) to (4;0): 6 plants (5;0) to (4;1): 8 plants
Stage 4	(4;0) to (3;0): 5 plants (4;0) to (3;1): 8 plants	(4;1) to (3;0): 7 plants (4;1) to (3;2): 5 plants
Stage 3	( $3 ; 0$ ) to ( $2 ; 1$ ): 8 plants (3;0) to (2;3): 6 plants	(3;1) to (2;0): 7 plants $( 3 ; 1 )$ to (2;2): 6 plants	(3;2) to (2;0): 7 plants (3;2) to (2;2): 6 plants ( $3 ; 2$ ) to ( $2 ; 3$ ): 8 plants
Stage 2	(2; 0) to (1; 0): 4 plants ( $2 ; 0$ ) to ( $1 ; 1$ ): 5 plants	(2; 1) to (1; 0): 6 plants	(2;2) to (1;1): 7 plants	(2;3) to (1;0): 5 plants (2;3) to (1;1): 6 plants
Stage 1	(1;0) to (0;0): 4 plants	(1; 1) to (0;0): 4 plants

Set up a dynamic programming tabulation to find the route through the garden that will enable Giles to see the maximum number of plants. Work backwards from stage 1 and show your calculations for each state. How many plants will Giles be able to see by following this route? Giles does not really like plants, so he ignores Henry's route and instead decides to take the route through the garden for which the maximum number of plants on any path is a minimum.
Which problem does Giles want to solve? Find a route through the garden on which no path has more than 6 plants. Explain how you know that there cannot be a route on which the maximum number of plants on a path is less than 6 . You do NOT need to draw the network and you do NOT need to use a dynamic programming tabulation to solve Giles' problem.

OCR D2 2007 June Q1

1 D aniel needs to clean four houses but only has one day in which to do it. He estimates that each house will take one day and so he has asked three professional cleaning companies to give him a quotation for cleaning each house. He intends to hire the three companies to clean one house each and he will clean the fourth house himself. The table below shows the quotations that Daniel was given by the three companies.

	House 1	House 2	House 3	House 4
Allclean	$\pounds 500$	$\pounds 400$	$\pounds 700$	$\pounds 600$
Brightenupp	$\pounds 300$	$\pounds 200$	$\pounds 400$	$\pounds 350$
Clean4U	$\pounds 500$	$\pounds 300$	$\pounds 750$	$\pounds 680$

Copy the table and add a dummy row to represent D aniel.
A pply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working and say how each matrix was formed.
Which house should Daniel ask each company to clean? Find the total cost of hiring the three companies.

OCR D2 2007 June Q2

2 The table gives the pay-off matrix for a zero-sum game between two players, A my and Bea. The values in the table show the pay-offs for A my.

	Bea
\cline { 3 - 5 }		Strategy X	Strategy Y	Strategy Z
\cline { 2 - 5 }	Strategy P	4	- 2	0
\cline { 2 - 5 } A my	Strategy Q	- 1	5	4
\cline { 2 - 5 }
\cline { 2 - 5 }

A my makes a random choice between strategies $\mathbf { P }$ and $Q$, choosing strategy $P$ with probability $p$ and strategy Q with probability $1 - \mathrm { p }$.

Write down and simplify an expression for the expected pay-off for Amy when Bea chooses strategy X . Write down similar expressions for the cases when B ea chooses strategy Y and when she chooses strategy $Z$.
Using graph paper, draw a graph to show A my's expected pay-off against p for each of Bea's choices of strategy. Using your graph, find the optimal value of pfor A my. A my and Bea play the game many times. A my chooses randomly between her strategies using the optimal value for p.
Showing your working, calculate A my's minimum expected pay-off per game. W hy might A my gain more points than this, on average?
W hat is B ea's minimum expected loss per game? How should B ea play to minimise her expected loss?

OCR D2 2007 June Q3

3 The table shows the activities involved in a project, their durations and precedences, and the number of workers needed for each activity.

On the insert, complete the last two columns of the table.
State the minimax value and write down the minimax route.
Complete the diagram on the insert to show the network that is represented by the table.

OCR D2 2009 June Q1

A café sells five different types of filled roll. Mr King buys one of each to take home to his family. The family consists of Mr King's daughter Fiona ( $F$ ), his mother Gwen ( $G$ ), his wife Helen ( $H$ ), his son Jack ( $J$ ) and Mr King ( $K$ ). The table shows who likes which rolls.

		$F$	$G$	$H$	$J$	$K$
Avocado and bacon	$( A )$	$\checkmark$		$\checkmark$
Beef and horseradish	$( B )$		$\checkmark$	$\checkmark$	$\checkmark$	$\checkmark$
Chicken and stuffing	$( C )$		$\checkmark$		$\checkmark$
Duck and plum sauce	$( D )$			$\checkmark$		$\checkmark$
Egg and tomato	$( E )$	$\checkmark$

Draw a bipartite graph to represent this information. Put the fillings ( $A , B , C , D$ and $E$ ) on the left-hand side and the members of the family ( $F , G , H , J$ and $K$ ) on the right-hand side. Fiona takes the avocado roll; Gwen takes the beef roll; Helen takes the duck roll and Jack takes the chicken roll.
Draw a second bipartite graph to show this incomplete matching.
Construct the shortest possible alternating path from $E$ to $K$ and hence find a complete matching. State which roll each family member has with this complete matching.
Find a different complete matching.

Mr King decides that the family should eat more fruit. Each family member gives a score out of 10 to five fruits. These scores are subtracted from 10 to give the values below. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Family member}
$F$ $G$ $H$ $J$ $K$
Lemon $L$ 8 8 8 8 1
Mandarin $M$ 4 8 6 4 2
Nectarine $N$ 9 9 9 7 1
Orange $O$ 4 6 5 4 3
Peach $P$ 6 9 7 5 0
\end{table} The smaller entries in each column correspond to fruits that the family members liked most.
Mr King buys one of each of these five fruits. Each family member is to be given a fruit.
Apply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working clearly. Which family member should be given which fruit?

OCR D2 2009 June Q2

Set up a dynamic programming tabulation to find the maximum weight route from ( $0 ; 0$ ) to ( $3 ; 0$ ) on the following directed network.
\includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-3_595_1056_404_587} Give the route and its total weight.
The actions now represent the activities in a project and the weights represent their durations. This information is shown in the table below.
Activity Duration Immediate predecessors
$A$ 8 -
$B$ 9 -
C 7 -
D 5 $A$
E 6 $A$
$F$ 4 $B$
$G$ 5 B
$H$ 6 $B$
$I$ 10 C
$J$ 9 $C$
$K$ 6 $C$
$L$ 7 D, F, I
$M$ 6 $E , G , J$
$N$ 8 $H$, $K$
Make a large copy of the network with the activities $A$ to $N$ labelled appropriately. Carry out a forward pass to find the early event times and a backward pass to find the late event times. Find the minimum completion time for the project and list the critical activities.
Compare the solutions to parts (i) and (ii).

OCR D2 2009 June Q3

3 The 'Rovers' and the 'Collies' are two teams of dog owners who compete in weekly dog shows. The top three dogs owned by members of the Rovers are Prince, Queenie and Rex. The top four dogs owned by the Collies are Woof, Xena, Yappie and Zulu. In a show the Rovers choose one of their dogs to compete against one of the dogs owned by the Collies. There are 10 points available in total. Each of the 10 points is awarded either to the dog owned by the Rovers or to the dog owned by the Collies. There are no tied points. At the end of the competition, 5 points are subtracted from the number of points won by each dog to give the score for that dog. The table shows the score for the dog owned by the Rovers for each combination of dogs.

	Collies
\cline { 2 - 6 }	$W$	$X$	$Y$	$Z$
\cline { 2 - 6 }	$P$	1	2	- 1	3
\cline { 2 - 6 }	$Q$	- 2	1	- 3	- 1
\cline { 2 - 6 } $R$	2	- 4	1	0
\cline { 2 - 6 }
\cline { 2 - 6 }

Explain why calculating the score by subtracting 5 from the number of points for each dog makes this a zero-sum game.
If the Rovers choose Prince and the Collies choose Woof, what score does Woof get, and how many points do Prince and Woof each get in the competition?
Show that column $W$ is dominated by one of the other columns, and state which column this is.
Delete the column for $W$ and find the play-safe strategy for the Rovers and the play-safe strategy for the Collies on the table that remains. Queenie is ill one week, so the Rovers make a random choice between Prince and Rex, choosing Prince with probability $p$ and Rex with probability $1 - p$.
Write down and simplify an expression for the expected score for the Rovers when the Collies choose Xena. Write down and simplify the corresponding expressions for when the Collies choose Yappie and for when they choose Zulu.
Using graph paper, draw a graph to show the expected score for the Rovers against $p$ for each of the choices that the Collies can make. Using your graph, find the optimal value of $p$ for the Rovers. If Queenie had not been ill, the Rovers would have made a random choice between Prince, Queenie and Rex, choosing Prince with probability $p _ { 1 }$, Queenie with probability $p _ { 2 }$ and Rex with probability $p _ { 3 }$. The problem of choosing the optimal values of $p _ { 1 } , p _ { 2 }$ and $p _ { 3 }$ can be formulated as the following linear programming problem: $$\begin{array} { l l } \operatorname { maximise } & M = m - 4
\text { subject to } & m \leqslant 6 p _ { 1 } + 5 p _ { 2 } ,
& m \leqslant 3 p _ { 1 } + p _ { 2 } + 5 p _ { 3 } ,
& m \leqslant 7 p _ { 1 } + 3 p _ { 2 } + 4 p _ { 3 } ,
& p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1
\text { and } & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , m \geqslant 0 . \end{array}$$
Explain how the expressions $6 p _ { 1 } + 5 p _ { 2 } , 3 p _ { 1 } + p _ { 2 } + 5 p _ { 3 }$ and $7 p _ { 1 } + 3 p _ { 2 } + 4 p _ { 3 }$ were obtained. Also explain how the linear programming formulation tells you that $M$ is a maximin solution. The Simplex algorithm is used to find the optimal values of the probabilities. The optimal value of $p _ { 1 }$ is $\frac { 5 } { 8 }$ and the optimal value of $p _ { 2 }$ is 0 .
Calculate the optimal value of $p _ { 3 }$ and the corresponding value of $M$.

OCR D2 2009 June Q4

4 The network represents a system of pipes through which fluid can flow from a source, $S$, to a sink, $T$. The weights on the arcs represent pipe capacities in gallons per minute.
\includegraphics[max width=\textwidth, alt={}, center]{9057da95-c53a-416c-8340-c94aff366385-6_599_1580_402_280}

Calculate the capacity of the cut that separates $\{ S , A , C , D \}$ from $\{ B , E , F , T \}$.
Explain why the arcs $A C$ and $A D$ cannot both be full to capacity and why the arcs $D F$ and $E F$ cannot both be full to capacity.
Draw a diagram to show a flow in which as much as possible flows through vertex $E$ but none flows through vertex $A$ and none flows through vertex $D$. State the maximum flow through vertex $E$. An engineer wants to find a flow augmenting route to improve the flow from part (iii).
(a) Explain why there can be no flow augmenting route that passes through vertex $A$ but not through vertex $D$.
(b) Write down a flow augmenting route that passes through vertex $D$ but not through vertex $A$. State the maximum by which the flow can be augmented.
Prove that the augmented flow in part (iv)(b) is the maximum flow.
A vertex restriction means that the flow through $E$ can no longer be at its maximum rate. By how much can the flow through $E$ be reduced without reducing the maximum flow from $S$ to $T$ ? Explain your reasoning. The pipe represented by the arc $B E$ becomes blocked and cannot be used.
Draw a diagram to show that, even when the flow through $E$ is reduced as in part (vi), the same maximum flow from $S$ to $T$ is still possible.

OCR D2 2011 June Q1

1 Adam, Barbara and their children Charlie, Donna, Edward and Fiona all want cereal for breakfast. The only cereal in the house is a pack of six individual portions of different cereals. The table shows which family members like each of the cereals in the pack.

\multirow{8}{*}{Cereal}	\multirow{2}{*}{}	Family member
		$A$	$B$	$C$	$D$	$E$	$F$
	Cornflakes (1)	✓	✓				✓
	Rice pips (2)			✓	✓
	Wheat biscs (3)		✓		✓
	Oatie bits (4)					✓	✓
	Choco pips (5)	✓		✓		✓
	Honey footballs (6)		✓

Draw a bipartite graph to represent this information. Adam gives the cornflakes to Fiona, the oatie bits to Edward, the rice pips to Donna, the choco pips to Charlie and the wheat biscs to Barbara. However, this leaves the honey footballs for Adam, which is not a possible pairing.
Draw a second bipartite graph to show this incomplete matching.
Construct the shortest possible alternating path from 6 to $A$ and hence find a complete matching between the cereals and the family members. Write down which family member is given each cereal with this complete matching.
Adam decides that he wants cornflakes. Construct an alternating path starting at $A$, based on your answer to part (iii) but with Adam being matched to the cornflakes, to find another complete matching. Write down which family member is given each cereal with this matching.

\(A - B = 30\) miles,	\(B - C = 15\) miles,	\(C - D = 35\) miles,	\(D - E = 12\) miles,
\(E - F = 3\) miles,	\(F - G = 30\) miles,	\(G - H = 10\) miles,	\(H - I = 25\) miles,
\(I - J = 10\) miles,	\(J - K = 10\) miles,	\(K - L = 5\) miles.

	\(N\)	\(P\)	\(Q\)	\(T\)
\(W\)	4	- 1	1	- 2
\(X\)	1	3	- 1	1
\(Y\)	5	1	2	- 1
\(Z\)	0	- 1	1	1

	House 1	House 2	House 3	House 4
Allclean	\(\pounds 500\)	\(\pounds 400\)	\(\pounds 700\)	\(\pounds 600\)
Brightenupp	\(\pounds 300\)	\(\pounds 200\)	\(\pounds 400\)	\(\pounds 350\)
Clean4U	\(\pounds 500\)	\(\pounds 300\)	\(\pounds 750\)	\(\pounds 680\)

		\(F\)	\(G\)	\(H\)	\(J\)	\(K\)
Avocado and bacon	\(( A )\)	\(\checkmark\)		\(\checkmark\)
Beef and horseradish	\(( B )\)		\(\checkmark\)	\(\checkmark\)	\(\checkmark\)	\(\checkmark\)
Chicken and stuffing	\(( C )\)		\(\checkmark\)		\(\checkmark\)
Duck and plum sauce	\(( D )\)			\(\checkmark\)		\(\checkmark\)
Egg and tomato	\(( E )\)	\(\checkmark\)

		\(F\)	\(G\)	\(H\)	\(J\)	\(K\)
Lemon	\(L\)	8	8	8	8	1
Mandarin	\(M\)	4	8	6	4	2
Nectarine	\(N\)	9	9	9	7	1
Orange	\(O\)	4	6	5	4	3
Peach	\(P\)	6	9	7	5	0

		Colin's card
		\(\circ\)	\(\square\)	\(\diamond\)	\(\triangle\)
\cline { 2 - 6 }	\(\bullet\)	- 2	3	- 4	1
\cline { 2 - 6 } Rose's	\(\square\)	4	- 3	4	5
\cline { 2 - 6 } card	\(\diamond\)	2	- 5	- 2	- 1
\cline { 2 - 6 }	\(\triangle\)	- 6	5	- 5	- 3
\cline { 2 - 6 }

\multirow{2}{*}{}	Character
	Fire Chief	Gardener	Handyman	Juggler	King
Adam	4	9	7	0	7
Bex	6	8	3	8	0
Chris	7	4	5	2	7
Denny	6	6	2	7	1

Activity	Duration	Immediate predecessors
\(A\)	8	-
\(B\)	9	-
C	7	-
D	5	\(A\)
E	6	\(A\)
\(F\)	4	\(B\)
\(G\)	5	B
\(H\)	6	\(B\)
\(I\)	10	C
\(J\)	9	\(C\)
\(K\)	6	\(C\)
\(L\)	7	D, F, I
\(M\)	6	\(E , G , J\)
\(N\)	8	\(H\), \(K\)

Questions — OCR D2 (141 questions)

Browse by module

Browse by board

OCR D2 2011 January Q5

OCR D2 2012 January Q1

OCR D2 2012 January Q2

OCR D2 2012 January Q3

OCR D2 2012 January Q4

OCR D2 2012 January Q5

OCR D2 2012 January Q6

OCR D2 2013 January Q1

OCR D2 2013 January Q2

OCR D2 2013 January Q3

OCR D2 2013 January Q4

OCR D2 2013 January Q5

OCR D2 2013 January Q6

OCR D2 2005 June Q1

OCR D2 2005 June Q2

OCR D2 2005 June Q3

OCR D2 2005 June Q4

OCR D2 2007 June Q1

OCR D2 2007 June Q2

OCR D2 2007 June Q3

OCR D2 2009 June Q1

OCR D2 2009 June Q2

OCR D2 2009 June Q3

OCR D2 2009 June Q4

OCR D2 2011 June Q1