Questions — OCR (4628 questions)

Browse by module
All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 Mechanics 1 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pure 1 S1 S2 S3 S4 Stats 1 Unit 1 Unit 2 Unit 3 Unit 4
Browse by board
AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 Mechanics 1 PURE Pure 1 S1 S2 S3 S4 Stats 1 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4
Sort by: Default | Easiest first | Hardest first
OCR D1 2014 June Q2
11 marks Moderate -0.3
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.
  1. (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.
  2. Draw five distinct simply connected graphs each with exactly five vertices and exactly five arcs.
OCR D1 2014 June Q3
9 marks Moderate -0.8
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 10Input a positive integer, \(N\)
Line 20Let \(C = 1\)
Line 30If \(C ^ { 2 } \geqslant N\) jump to line 110
Line 40Let \(X = \sqrt { \left( N - C ^ { 2 } \right) }\) [you may record your answer as a surd or a decimal]
Line 50Let \(Y = \operatorname { INT } ( X )\)
Line 60If \(X = Y\) jump to line 100
Line 70If \(C > Y\) jump to line 110
Line 80Add 1 to \(C\)
Line 90Go back to line 30
Line 100Print \(C , X\) and stop
Line 110Print 'FAIL' and stop
  1. 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 .
  2. Apply the algorithm to the input \(N = 7\).
  3. Explain why lines 70 and 110 are needed. The algorithm has order \(\sqrt { N }\).
  4. 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
11 marks Moderate -0.3
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}
  1. 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.
  2. 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.
  3. 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\).
  4. 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
15 marks Moderate -0.5
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.
  1. (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\).
  2. 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).
  3. (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.
  4. 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\).
  5. 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\).
  6. Use this information to write down a second constraint on \(x\) and \(y\).
OCR D1 2014 June Q6
17 marks Moderate -0.8
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.
  1. 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\).
  2. 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-400000
    010851000400
    0025010070
    02410010176
    0513000180
  3. Use the initial Simplex tableau to write down two inequalities to represent the availability constraints for the colourants.
  4. Write down the profit that Sandie makes on each litre of amber lotion that she sells.
  5. 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
    10014.302.701.6317
    000-161-30-230
    0012.500.50035
    000-9.20-1.81-0.418
    0100.10-0.100.29
  6. Explain how you know that the optimal solution has been achieved.
  7. How much of each lotion should Sandie make and what is her maximum profit? Why might the profit be less than this?
  8. 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
13 marks Easy -1.8
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.
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. Which of the two methods is the more efficient at sorting this list? Support your answer with a reason.
OCR D1 2015 June Q2
10 marks Standard +0.3
2
  1. 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}$$
  2. 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.
  3. 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\)CDE\(F\)G\(H\)
    A-10-910---
    B10-85----
    C-8-9-10--
    D959-678-
    E10--6-一97
    F--107--5-
    G---895-8
    H----7-8-
  4. 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
9 marks Standard +0.8
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\).
  1. Find the coordinates of the optimum vertex and the corresponding value of \(P\).
  2. Find the optimum point if \(x\) and \(y\) must both have integer values. The objective is changed to maximise \(P = x + k y\).
  3. If \(k\) is positive, explain why the optimum point cannot be at \(C\) or \(D\).
  4. 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
15 marks Moderate -0.8
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.
  1. Express the profit, \(\pounds P\), as a function of \(x , y\) and \(z\).
  2. 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.
  3. 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
    10902008002000
    010.500.250-0.25012.5
    00-0.50-0.2510.25012.5
    0001001010
    000.50-0.250-0.75117.5
  4. 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
15 marks Challenging +1.2
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}
  1. Apply Dijkstra's algorithm to the network, starting at \(A\), to find the shortest route from \(A\) to \(H\).
  2. 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\).
  3. Explain why Sheng-Li will need to repeat some streets.
  4. 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.
  5. 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
10 marks Moderate -0.8
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
  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}
  2. 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
  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}
  4. 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.
  5. 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.
  6. Draw a subgraph that has the required properties and uses the edge labelled 1 that joins B and R .
  7. Using your answer to part (vi), show the two possible colourings of the back of the tower.
OCR D1 2016 June Q1
5 marks Moderate -0.8
1 The arc weights for a network on a complete graph with six vertices are given in the following table.
AB\(C\)DE\(F\)
A-579812
B5-46510
C74-768
D967-510
E8565-10
F121081010-
Apply Prim's algorithm to the table in the Printed Answer Book. Start by crossing out the row for \(A\) and choosing an entry from the column for \(A\). Write down the arcs used in the order that they are chosen. Draw the resulting minimum spanning tree and give its total weight.
OCR D1 2016 June Q2
9 marks Moderate -0.8
2 Shaun measured the mass, in kg, of each of 9 filled bags. He then used an algorithm to sort the masses into increasing order. Shaun's list after the first pass through the sorting algorithm is given below. $$\begin{array} { l l l l l l l l l } 32 & 41 & 22 & 37 & 53 & 43 & 29 & 15 & 26 \end{array}$$
  1. Explain how you know that Shaun did not use bubble sort. In fact, Shaun used shuttle sort, starting at the left-hand end of the list.
  2. Write down the two possibilities for the original list.
  3. Write down the list after the second pass through the shuttle sort algorithm.
  4. How many passes through shuttle sort were needed to sort the entire list? Shaun's sorted list is given below. $$\begin{array} { l l l l l l l l l } 15 & 22 & 26 & 29 & 32 & 37 & 41 & 43 & 53 \end{array}$$ Shaun wants to pack the bags into bins, each of which can hold a maximum of 100 kg .
  5. Write the list in decreasing order of mass and then apply the first-fit decreasing method to decide how to pack the bags into bins. Write the weights of the bags in each bin in the order that they are put into the bin.
  6. Find a way to pack all the bags using only 3 bins, each of which can hold a maximum of 100 kg .
OCR D1 2016 June Q3
11 marks Moderate -0.8
3 A problem to maximise \(P\) as a function of \(x , y\) and \(z\) is represented by the initial Simplex tableau below.
\(P\)\(x\)\(y\)\(z\)\(s\)\(t\)RHS
1- 1023000
050- 51060
043001100
  1. Write down \(P\) as a function of \(x , y\) and \(z\).
  2. Write down the constraints as inequalities involving \(x , y\) and \(z\).
  3. Carry out one iteration of the Simplex algorithm. After a second iteration of the Simplex algorithm the tableau is as given below.
    \(P\)\(x\)\(y\)\(z\)\(s\)\(t\)RHS
    107.2500.61.75211
    010.75000.2525
    000.751- 0.20.2513
  4. Explain how you know that the optimal solution has been achieved.
  5. Write down the values of \(x , y\) and \(z\) that maximise \(P\). Write down the optimal value of \(P\).
OCR D1 2016 June Q4
11 marks Standard +0.3
4 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. Molly says that she has drawn a graph with exactly five vertices, having vertex orders 1, 2, 3, 4 and 5.
  1. State how you know that Molly is wrong. Holly has drawn a connected graph with exactly six vertices, having vertex orders 2, 2, 2, 2, 4 and 6.
  2. (a) Explain how you know that Holly’s graph is not simply connected.
    (b) Determine whether Holly's graph is Eulerian, semi-Eulerian or neither, explaining how you know which of these it is. Olly has drawn a simply connected graph with exactly six vertices.
  3. (a) State the minimum possible value of the sum of the vertex orders in Olly's graph.
    (b) If Olly's graph is also Eulerian, what numerical values can the vertex orders take? Polly has drawn a simply connected Eulerian graph with exactly six vertices and exactly ten arcs.
  4. (a) What can you deduce about the vertex orders in Polly's graph?
    (b) Draw a graph that fits the description of Polly's graph.
OCR D1 2016 June Q5
12 marks Standard +0.3
5 The network below represents a single-track railway system. The vertices represent stations, the arcs represent railway tracks and the weights show distances in km. The total length of the arcs shown is 60 km . \includegraphics[max width=\textwidth, alt={}, center]{d783915d-5950-4a97-b6a0-70959214e218-5_442_1152_429_459}
  1. Apply Dijkstra's algorithm to the network, starting at \(G\), to find the shortest distance (in km ) from \(G\) to \(N\) and write down the route of this shortest path. Greg wants to travel from the station represented by vertex \(G\) to the station represented by vertex \(N\). He especially wants to include the track \(K L\) (in either direction) in his journey.
  2. Show how to use your working from part (i) to find the shortest journey that Greg can make that fulfils his requirements. Write down his route. Percy Li needs to check each track to see if any maintenance is required. He wants to start and end at the station represented by vertex \(G\) and travel in one continuous route that passes along each track at least once. The direction of travel along the tracks does not matter.
  3. Apply the route inspection algorithm, showing your working, to find the minimum distance that Percy will need to travel. Write down those arcs that Percy will need to repeat. If he travels this minimum distance, how many times will Percy travel through the station represented by vertex \(L\) ?
OCR D1 2016 June Q6
12 marks Moderate -0.5
6 William is making the bridesmaid dresses and pageboy outfits for his sister's wedding. He expects it to take 20 hours to make each bridesmaid dress and 15 hours to make each pageboy outfit. Each bridesmaid dress uses 8 metres of fabric. Each pageboy outfit uses 3 metres of fabric. The fabric costs \(\pounds 8\) per metre. Additional items cost \(\pounds 35\) for each bridesmaid dress and \(\pounds 80\) for each pageboy outfit. William's sister wants to have at least one bridesmaid and at least one pageboy. William has 100 hours available and must not spend more than \(\pounds 600\) in total on materials. Let \(x\) denote the number of bridesmaids and \(y\) denote the number of pageboys.
  1. Show why the constraint \(4 x + 3 y \leqslant 20\) is needed and write down three more constraints on the values of \(x\) and \(y\), other than that they must be integers.
  2. Plot the feasible region where all four constraints are satisfied. William's sister wants to maximise the total number of attendants (bridesmaids and pageboys) at her wedding.
  3. Use your graph to find the maximum number of attendants.
  4. William costs his time at \(\pounds 15\) an hour. Find, and simplify, an expression, in terms of \(x\) and \(y\), for the total cost (for all materials and William’s time). Hence find, and interpret, the minimum cost solution to part (iii).
OCR D1 2016 June Q7
12 marks Moderate -0.5
7 A tour guide wants to find a route around eight places of interest: Queen Elizabeth Olympic Park ( \(Q\) ), Royal Albert Hall ( \(R\) ), Statue of Eros ( \(S\) ), Tower Bridge ( \(T\) ), Westminster Abbey ( \(W\) ), St Paul's Cathedral ( \(X\) ), York House ( \(Y\) ) and Museum of Zoology ( \(Z\) ). The table below shows the travel times, in minutes, from each of the eight places to each of the other places.
\(Q\)\(R\)S\(T\)W\(X\)\(Y\)\(Z\)
\(Q\)-30352537404332
\(R\)30-12151520208
S3512-2010182516
\(T\)251520-12161818
W37151012-81420
\(X\)402018168-1722
\(Y\)432025181417-13
Z3281618202213-
  1. Use the nearest neighbour method to find an upper bound for the minimum time to travel to each of the eight places, starting and finishing at \(Y\). Write down the route and give the time in minutes.
  2. The Answer Book lists the arcs by increasing order of weight (reading across the rows). Apply Kruskal's algorithm to this list to find the minimum spanning tree for all eight places. Draw your tree and give its total weight.
  3. (a) Vertex \(Q\) and all arcs joined to \(Q\) are temporarily removed. Use your answer to part (ii) to write down the weight of the minimum spanning tree for the seven vertices \(R , S , T , W , X , Y\) and \(Z\).
    (b) Use your answer to part (iii)(a) to find a lower bound for the minimum time to travel to each of the eight places of interest, starting and finishing at \(Y\). The tour guide allows for a 5 -minute stop at each of \(S\) and \(Y\), a 10 -minute stop at \(T\) and a 30 -minute stop at each of \(Q , R , W , X\) and \(Z\). The tour guide wants to find a route, starting and ending at \(Y\), in which the tour (including the stops) can be completed in five hours (300 minutes).
  4. Use the nearest neighbour method, starting at \(Q\), to find a closed route through each vertex. Hence find a route for the tour, showing that it can be completed in time.
OCR D1 Specimen Q1
4 marks Easy -1.2
1 The graph \(\mathrm { K } _ { 5 }\) has five nodes, \(A , B , C , D\) and \(E\), and there is an arc joining every node to every other node.
  1. Draw the graph \(\mathrm { K } _ { 5 }\) and state how you know that it is Eulerian.
  2. By listing the arcs involved, give an example of a path in \(\mathrm { K } _ { 5 }\). (Your path must include more than one arc.)
  3. By listing the arcs involved, give an example of a cycle in \(\mathrm { K } _ { 5 }\).
OCR D1 Specimen Q2
7 marks Moderate -0.8
2 This question is about a simply connected network with at least three arcs joining 4 nodes. The weights on the arcs are all different and any direct paths always have a smaller weight than the total weight of any indirect paths between two vertices.
  1. Kruskal's algorithm is used to construct a minimum connector. Explain why the arcs with the smallest and second smallest weights will always be included in this minimum connector.
  2. Draw a diagram to show that the arc with the third smallest weight need not always be included in a minimum connector.
OCR D1 Specimen Q3
8 marks Easy -1.2
3
  1. Use the shuttle sort algorithm to sort the list $$\begin{array} { l l l l l } 6 & 3 & 8 & 3 & 2 \end{array}$$ into increasing order. Write down the list that results from each pass through the algorithm.
  2. Shuttle sort is a quadratic order algorithm. Explain briefly what this statement means.
OCR D1 Specimen Q4
9 marks Easy -1.2
4 [Answer this question on the insert provided.]
An algorithm involves the following steps.
Step 1: Input two positive integers, \(A\) and \(B\).
Let \(C = 0\) Step 2: If \(B\) is odd, replace \(C\) by \(C + A\).
Step 3: If \(B = 1\), go to step 6.
Step 4: Replace \(A\) by \(2 A\).
If \(B\) is even, replace \(B\) by \(B \div 2\), otherwise replace \(B\) by ( \(B - 1\) ) ÷ 2 .
Step 5: Go back to step 2.
Step 6: Output the value of \(C\).
  1. Demonstrate the use of the algorithm for the inputs \(A = 6\) and \(B = 13\).
  2. When \(B = 8\), what is the output in terms of \(A\) ? What is the relationship between the output and the original inputs?
OCR D1 Specimen Q5
9 marks Moderate -0.5
5 [Answer this question on the insert provided.] \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-3_659_1002_324_609} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the shortest distances in kilometres.
  1. The diagram on the insert shows the result of deleting vertex \(F\) and all the arcs joined to \(F\). Show that a lower bound for the length of the travelling salesperson problem on the original network is 38 km . The corresponding lower bounds by deleting each of the other vertices are: $$A : 40 \mathrm {~km} , \quad B : 39 \mathrm {~km} , \quad C : 35 \mathrm {~km} , \quad D : 37 \mathrm {~km} , \quad E : 35 \mathrm {~km} \text {. }$$ The route \(A - B - C - D - E - F - A\) has length 47 km .
  2. Using only this information, what are the best upper and lower bounds for the length of the solution to the travelling salesperson problem on the network?
  3. By considering the orders in which vertices \(C , D\) and \(E\) can be visited, find the best upper bound given by a route of the form \(A - B - \ldots - F - A\).
OCR D1 Specimen Q6
15 marks Standard +0.3
6 [Answer part (i) of this question on the insert provided.]
The diagram shows a simplified version of an orienteering course. The vertices represent checkpoints and the weights on the arcs show the travel times between checkpoints, in minutes. \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-4_483_931_461_630}
  1. Use Dijkstra's algorithm, starting from checkpoint \(\boldsymbol { A }\), to find the least travel time from \(A\) to \(D\). You must show your working, including temporary labels, permanent labels and the order in which permanent labels were assigned. Give the route that takes the least time from \(A\) to \(D\).
  2. By using an appropriate algorithm, find the least time needed to travel every arc in the diagram starting and ending at \(A\). You should show your method clearly.
  3. Starting from \(A\), apply the nearest neighbour algorithm to the diagram to find a cycle that visits every checkpoint. Use your solution to find a path that visits every checkpoint, starting from \(A\) and finishing at \(D\).
OCR D1 Specimen Q7
20 marks Moderate -0.3
7 Consider the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = 4 y - x , \\ \text { subject to } & x + 4 y \leqslant 22 , \\ & x + y \leqslant 10 , \\ & - x + 2 y \leqslant 8 , \\ \text { and } & x \geqslant 0 , y \geqslant 0 . \end{array}$$
  1. Represent the constraints graphically, shading out the regions where the inequalities are not satisfied. Calculate the value of \(x\) and the value of \(y\) at each of the vertices of the feasible region. Hence find the maximum value of \(P\), clearly indicating where it occurs.
  2. By introducing slack variables, represent the problem as an initial Simplex tableau and use the Simplex algorithm to solve the problem.
  3. Indicate on your diagram for part (i) the points that correspond to each stage of the Simplex algorithm carried out in part (ii). \section*{OXFORD CAMBRIDGE AND RSA EXAMINATIONS} Advanced Subsidiary General Certificate of Education Advanced General Certificate of Education MATHEMATICS
    4736
    Decision Mathematics 1
    INSERT for Questions 4, 5 and 6
    Specimen Paper
    • This insert should be used to answer Questions 4, 5 and 6
    • .
    • Write your Name, Centre Number and Candidate Number in the spaces provided at the top of this page.
    • Write your answers to Questions 4, 5 and 6
    • in the spaces provided in this insert, and attach it to your answer booklet.
    4
  4. STEPA\(B\)C
    1
    2
  5. STEPA\(B\)C
    1
    2
    5
  6. \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-7_661_1004_285_557}
  7. Upper bound = \(\_\_\_\_\) km Lower bound = \(\_\_\_\_\) km
  8. \(\_\_\_\_\) Best upper bound = \(\_\_\_\_\) km 6
  9. \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-8_668_1406_292_406} \includegraphics[max width=\textwidth, alt={}, center]{b1227633-913e-41a9-8bf8-1f064056963e-8_307_1342_1014_424}
    Least travel time = \(\_\_\_\_\) minutes Route: A- \(\_\_\_\_\) \(- D\)