Questions - OCR D1 - A-Level Maths

Find, in terms of $x$, the length of the shortest route that Richard could use to walk along every track, starting at $A$ and ending at $G$. Show all of your working.
Now suppose that Richard wants to find the length of the shortest route that he could use to walk along every track, starting and ending at $A$. Show that for $x \leqslant 1.8$ this route has length $( 32.4 + 2 x ) \mathrm { km }$, and for $x \geqslant 1.8$ it has length $( 34.2 + x ) \mathrm { km }$. Whenever two tracks join there is an information board for visitors to the forest. Shauna wants to check that the information boards have not been vandalised. She wants to find the length of the shortest possible route that starts and ends at $A$, passing through every vertex at least once. Consider first the case when $x$ is less than 3.2.
(a) Apply Prim's algorithm to the network, starting from vertex $A$, to find a minimum spanning tree. Draw the minimum spanning tree and state its total weight. Explain why the solution to Shauna's problem must be longer than this.
(b) Use the nearest neighbour strategy, starting from vertex $A$, and show that it stalls before it has visited every vertex. Now consider the case when $x$ is greater than 3.2 but less than 4.6.
(a) Draw the minimum spanning tree and state its total weight.
(b) Use the nearest neighbour strategy, starting from vertex $A$, to find a route from $A$ to $G$ passing through each vertex once. Write down the route obtained and its total weight. Show how a shortcut can give a shorter route from $A$ to $G$ passing through each vertex. Hence, explaining your method, find an upper bound for Shauna's problem.

OCR D1 2012 June Q1

1 Satellite navigation systems (sat navs) use a version of Dijkstra's algorithm to find the shortest route between two places. A simplified map is shown below. The values marked represent road distances, in km , for that section of road (from a place to a road junction, or between two places). \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{ccb12789-cd5f-40dc-9f10-f8bb45399580-2_712_1386_431_335} \captionsetup{labelformat=empty} \caption{Fort Effleigh (F)}

\end{figure}

Use the map to construct a network with exactly 10 arcs to show the direct distances between these places, with no road junctions shown. For example, there will need to be an arc connecting $A$ to $B$ of weight 22, and also arcs connecting $A$ to $C , D$, and $E$. There is no arc connecting $A$ to $F$ (because there is no route from $A$ to $F$ that does not pass through another place).
Apply Dijkstra's algorithm, starting at $A$, to find the shortest route from $A$ to $F$. Dijkstra's algorithm has quadratic order (order $n ^ { 2 }$ ).
If it takes 3 seconds for a certain sat nav to find the shortest route between two places when it has to process 200 places, calculate approximately how many minutes it will take when it has to process 4000 places.

OCR D1 2012 June Q2

2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.

(a) Draw a simply connected Eulerian graph with exactly five vertices and five arcs.
(b) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which one of the vertices has order 4.
(c) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which none of the vertices have order 4. A teacher is organising revision classes for her students. There will be ten revision classes scheduled into a number of sessions. Each class will run in one session only. Each student has chosen two classes to attend. The table shows which classes each student has chosen. \begin{table}[h]
\captionsetup{labelformat=empty} \caption{Revision classes}
Student number C1 C2 C3 C4 M1 M2 S1 S2 D1 D2
1 ✓ ✓
2 ✓ ✓
3 ✓ ✓
4 ✓ ✓
5 ✓ ✓
6 ✓ ✓
7 ✓ ✓
8 ✓ ✓
9 ✓ ✓
10 ✓ ✓
\end{table}
(a) Draw a graph to show this information. Each vertex represents a class. Each arc links the two classes chosen by a student.
(b) Show how the teacher can arrange the classes in just two sessions, which satisfy all student choices. For example, C1 and C2 cannot be in the same session. An extra student joins the group. This student chooses to attend the revision classes in M1 and D1.
(c) Explain why the teacher cannot now arrange the classes in just two sessions. Do not amend your graph from part (ii)(a).

OCR D1 2012 June Q3

Obtain the four inequalities that define the feasible region.
Calculate the coordinates of the vertices of the feasible region, giving your values as fractions. The objective is to maximise $P = x + 4 y$.
Calculate the value of $P$ at each vertex of the feasible region. Hence write down the coordinates of the optimal point, and the corresponding value of $P$. Suppose that the solution must have integer values for both $x$ and $y$.
Find the coordinates of the optimal point with integer-valued $x$ and $y$, and the corresponding value of $P$. Explain how you know that this is the optimal solution.

OCR D1 2012 June Q4

4 Consider the following linear programming problem. $$\begin{array} { l r } \text { Maximise } & P = - 5 x - 6 y + 4 z ,
\text { subject to } & 3 x - 4 y + z \leqslant 12 ,
& 6 x + 2 z \leqslant 20 ,
& - 10 x - 5 y + 5 z \leqslant 30 ,
& x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$

Use slack variables $s , t$ and $u$ to rewrite the first three constraints as equations. What restrictions are there on the values of $s , t$ and $u$ ?
Represent the problem as an initial Simplex tableau.
Show why the pivot for the first iteration of the Simplex algorithm must be the coefficient of $z$ in the third constraint.
Perform one iteration of the Simplex algorithm, showing how the elements of the pivot row were calculated and how this was used to calculate the other rows.
Perform a second iteration of the Simplex algorithm and record the values of $x , y , z$ and $P$ at the end of this iteration.
Write down the values of $s , t$ and $u$ from your final tableau and explain what they mean in terms of the original constraints.

OCR D1 2012 June Q5

5 Jess and Henry are out shopping. The network represents the main routes between shops in a shopping arcade. The arcs represent pathways and escalators, the vertices represent some of the shops and the weights on the arcs represent distances in metres.
\includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-6_586_1084_367_495} The total weight of all the arcs is 1200 metres.
The table below shows the shortest distances between vertices; some of these are indirect distances.

	M	$N$	$P$	$R$	$S$	$T$	$V$	$W$
M	-	70	110	190	60	190	140	90
N	70	-	40	130	120	170	80	150
$P$	110	40	-	100	80	140	120	110
$R$	190	130	100	-	130	40	50	160
$S$	60	120	80	130	-	170	80	30
$T$	190	170	140	40	170	-	90	200
$V$	140	80	120	50	80	90	-	110
W	90	150	110	160	30	200	110	-

Use a standard algorithm to find the shortest distance that Jess must travel to cover every arc in the original network, starting and ending at $M$.
Find the shortest distance that Jess must travel if she just wants to cover every arc, but does not mind where she starts and where she finishes. Which two points are her start and finish? Henry suggests that Jess only needs to visit each shop.
Apply the nearest neighbour method to the network, starting at $M$, to write down a closed tour through all the vertices. Calculate the weight of this tour. What does this value tell you about the length of the shortest closed route that passes through every vertex? Henry thinks that Jess does not need to visit shop $W$. He uses the table of shortest distances to list all the possible connections between $M , N , P , R , S$ and $V$ by increasing order of weight. Henry's list is given in your answer book.
Use Kruskal's algorithm on Henry's list to find a minimum spanning tree for $M , N , P , R , S , T$ and $V$. Draw the tree and calculate its total weight. Jess insists that they must include shop $W$.
Use the weight of the minimum spanning tree for $M , N , P , R , S , T$ and $V$, and the table of shortest distances, to find a lower bound for the length of the shortest closed route that passes through all eight vertices.

OCR D1 2012 June Q6

6 The following flow chart has been written to find a root of the cubic equation $x ^ { 3 } + A x ^ { 2 } + B x + C = 0$, given a starting value $X$ that is thought to be near the root.
\includegraphics[max width=\textwidth, alt={}, center]{ccb12789-cd5f-40dc-9f10-f8bb45399580-8_1410_1648_324_212}

Work through the algorithm, recording the values of $X , Y , Z$ and $W$ each time they change, for the equation $x ^ { 3 } - 4 x ^ { 2 } + 5 x + 1 = 0$, with a starting value of $X = 0$.
Show what happens when the algorithm is used for the equation $x ^ { 3 } - 4 x ^ { 2 } + 5 x + 1 = 0$, with a starting value of $X = 1$.
Show what happens when the algorithm is used for the equation $x ^ { 3 } - 4 x ^ { 2 } + 5 x + 1 = 0$, with a starting value of $X = - 1$.
Identify a possible problem with using this algorithm.

OCR D1 2013 June Q1

1 The list below is to be sorted into increasing order using bubble sort, starting at the left-hand end of the list. $$\begin{array} { l l l l l l } 24 & 57 & 9 & 31 & 16 & 4 \end{array}$$

Show which values are compared and which are swapped in the first pass. Write down the list that results at the end of the first pass.
Without showing the individual comparisons and swaps, write down the lists that result after the second pass and after the third pass.
In total there will be five passes made in carrying out bubble sort on the list. Write down how many swaps are made in each pass.

OCR D1 2013 June Q2

(a) Draw a connected Eulerian graph that has exactly four vertices and five arcs but is not simple.
(b) Explain why it is not possible to have a simply connected Eulerian graph with exactly four vertices and five arcs. A simply connected Eulerian graph is drawn that has exactly eight vertices and ten arcs.
(a) Explain how you know that the sum of the vertex orders must be 20 .
(b) Write down the minimum and maximum possible vertex order and draw a diagram that includes both the minimum and the maximum cases.
(c) Draw a diagram to show a simply connected Eulerian graph with exactly eight vertices and ten arcs in which the number of vertices of order 4 is as large as possible.

OCR D1 2013 June Q3

3 Holly has written an algorithm.

Step 1	Input two positive integers $A$ and $B$
Step 2	Let $C = A - B$
Step 3	If $C < 0$, let $D = B$ then let $E = B + C$
Step 4	If $C = 0$, jump to Step 10
Step 5	If $C > 0$, let $D = A$ and let $E = B$
Step 6	Let $F = D - E$
Step 7	If $F < 0$, let $D = E$ then let $E = F + D$ and go back to Step 6
Step 8	If $F = 0$, let $F = D$ then jump to Step 11
Step 9	If $F > 0$, let $D = F$ then go back to Step 6
Step 10	Let $F = A$
Step 11	Let $G = A \div F$
Step 12	Let $M = G \times B$
Step 13	Print the values $F$ and $M$

Work through Holly's algorithm using the input values $A = 30$ and $B = 18$. Set out your working using the table in the answer book. Use one row for each step where any values change and only write down values when they change. Write down the values that are printed.
Describe what happens when $A = 18$ and $B = 30$. You need only record enough rows of the table to be able to show what happens.
Without doing further working, state the output values of $F$ and $M$ when $A = 12$ and $B = 8$.

OCR D1 2013 June Q4

4 A simplified map of an area of moorland is shown below. The vertices represent farmhouses and the arcs represent the paths between the farmhouses. The weights on the arcs show distances in km.
\includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-4_618_1420_356_319} Ted wants to visit each farmhouse and then return to his starting point.

In your answer book the arcs have been sorted into increasing order of weight. Use Kruskal’s algorithm to find a minimum spanning tree for the network, and give its total weight. Hence find a route visiting each farmhouse, and returning to the starting point, which has length 82 km .
Give the weight of the minimum spanning tree for the six vertices $A , B , C , E , F , G$. Hence find a route visiting each of the seven farmhouses once, and returning to the starting point, which has length 81 km .
Show that the nearest neighbour method fails to produce a cycle through every vertex when started from $A$ but that it succeeds when started from $B$. Adapt this cycle to find a complete cycle of total weight less than 70 , and find the total length of the shorter cycle.

OCR D1 2013 June Q5

5 This question uses the same network as question 4. The total weight of the arcs in the network is 224.
\includegraphics[max width=\textwidth, alt={}, center]{dbefedb2-b398-45e8-92eb-eb510ff16def-5_618_1415_310_319}

Apply Dijkstra's algorithm to the network, starting at $A$, to find the shortest route from $A$ to $G$.
Dijkstra's algorithm has quadratic order (order $n ^ { 2 }$ ). It takes 2.25 seconds for a certain computer to apply Dijkstra's algorithm to a network with 7 vertices. Calculate approximately how many hours it will take to apply Dijkstra's algorithm to a network with 1400 vertices.
How much shorter would the path $C E$ need to be for it to become part of a shortest path from $A$ to $G$ ? Following a landslip, the paths $A C$ and $C E$ become blocked and cannot be used. A warden needs to travel along all the remaining paths to check that there are no more landslips.
Find the shortest distance that the warden must travel, assuming that she starts and ends at vertex $C$. Show your working.

OCR D1 2013 June Q6

6 Consider the following linear programming problem.

Maximise	$P = 5 x + 8 y$,

subject to	$3 x - 2 y \leqslant 12$,
	$3 x + 4 y \leqslant 30$,
	$3 x - 8 y \geqslant - 24$,
	$x \geqslant 0 , y \geqslant 0$.

Represent the constraints graphically. Shade the regions where the inequalities are not satisfied and hence identify the feasible region.
Calculate the coordinates of the vertices of the feasible region, apart from the origin, and calculate the value of $P$ at each vertex. Hence find the optimal values of $x$ and $y$, and state the maximum value of the objective.
Suppose that, additionally, $x$ and $y$ must both be integers. Find the maximum feasible value of $y$ for every feasible integer value of $x$. Calculate the value of $P$ at each of these points and hence find the optimal values of $x$ and $y$ with this additional restriction. Tom wants to use the Simplex algorithm to solve the original (non-integer) problem. He reformulates it as follows.
Maximise $\quad P = 5 x + 8 y$,
subject to $3 x - 2 y \leqslant 12$,
$3 x + 4 y \leqslant 30$,
$- 3 x + 8 y \leqslant 24$,
$x \geqslant 0 , y \geqslant 0$.
Explain why Tom needed to change the third constraint.
Represent the problem by an initial Simplex tableau.
Perform one iteration of the Simplex algorithm, choosing your pivot from the $\boldsymbol { y }$ column. Show how the pivot row was used to calculate the other rows. Write down the values of $x , y$ and $P$ that result from this iteration. Perform a second iteration of the Simplex algorithm to achieve the optimum point.

OCR D1 2014 June Q1

1 Sangita needs to move some heavy boxes to her new house. She has borrowed a van that can carry at most 600 kg . She will have to make several deliveries to her new house. The masses of the boxes have been recorded in kg as: $$\begin{array} { l l l l l l l l l l l } 120 & 120 & 120 & 100 & 150 & 200 & 250 & 150 & 200 & 250 & 120 \end{array}$$

Use the first-fit method to show how Sangita could pack the boxes into the van. How many deliveries does this solution require?
Use the first-fit decreasing method to show how Sangita could pack the boxes into the van. There is no need to use a sorting algorithm, but you should write down the sorted list before showing the packing. How many deliveries does this solution require? Sangita then realises that she cannot fit more than four boxes in the van at a time.
Find a way to pack the boxes into the van so that she makes as few deliveries as possible.

OCR D1 2014 June Q2

(a) Draw a simply connected graph that has exactly four vertices and exactly five arcs. Is your graph Eulerian, semi-Eulerian or neither? Explain how you know.
(b) By considering the sum of the vertex orders, show that there is only one possible simply connected graph with exactly four vertices and exactly five arcs.
Draw five distinct simply connected graphs each with exactly five vertices and exactly five arcs.

OCR D1 2014 June Q3

3 The following algorithm finds two positive integers for which the sum of their squares equals a given input, when this is possible. The function $\operatorname { INT } ( X )$ gives the largest integer that is less than or equal to $X$. For example: $\operatorname { INT } ( 6.9 ) = 6$, $\operatorname { INT } ( 7 ) = 7 , \operatorname { INT } ( 7.1 ) = 7$.

Line 10	Input a positive integer, $N$
Line 20	Let $C = 1$
Line 30	If $C ^ { 2 } \geqslant N$ jump to line 110
Line 40	Let $X = \sqrt { \left( N - C ^ { 2 } \right) }$ [you may record your answer as a surd or a decimal]
Line 50	Let $Y = \operatorname { INT } ( X )$
Line 60	If $X = Y$ jump to line 100
Line 70	If $C > Y$ jump to line 110
Line 80	Add 1 to $C$
Line 90	Go back to line 30
Line 100	Print $C , X$ and stop
Line 110	Print 'FAIL' and stop

Apply the algorithm to the input $N = 500$. You only need to write down values when they change and there is no need to record the use of lines $30,60,70$ or 90 .
Apply the algorithm to the input $N = 7$.
Explain why lines 70 and 110 are needed. The algorithm has order $\sqrt { N }$.
If it takes 0.7 seconds to run the algorithm when $N = 3000$, roughly how long will it take when $N = 12000$ ?

OCR D1 2014 June Q4

4 The network below represents a treasure trail. The arcs represent paths and the weights show distances in units of 100 metres. The total length of the paths shown is 4200 metres.
\includegraphics[max width=\textwidth, alt={}, center]{cdad4fbe-4b94-4c8f-bb42-24d20eeaab4d-4_681_1157_450_459}

Apply Dijkstra's algorithm to the network, starting at $A$, to find the shortest distance (in metres) from $A$ to each of the other vertices. Alex wants to hunt for the treasure. His current location is marked on the network as $A$. The clues to the location of the treasure are located on the paths. Every path has at least one clue and some paths have more than one. This means that Alex will need to search along the full length of every path to find all the clues.
Showing your working, find the length of the shortest route that Alex can take, starting and ending at $A$, to find every clue. The clues tell Alex that the treasure is located at the point marked as $H$ on the network.
Write down the shortest route from $A$ to $H$. Zac also starts at $A$ and searches along every path to find the clues. He also uses a shortest route to do this, but without returning to $A$. Instead he proceeds directly to the treasure at $H$.
Calculate the length of the shortest route that Zac can take to search for all the clues and reach the treasure.

OCR D1 2014 June Q5

5 This question uses the same network as question 4.
The network below represents a treasure trail. The arcs represent paths and the weights show distances in units of 100 metres.
\includegraphics[max width=\textwidth, alt={}, center]{cdad4fbe-4b94-4c8f-bb42-24d20eeaab4d-5_680_1154_431_459} Gus wants to hunt for the treasure. He assumes that the treasure is located at a vertex, but he does not know which one.

(a) Use the nearest neighbour method starting at $G$ to find an upper bound for the length of the shortest closed route through every vertex.
(b) Gus follows this route, but starting at $A$. Write down his route, starting and ending at $A$.
Use Prim's algorithm on the network, starting at $A$, to find a minimum spanning tree. You should write down the arcs in the order they are included, draw the tree and give its total weight (in units of 100 metres).
(a) Vertex $H$ and all arcs joined to $H$ are removed from the original network. Write down the weight of the minimum spanning tree for vertices $A , B , C , D , E , F$ and $G$ in the resulting reduced network.
(b) Use this minimum spanning tree for the reduced network to find a lower bound for the length of the shortest closed route through every vertex in the original network.
Find a route that passes through every vertex, starting and ending at $A$, that is longer than the lower bound from part (iii)(b) but shorter than the upper bound from part (i)(a). Give the length of your route, in metres. Assume that Gus travels along paths at a rate of $x$ minutes for every 100 metres and that he spends $y$ minutes at each vertex hunting for the treasure. Gus starts by hunting for the treasure at $A$. He then follows the route from part (iv), starting and finishing at $A$ and hunting for the treasure at each vertex. Unknown to Gus, the treasure is found before he gets to it, so he has to search at every vertex. Gus can take at most 2 hours from when he starts searching at $A$ to when he arrives back at $A$.
Use this information to write down a constraint on $x$ and $y$. The treasure was at $H$ and was found 40 minutes after Gus started. This means that Gus takes more than 40 minutes to get to $H$.
Use this information to write down a second constraint on $x$ and $y$.

OCR D1 2014 June Q6

6 Sandie makes tanning lotions which she sells to beauty salons. She makes three different lotions using the same basic ingredients but in different proportions. These lotions are called amber, bronze and copper. To make one litre of tanning lotion she needs one litre of fluid. This can either be water or water mixed with hempseed oil. One litre of amber lotion uses one litre of water, one litre of bronze lotion uses 0.8 litres of water and one litre of copper lotion uses 0.5 litres of water. Any remainder is made up of hempseed oil. Sandie has 40 litres of water and 7 litres of hempseed oil available.

By defining appropriate variables $a , b$ and $c$, show that the constraint on the amount of water available can be written as $10 a + 8 b + 5 c \leqslant 400$.
Find a similar constraint on the amount of hempseed oil available. The tanning lotions also use two colourants which give two further availability constraints. Sandie wants to maximise her profit, $\pounds P$. The problem can be represented as a linear programming problem with the initial Simplex tableau below. In this tableau $s , t , u$ and $v$ are slack variables.
$P$ $a$ $b$ $c$ $s$ $t$ $u$ $v$ RHS
1 -8 -7 -4 0 0 0 0 0
0 10 8 5 1 0 0 0 400
0 0 2 5 0 1 0 0 70
0 2 4 1 0 0 1 0 176
0 5 1 3 0 0 0 1 80
Use the initial Simplex tableau to write down two inequalities to represent the availability constraints for the colourants.
Write down the profit that Sandie makes on each litre of amber lotion that she sells.
Carry out one iteration of the Simplex algorithm, choosing a pivot from the $a$ column. Show the operations used to calculate each row. After a second iteration of the Simplex algorithm the tableau is as given below.
$P$ $a$ $b$ $c$ $s$ $t$ $u$ $v$ RHS
1 0 0 14.3 0 2.7 0 1.6 317
0 0 0 -16 1 -3 0 -2 30
0 0 1 2.5 0 0.5 0 0 35
0 0 0 -9.2 0 -1.8 1 -0.4 18
0 1 0 0.1 0 -0.1 0 0.2 9
Explain how you know that the optimal solution has been achieved.
How much of each lotion should Sandie make and what is her maximum profit? Why might the profit be less than this?
If none of the other availabilities change, what is the least amount of water that Sandie needs to make the amounts of lotion found in part (vii)?

OCR D1 2015 June Q1

1 The following list is to be sorted into increasing order, from smallest to largest. $$\begin{array} { l l l l l l } 15 & 7 & 9 & 26 & 10 & 4 \end{array}$$ Bubble sort is to be used, starting at the left-hand end of the list, so that after the completion of the first pass the largest value will be at the right-hand end of the list.

Write down the list that results at the end of the first pass through bubble sort. Write down the number of comparisons and the number of swaps that were made in this pass.
After 3 passes the list is $$\begin{array} { l l l l l l } 7 & 9 & 4 & 10 & 15 & 26 \end{array}$$ Write down the list that results at the end of the fourth pass through bubble sort. Write down the number of comparisons and the number of swaps that were made in this pass.
How many comparisons are needed in total to sort the list using bubble sort? Shuttle sort is then used to sort the original list, into increasing order, starting at the left-hand end of the list.
Write down the list that results at the end of the first pass through shuttle sort. Write down the number of comparisons and the number of swaps that were made in this pass.
After 3 passes the list is $$\begin{array} { l l l l l l } 7 & 9 & 15 & 26 & 10 & 4 \end{array}$$ Write down the list that results at the end of the fourth pass through shuttle sort. Write down the number of comparisons and the number of swaps that were made in this pass.
How many comparisons and how many swaps are made in the fifth pass? In sorting the original list, both methods use a total of 9 swaps.
Which of the two methods is the more efficient at sorting this list? Support your answer with a reason.

OCR D1 2015 June Q2

A minimum spanning tree is constructed for a network. A vertex and all arcs joined to it are then deleted from the network. Under what circumstances will the remaining arcs of the minimum spanning tree form a minimum spanning tree for the reduced network? Joseph wants to use Kruskal's algorithm to find the minimum spanning tree for a network. He has sorted the arcs in the network by increasing order of weight. $$\begin{array} { l l l l l l l } B D = 5 & F G = 5 & D E = 6 & D F = 7 & E H = 7 & B C = 8 & D G = 8
G H = 8 & A D = 9 & C D = 9 & E G = 9 & A B = 10 & A E = 10 & C F = 10 \end{array}$$
Use Kruskal's algorithm on the list in your answer book, crossing out arcs that are not used. Draw your minimum spanning tree and give its total weight.
By considering the minimum spanning tree for the reduced network formed when vertex $A$ and all arcs joined to $A$ are deleted, find a lower bound for the shortest closed cycle through every vertex on the original network. The table shows the arc weights for the same network.
A $B$ C D E $F$ G $H$
A - 10 - 9 10 - - -
B 10 - 8 5 - - - -
C - 8 - 9 - 10 - -
D 9 5 9 - 6 7 8 -
E 10 - - 6 - 一 9 7
F - - 10 7 - - 5 -
G - - - 8 9 5 - 8
H - - - - 7 - 8 -
Apply the nearest neighbour method, starting at $A$, to find a cycle through every vertex. Hence write down an upper bound for the shortest closed cycle through every vertex on the network.

OCR D1 2015 June Q3

3 The constraints of a linear programming problem are represented by the graph below. The feasible region is the unshaded region, including its boundaries.
\includegraphics[max width=\textwidth, alt={}, center]{372c062a-793f-4fb8-a769-957479f5fce7-05_846_833_365_614} The vertices of the feasible region are $A ( 3.5,2 ) , B ( 1.5,3 ) , C ( 0.5,1.5 ) , D ( 1,0.5 )$.
The objective is to maximise $P = x + 3 y$.

Find the coordinates of the optimum vertex and the corresponding value of $P$.
Find the optimum point if $x$ and $y$ must both have integer values. The objective is changed to maximise $P = x + k y$.
If $k$ is positive, explain why the optimum point cannot be at $C$ or $D$.
If $k$ can take any value, find the range of values of $k$ for which $A$ is the optimum point.

OCR D1 2015 June Q4

4 A farmer has 40 acres of land that can be used for growing wheat, potatoes and soya beans. The farmer can expect a profit of $\pounds 80$ for each acre of wheat, $\pounds 31$ for each acre of potatoes and $\pounds 100$ for each acre of soya beans. Land that is left unplanted incurs no cost and generates no profit. The farmer wants to choose how much land to use for growing each crop to maximise the profit. It takes 4 hours to plant each acre of wheat, 2 hours to plant each acre of potatoes and 1 hour to plant each acre of soya beans. There are 60 hours available in total for planting. At most 25 acres can be used for wheat and at most 10 acres can be used for soya beans.
Let $x$ denote the number of acres used for wheat, $y$ denote the number of acres used for potatoes and $z$ denote the number of acres used for soya beans.

Express the profit, $\pounds P$, as a function of $x , y$ and $z$.
Explain why the constraint $4 x + 2 y + z \leqslant 60$ is needed. Write down three more constraints on the values of $x , y$ and $z$, other than that they must be non-negative.
Set up an initial Simplex tableau to represent the farmer's problem. Perform one iteration of the Simplex algorithm, choosing a pivot from the column with the most negative value in the objective row. Show how each row that has changed was calculated. Julie uses the Simplex algorithm to solve the farmer's problem. Her final tableau is given below. The order of the rows and the use of the slack variables in Julie's tableau may be different from yours.
P $x$ $y$ $z$ $s$ $t$ $u$ $v$ RHS
1 0 9 0 20 0 80 0 2000
0 1 0.5 0 0.25 0 -0.25 0 12.5
0 0 -0.5 0 -0.25 1 0.25 0 12.5
0 0 0 1 0 0 1 0 10
0 0 0.5 0 -0.25 0 -0.75 1 17.5
Write down the values of $x , y$ and $z$ from Julie's final tableau. Hence advise the farmer on how many acres to use for each crop and how much land should be left unplanted.

OCR D1 2015 June Q5

4 marks

5 The network below represents the streets in a small village. The weights on the arcs show distances in metres. The total length of all the streets shown is 2200 metres.
\includegraphics[max width=\textwidth, alt={}, center]{372c062a-793f-4fb8-a769-957479f5fce7-07_499_1264_367_402}

Apply Dijkstra's algorithm to the network, starting at $A$, to find the shortest route from $A$ to $H$.
Write down the shortest route from $A$ to $E$ and the shortest route from $A$ to $G$. Sheng-Li needs to travel along every street to deliver leaflets. He will start and finish at $A$.
Explain why Sheng-Li will need to repeat some streets.
Showing your working, find the length of the shortest route that Sheng-Li can take, starting and ending at $A$, to deliver leaflets to every street. The streets have houses on both sides. Sheng-Li does not want to keep crossing the streets from one side to the other. His friend Nadia offers to help him. They decide that they will work together and set off from $A$, with Sheng-Li delivering to one side of $A B$ and Nadia delivering to the other side. Each street will have to be travelled along twice, either by both of them travelling along it once or by one of them travelling along it twice. Nadia and Sheng-Li travel $A - B - C - E$. At this point Sheng-Li is called back to $A$. He travels along $E - C - A$, delivering leaflets on one side of $C A$. Nadia completes the leaflet delivery on her own.
Calculate the minimum distance that Nadia will need to travel on her own to complete the delivery. Explain how your answer was achieved and how you know that it is the minimum possible distance.
[0pt] [4]

OCR D1 2015 June Q6

6 The Devil's Dice are four cubes with faces coloured green, yellow, blue or red.
Cube 1 has three green faces and one each of yellow, blue and red.

Two of the green faces are opposite one another.
The other green face is opposite the yellow face.
The blue face is opposite the red face.

This information is represented using the graph in Fig. 1. \begin{figure}[h]

\captionsetup{labelformat=empty} \caption{Cube 1} \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_359_330_685_957}

\end{figure} Fig. 1

Cube 2 has a green face opposite a blue face, another green face opposite a red face and a second red face opposite a yellow face. Draw a graph to represent this information. The graph in Fig. 2 represents opposite faces in cube 3. Cube 3 \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_350_326_1398_986} \captionsetup{labelformat=empty} \caption{Fig. 2}
\end{figure}
How many yellow faces does cube 3 have? Cube 4 has one green face, two yellow faces, one blue face and two red faces. The graph in Fig. 3 is an incomplete representation of opposite faces in cube 4 . \begin{figure}[h]
\captionsetup{labelformat=empty} \caption{Cube 4} \includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-08_257_273_2115_1018}
\end{figure} Fig. 3
Complete the graph in your answer book. The Devil's Dice puzzle requires the cubes to be stacked to form a tower so that each long face of the tower uses all four colours. The puzzle can be solved using graph theory. First the graphs representing the opposite faces of the four cubes are combined into a single graph. The edges of the graph are labelled $1,2,3$ or 4 to show which cube they belong to. The labelled graph in Fig. 4 shows cube 1 and cube 3 together. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{372c062a-793f-4fb8-a769-957479f5fce7-09_630_689_625_689} \captionsetup{labelformat=empty} \caption{Fig. 4}
\end{figure}
Complete the copy of the labelled graph in your answer book to show all four cubes. A subgraph is a graph contained within a given graph.
From the graph representing all four cubes a subgraph needs to be found that will represent the front and back faces of the tower. Each face of the tower uses each colour once. This means that the graph representing the front and back faces must be a subgraph of the answer to part (iv) with four edges labelled $1,2,3$ and 4 and four nodes each having order two.
Explain why if the loop labelled 1 joining G to G is used, it is not possible to form a subgraph with four edges labelled 1, 2, 3 and 4 and nodes each having order two. Suppose that the edge labelled 1 that joins B and R is used.
Draw a subgraph that has the required properties and uses the edge labelled 1 that joins B and R .
Using your answer to part (vi), show the two possible colourings of the back of the tower.

Maximise	\(P = 5 x + 8 y\),

subject to	\(3 x - 2 y \leqslant 12\),
	\(3 x + 4 y \leqslant 30\),
	\(3 x - 8 y \geqslant - 24\),
	\(x \geqslant 0 , y \geqslant 0\).

Maximise	\(\quad P = 5 x + 8 y\),
subject to	\(3 x - 2 y \leqslant 12\),
	\(3 x + 4 y \leqslant 30\),
	\(- 3 x + 8 y \leqslant 24\),
	\(x \geqslant 0 , y \geqslant 0\).

Student number	C1	C2	C3	C4	M1	M2	S1	S2	D1	D2
1	✓	✓
2				✓						✓
3			✓	✓
4			✓			✓
5								✓	✓
6		✓				✓
7					✓			✓
8	✓						✓
9						✓				✓
10					✓		✓

	M	\(N\)	\(P\)	\(R\)	\(S\)	\(T\)	\(V\)	\(W\)
M	-	70	110	190	60	190	140	90
N	70	-	40	130	120	170	80	150
\(P\)	110	40	-	100	80	140	120	110
\(R\)	190	130	100	-	130	40	50	160
\(S\)	60	120	80	130	-	170	80	30
\(T\)	190	170	140	40	170	-	90	200
\(V\)	140	80	120	50	80	90	-	110
W	90	150	110	160	30	200	110	-

Step 1	Input two positive integers \(A\) and \(B\)
Step 2	Let \(C = A - B\)
Step 3	If \(C < 0\), let \(D = B\) then let \(E = B + C\)
Step 4	If \(C = 0\), jump to Step 10
Step 5	If \(C > 0\), let \(D = A\) and let \(E = B\)
Step 6	Let \(F = D - E\)
Step 7	If \(F < 0\), let \(D = E\) then let \(E = F + D\) and go back to Step 6
Step 8	If \(F = 0\), let \(F = D\) then jump to Step 11
Step 9	If \(F > 0\), let \(D = F\) then go back to Step 6
Step 10	Let \(F = A\)
Step 11	Let \(G = A \div F\)
Step 12	Let \(M = G \times B\)
Step 13	Print the values \(F\) and \(M\)

Line 10	Input a positive integer, \(N\)
Line 20	Let \(C = 1\)
Line 30	If \(C ^ { 2 } \geqslant N\) jump to line 110
Line 40	Let \(X = \sqrt { \left( N - C ^ { 2 } \right) }\) [you may record your answer as a surd or a decimal]
Line 50	Let \(Y = \operatorname { INT } ( X )\)
Line 60	If \(X = Y\) jump to line 100
Line 70	If \(C > Y\) jump to line 110
Line 80	Add 1 to \(C\)
Line 90	Go back to line 30
Line 100	Print \(C , X\) and stop
Line 110	Print 'FAIL' and stop

\(P\)	\(a\)	\(b\)	\(c\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
1	-8	-7	-4	0	0	0	0	0
0	10	8	5	1	0	0	0	400
0	0	2	5	0	1	0	0	70
0	2	4	1	0	0	1	0	176
0	5	1	3	0	0	0	1	80

	A	\(B\)	C	D	E	\(F\)	G	\(H\)
A	-	10	-	9	10	-	-	-
B	10	-	8	5	-	-	-	-
C	-	8	-	9	-	10	-	-
D	9	5	9	-	6	7	8	-
E	10	-	-	6	-	一	9	7
F	-	-	10	7	-	-	5	-
G	-	-	-	8	9	5	-	8
H	-	-	-	-	7	-	8	-

P	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
1	0	9	0	20	0	80	0	2000
0	1	0.5	0	0.25	0	-0.25	0	12.5
0	0	-0.5	0	-0.25	1	0.25	0	12.5
0	0	0	1	0	0	1	0	10
0	0	0.5	0	-0.25	0	-0.75	1	17.5

\(P\)	\(a\)	\(b\)	\(c\)	\(s\)	\(t\)	\(u\)	\(v\)	RHS
1	0	0	14.3	0	2.7	0	1.6	317
0	0	0	-16	1	-3	0	-2	30
0	0	1	2.5	0	0.5	0	0	35
0	0	0	-9.2	0	-1.8	1	-0.4	18
0	1	0	0.1	0	-0.1	0	0.2	9

Questions — OCR D1 (124 questions)

Browse by module

Browse by board

OCR D1 2011 June Q6

OCR D1 2012 June Q1

OCR D1 2012 June Q2

OCR D1 2012 June Q3

OCR D1 2012 June Q4

OCR D1 2012 June Q5

OCR D1 2012 June Q6

OCR D1 2013 June Q1

OCR D1 2013 June Q2

OCR D1 2013 June Q3

OCR D1 2013 June Q4

OCR D1 2013 June Q5

OCR D1 2013 June Q6

OCR D1 2014 June Q1

OCR D1 2014 June Q2

OCR D1 2014 June Q3

OCR D1 2014 June Q4

OCR D1 2014 June Q5

OCR D1 2014 June Q6

OCR D1 2015 June Q1

OCR D1 2015 June Q2

OCR D1 2015 June Q3

OCR D1 2015 June Q4

OCR D1 2015 June Q5

OCR D1 2015 June Q6