June 2024: A level Paper 3D: Decision Mathematics 1

75 marks · 28 question parts · Question paper, mark scheme and examiner's report on Pearson's site

Question by question

QTopicMarksDifficulty
1(a) Algorithms, sorting, bin packing and graph theory 1 —
1(b) Algorithms, sorting, bin packing and graph theory 4 —
1(c) Algorithms, sorting, bin packing and graph theory 2 —
2(a) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 3 —
2(b) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 1 —
2(c) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 1 —
2(d) Route inspection and the travelling salesman problem 1 —
2(e) Route inspection and the travelling salesman problem 3 —
2(f) Route inspection and the travelling salesman problem 1 —
2(g) Route inspection and the travelling salesman problem 2 —
2(h) Route inspection and the travelling salesman problem 1 —
3(a) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 5 —
3(b) Route inspection and the travelling salesman problem 6 —
3(c) Route inspection and the travelling salesman problem 2 —
4(a) Algorithms, sorting, bin packing and graph theory 1 —
4(b) Algorithms, sorting, bin packing and graph theory 1 —
4(c) Algorithms, sorting, bin packing and graph theory 5 —
4(d) Algorithms, sorting, bin packing and graph theory 1 —
5(a) Linear programming: formulation, graphs and the Simplex algorithm 6 —
5(b) Linear programming: formulation, graphs and the Simplex algorithm 3 —
6(a) Critical path analysis 5 —
6(b) Critical path analysis 4 —
6(c) Critical path analysis 2 —
7(a) Linear programming: formulation, graphs and the Simplex algorithm 2 —
7(b) Linear programming: formulation, graphs and the Simplex algorithm 5 —
7(c) Linear programming: formulation, graphs and the Simplex algorithm 4 —
7(d) Linear programming: formulation, graphs and the Simplex algorithm 2 —
7(e) Linear programming: formulation, graphs and the Simplex algorithm 1 —

The questions

1(a)1(b)1(c)2(a)2(b)2(c)2(d)2(e)2(f)2(g)2(h)3(a)3(b)3(c)4(a)4(b)4(c)4(d)5(a)5(b)6(a)6(b)6(c)7(a)7(b)7(c)7(d)7(e)
June 2024 · Paper 3D (Decision 1) · Q1(a) 1 mark algorithms and graph theory
1. The eleven numbers listed above are to be packed into bins of size n where n is a positive integer. When the first-fit bin packing algorithm is applied to the eleven numbers, the bins are packed as shown below. Bin 1: Bin 2: Bin 3: Bin 4: Bin 5: (a) Explain why this packing means that the value of n must be 40 (1)
June 2024 · Paper 3D (Decision 1) · Q1(b) 4 marks algorithms and graph theory
The original list of eleven numbers is to be sorted into descending order. (b) Use a quick sort to obtain the fully sorted list. You must make your pivots clear. (4)
June 2024 · Paper 3D (Decision 1) · Q1(c) 2 marks algorithms and graph theory
(c) Apply the first-fit decreasing bin packing algorithm to the fully sorted list to pack the numbers into bins of size 40 (2)
June 2024 · Paper 3D (Decision 1) · Q2(a) 3 marks minimum spanning trees and shortest paths
2. The table below represents a network of shortest distances, in miles, to travel between nine castles, A, B, C, D, E, F, G, H and J. A B C E F G H J A – B – C – – E – F – G – H – J – (a) Use Prim’s algorithm, starting at D, to find the minimum spanning tree for this network. You must clearly state the order in which you select the arcs of your tree. (3)
June 2024 · Paper 3D (Decision 1) · Q2(b) 1 mark minimum spanning trees and shortest paths
(b) State the weight of the minimum spanning tree found in part (a). (1)
June 2024 · Paper 3D (Decision 1) · Q2(c) 1 mark minimum spanning trees and shortest paths
(c) Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book. (1)
June 2024 · Paper 3D (Decision 1) · Q2(d) 1 mark route inspection and travelling salesman
A historian needs to visit all of the castles, starting and finishing at the same castle, and wishes to minimise the total distance travelled. (d) Use your answer to part (b) to calculate an initial upper bound for the length of the historian’s route. (1)
June 2024 · Paper 3D (Decision 1) · Q2(e) 3 marks route inspection and travelling salesman
(e) (i) Use the nearest neighbour algorithm, starting at D, to find an upper bound for the length of the historian’s route. (ii) Write down the route which gives this upper bound. (3)
June 2024 · Paper 3D (Decision 1) · Q2(f) 1 mark route inspection and travelling salesman
Using the nearest neighbour algorithm, starting at F, an upper bound of length 352 miles was found. (f) State the best upper bound that can be obtained by using this information and your answers from parts (d) and (e). Give the reason for your answer. (1)
June 2024 · Paper 3D (Decision 1) · Q2(g) 2 marks route inspection and travelling salesman
(g) By deleting A and all of its arcs, find a lower bound for the length of the historian’s route. (2)
June 2024 · Paper 3D (Decision 1) · Q2(h) 1 mark route inspection and travelling salesman
By deleting J and all of its arcs, a lower bound of length 274 miles was found. (h) State the best lower bound that can be obtained by using this information and your answer to part (g). Give the reason for your answer. (1)
June 2024 · Paper 3D (Decision 1) · Q3(a) 5 marks minimum spanning trees and shortest paths
3. B E K A J F C G H Figure 1 [The total weight of the network is 413] Figure 1 represents a network of cycle tracks between ten towns, A, B, C, D, E, F, G, H, J and K. The number on each arc represents the length, in kilometres, of the corresponding track. (a) Use Dijkstra’s algorithm to find the shortest path from A to J. (5)
June 2024 · Paper 3D (Decision 1) · Q3(b) 6 marks route inspection and travelling salesman
Abi needs to travel along every track shown in Figure 1 to check that they are all in good repair. She needs to start her inspection route at town G and finish her route at either town J or town K. Abi wishes to minimise the total distance required to traverse every track. (b) By considering all relevant pairings of vertices, determine whether Abi should finish her inspection route at town J or town K. You must • state which tracks she will repeat in her route • state the total length of her route (6)
June 2024 · Paper 3D (Decision 1) · Q3(c) 2 marks route inspection and travelling salesman
The direct track between town B and town C and the direct track between town H and town K are now closed to all users. A second person, Tarig, is asked to check all the remaining tracks starting at G and finishing at H. Tarig wishes to minimise the total length of his inspection route. (c) Determine which route, Abi’s or Tarig’s, is shorter. You must make your working clear. (2)
June 2024 · Paper 3D (Decision 1) · Q4(a) 1 mark algorithms and graph theory
4. (a) Explain why it is not possible to draw a graph with exactly six nodes with degrees 1, 2, 3, 4, 5 and 6 (1)
June 2024 · Paper 3D (Decision 1) · Q4(b) 1 mark algorithms and graph theory
A tree, T, has exactly six nodes. The degrees of the six nodes of T are (4 – x) (2x – 5) (4x – 11) (3x – 5) where x is an integer. (b) Explain how you know that T cannot be Eulerian. (1)
June 2024 · Paper 3D (Decision 1) · Q4(c) 5 marks algorithms and graph theory
(c) (i) Determine the value of x (ii) Hence state whether T is semi-Eulerian or not. You must justify your answer. (5)
June 2024 · Paper 3D (Decision 1) · Q4(d) 1 mark algorithms and graph theory
Figure 2 Figure 2 shows a graph, G, with six nodes with degrees 1, 2, 3, 3, 3 and 4 (d) Using the vertices in Diagram 1 in the answer book, draw a graph with exactly six nodes with degrees 1, 2, 3, 3, 3 and 4 that is not isomorphic to G. (1)
June 2024 · Paper 3D (Decision 1) · Q5(a) 6 marks linear programming
5. Two friends, Anaira and Tommi, play a game involving two positive numbers x and y Anaira gives Tommi the following clues to see if he can correctly determine the value of x and the value of y • x is greater than y and the difference between the two is at least 100 • x is at most 5 times as large as y • the sum of 2x and 3y is at least 350 • the sum of x and y is as small as possible Tommi decides to solve this problem by using the big-M method. (a) Set up an initial tableau for solving this problem using the big-M method. As part of your solution, you must show • how the constraints were made into equations using one slack variable, exactly two surplus variables and exactly two artificial variables • how the objective function was formed (6)
June 2024 · Paper 3D (Decision 1) · Q5(b) 3 marks linear programming
The big-M method is applied until the tableau containing the optimal solution to the problem is found. One row of this final tableau is as follows. b.v. x y s1 s2 s3 a1 a2 Value x -3 -1 (b) (i) State the value of x (ii) Hence deduce the value of y, making your reasoning clear. (3)
June 2024 · Paper 3D (Decision 1) · Q6(a) 5 marks critical path analysis
6. The precedence table below shows the 12 activities required to complete a project. Activity Immediately preceding activities A – B – C – A E A, B, C F A, B, C G C H D, E I D, E J D, E K F, G, J L F, G (a) Draw the activity network described in the precedence table, using activity on arc. Your activity network must contain the minimum number of dummies only. (5)
June 2024 · Paper 3D (Decision 1) · Q6(b) 4 marks critical path analysis
Each of the activities shown in the precedence table requires one worker. The project is to be completed in the minimum possible time. 12 13 14 15 16 17 18 19 20 C E J K A G H I B F L Figure 3 Figure 3 shows a schedule for the project using three workers. (b) (i) State the critical path for the network. (ii) State the minimum completion time for the project. (iii) Calculate the total float on activity B. (iv) Calculate the total float on activity G. (4)
June 2024 · Paper 3D (Decision 1) · Q6(c) 2 marks critical path analysis
Immediately after the start of the project, it is found that the duration of activity I, as shown in Figure 3, is incorrect. In fact, activity I will take 8 hours. The durations of all the other activities remain as shown in Figure 3. (c) Determine whether the project can still be completed in the minimum completion time using only three workers when the duration of activity I is 8 hours. Your answer must make specific reference to workers, times and activities. (2)
June 2024 · Paper 3D (Decision 1) · Q7(a) 2 marks linear programming
7. A maximisation linear programming problem in x, y and z is to be solved using the Simplex method. The tableau after the 1st iteration is shown below. b.v. x y z s1 s2 s3 Value s1 -1 -1 x -1 s3 P -1 -11 (a) State the column that contains the pivot value for the 1st iteration. You must give a reason for your answer. (2)
June 2024 · Paper 3D (Decision 1) · Q7(b) 5 marks linear programming
(b) By considering the equations represented in the above tableau, formulate the linear programming problem in x, y and z only. State the objective and list the constraints as inequalities with integer coefficients. (5)
June 2024 · Paper 3D (Decision 1) · Q7(c) 4 marks linear programming
(c) Taking the most negative number in the profit row to indicate the pivot column, perform the 2nd iteration of the Simplex algorithm, to obtain a new tableau, T. Make your method clear by stating the row operations you use. (4)
June 2024 · Paper 3D (Decision 1) · Q7(d) 2 marks linear programming
(d) (i) Explain, using T, how you know that an optimal solution to the original linear programming problem has not been found after the 2nd iteration. (ii) State the values of the basic variables after the 2nd iteration. (2)
June 2024 · Paper 3D (Decision 1) · Q7(e) 1 mark linear programming
A student attempts the 3rd iteration of the Simplex algorithm and obtains the tableau below. b.v. x y z s1 s2 s3 Value -1 z -1 x -1 y P (e) Explain how you know that the student’s attempt at the 3rd iteration is not correct. (1)

Find an Edexcel Further Maths tutor

Want this paper marked and gone through with a Further Maths tutor? Message us.

Prefer email? Send an enquiry

If you are under 18, please include a parent's contact details. Enquiries go to enquiries@alevelfurthermathstutor.com and are deleted once handled.