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

75 marks · 29 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 1 —
1(c) Algorithms, sorting, bin packing and graph theory 1 —
1(d) Algorithms, sorting, bin packing and graph theory 1 —
1(e) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 1 —
1(f) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 2 —
2(a) Critical path analysis 3 —
2(b) Critical path analysis 4 —
3(a) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 6 —
3(b) Algorithms, sorting, bin packing and graph theory 2 —
4(a) Algorithms, sorting, bin packing and graph theory 1 —
4(b) Algorithms, sorting, bin packing and graph theory 2 —
4(c) Algorithms, sorting, bin packing and graph theory 3 —
4(d) Algorithms, sorting, bin packing and graph theory 4 —
4(e) Algorithms, sorting, bin packing and graph theory 2 —
5(a) Route inspection and the travelling salesman problem 5 —
5(b) Minimum spanning trees (Prim, Kruskal) and shortest paths (Dijkstra, Floyd) 3 —
5(c) Route inspection and the travelling salesman problem 2 —
5(d) Route inspection and the travelling salesman problem 2 —
5(e) Route inspection and the travelling salesman problem 1 —
6(a) Critical path analysis 5 —
6(b) Critical path analysis 1 —
6(c) Critical path analysis 1 —
6(d) Critical path analysis 2 —
7(a) Linear programming: formulation, graphs and the Simplex algorithm 5 —
7(b) Linear programming: formulation, graphs and the Simplex algorithm 6 —
7(c) Linear programming: formulation, graphs and the Simplex algorithm 5 —
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)1(d)1(e)1(f)2(a)2(b)3(a)3(b)4(a)4(b)4(c)4(d)4(e)5(a)5(b)5(c)5(d)5(e)6(a)6(b)6(c)6(d)7(a)7(b)7(c)7(d)7(e)
June 2023 · Paper 3D (Decision 1) · Q1(a) 1 mark algorithms and graph theory
1. E A B C Figure 1 Figure 1 shows the graph G. (a) State whether G is Eulerian, semi-Eulerian, or neither, giving a reason for your answer. (1)
June 2023 · Paper 3D (Decision 1) · Q1(b) 1 mark algorithms and graph theory
(b) Write down an example of a Hamiltonian cycle on G. (1)
June 2023 · Paper 3D (Decision 1) · Q1(c) 1 mark algorithms and graph theory
(c) State whether or not G is planar, justifying your answer. (1)
June 2023 · Paper 3D (Decision 1) · Q1(d) 1 mark algorithms and graph theory
(d) State the number of arcs that would need to be added to G to make the graph K5 (1)
June 2023 · Paper 3D (Decision 1) · Q1(e) 1 mark minimum spanning trees and shortest paths
E A B C Figure 2 Direct roads between five villages, A, B, C, D and E, are represented in Figure 2. The weight on each arc is the time, in minutes, required to travel along the corresponding road. Floyd’s algorithm is to be used to find the complete network of shortest times between the five villages. (e) For the network represented in Figure 2, complete the initial time matrix in the answer book. (1)
June 2023 · Paper 3D (Decision 1) · Q1(f) 2 marks minimum spanning trees and shortest paths
The time matrix after four iterations of Floyd’s algorithm is shown in Table 1. A B C E A – B – C – – E – Table 1 (f) Perform the final iteration of Floyd’s algorithm that follows from Table 1, showing the time matrix for this iteration. (2)
June 2023 · Paper 3D (Decision 1) · Q2(a) 3 marks critical path analysis
2. A(3) B(5) H(1) E(1) C(4) F(2) D(7) G(4) Figure 3 The network in Figure 3 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration, in hours, of the corresponding activity is shown in brackets. (a) (i) Complete Diagram 1 in the answer book to show the early event times and the late event times. (ii) State the minimum completion time of the project. (3)
June 2023 · Paper 3D (Decision 1) · Q2(b) 4 marks critical path analysis
The table below lists the number of workers required for each activity in the project. Activity Number of workers A B C E F G H Each worker is able to do any of the activities. Once an activity is started it must be completed without interruption. It is given that each activity begins at its earliest possible start time. (b) (i) On Grid 1 in the answer book, draw a resource histogram to show the number of workers required at each time. (ii) Hence state the time interval(s) when six workers are required. (4)
June 2023 · Paper 3D (Decision 1) · Q3(a) 6 marks minimum spanning trees and shortest paths
3. B E J A G C F H Figure 4 Figure 4 represents a network with nodes, A, B, C, D, E, F, G, H and J. The number on each edge gives the length of the corresponding edge. (a) (i) Use Dijkstra’s algorithm to find the shortest path from A to J. (ii) State the length of the shortest path from A to J. (6)
June 2023 · Paper 3D (Decision 1) · Q3(b) 2 marks algorithms and graph theory
2 , where n is the number of nodes in One application of Dijkstra’s algorithm has order n the network. It takes a computer 0.0312 seconds to find the shortest path from a given start node to a given end node in a network of 9 nodes. (b) Calculate approximately how long it would take, in minutes, for the computer to find the shortest path from a given start node to a given end node for a network of 9000 nodes. (2)
June 2023 · Paper 3D (Decision 1) · Q4(a) 1 mark algorithms and graph theory
4. The eleven distinct numbers listed below are to be packed into bins of size 40 15 22 3 9 23 x 5 4 18 20 13 It is known that x • is an integer less than 40 • is the largest number in the list (a) Explain why it is not possible to pack the numbers into 3 bins of size 40 (1)
June 2023 · Paper 3D (Decision 1) · Q4(b) 2 marks algorithms and graph theory
Given that it is possible to pack the numbers into 4 bins of size 40 (b) determine the range of values for x (2)
June 2023 · Paper 3D (Decision 1) · Q4(c) 3 marks algorithms and graph theory
(c) Use the first-fit bin packing algorithm to determine how the numbers can be packed into bins of size 40 (3)
June 2023 · Paper 3D (Decision 1) · Q4(d) 4 marks algorithms and graph theory
(d) Carry out a quick sort to produce a list of the numbers in descending order. You should show the result of each pass and identify your pivots clearly. (4)
June 2023 · Paper 3D (Decision 1) · Q4(e) 2 marks algorithms and graph theory
When the first-fit decreasing bin packing algorithm is applied to the list, neither the 15 nor the 13 is placed in the first bin. (e) Determine the value of x. You must give reasons for your answer. (2)
June 2023 · Paper 3D (Decision 1) · Q5(a) 5 marks route inspection and travelling salesman
5. A B H C G F E J Figure 5 [The total weight of the network is 423] Direct roads between nine towns, A, B, C, D, E, F, G, H and J, are represented in Figure 5. The number on each arc represents the length, in miles, of the corresponding road. The table below shows the shortest distances, in miles, between the nine towns. A B C E F G H J A – B – C – – E – F – G – H – J – Table of shortest distances A route is needed that minimises the total distance required to traverse each road at least once. The route must start at F and finish at J. (a) (i) By considering the pairings of all relevant nodes, find the roads that would need to be traversed twice. (ii) State the total length of this route. (5)
June 2023 · Paper 3D (Decision 1) · Q5(b) 3 marks minimum spanning trees and shortest paths
(b) Starting at A, use Prim’s algorithm to find the minimum spanning tree for the table of shortest distances. You must state the order in which you select the arcs of your tree. (3)
June 2023 · Paper 3D (Decision 1) · Q5(c) 2 marks route inspection and travelling salesman
Pete needs to visit all nine towns, starting and finishing in the same town, and wishes to minimise the total distance he travels. (c) Starting at G, use the nearest neighbour algorithm on the table of shortest distances to find an upper bound for the length of Pete’s route. Write down the route that gives this upper bound. (2)
June 2023 · Paper 3D (Decision 1) · Q5(d) 2 marks route inspection and travelling salesman
(d) By deleting G and all of its arcs, find a lower bound for the length of Pete’s route. (2)
June 2023 · Paper 3D (Decision 1) · Q5(e) 1 mark route inspection and travelling salesman
Pete decides to take the route he found in (c). (e) Interpret the route in terms of the actual towns visited. (1)
June 2023 · Paper 3D (Decision 1) · Q6(a) 5 marks critical path analysis
6. The precedence table below shows the twelve activities required to complete a project. Immediately preceding Activity activities A – B – C – A E A, B F D, E G A, B, C H F, G I D, E J D, E K F, G, I, J L I (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 2023 · Paper 3D (Decision 1) · Q6(b) 1 mark critical path analysis
B E I L A C G H Figure 6 Figure 6 shows a partially completed cascade chart for the project. The non‑critical activities F, J and K are not shown in Figure 6. The time taken to complete each activity is given in hours and the project is to be completed in the minimum possible time. (b) State the critical activities. (1)
June 2023 · Paper 3D (Decision 1) · Q6(c) 1 mark critical path analysis
Given that the total float of activity F is 2 hours, (c) state the duration of activity F. (1)
June 2023 · Paper 3D (Decision 1) · Q6(d) 2 marks critical path analysis
The duration of activity J is x hours, and the duration of activity K is y hours, where x > 0 and y > 0 (d) (i) State, in terms of y, the maximum possible total float for activity K. (ii) State, in terms of x and y, the total float for activity J. (2)
June 2023 · Paper 3D (Decision 1) · Q7(a) 5 marks linear programming
7. A publisher plans to produce three versions of the same book: a paperback, a hardcover, and a deluxe edition. • Each paperback takes 4 minutes to print and 1 minute to bind • Each hardcover takes 8 minutes to print and 5 minutes to bind • Each deluxe edition takes 15 minutes to print and 12 minutes to bind The printing machine is available for at most 150 hours and the binding machine must be used for at least 60 hours. The publisher decides to produce • at least 1600 books in total • at least three times as many paperbacks as hardcovers The profit on each paperback sold is £8, the profit on each hardcover sold is £20 and the profit on each deluxe edition sold is £40 Let x, y and z represent the number of paperbacks, hardcovers and deluxe editions produced. (a) Formulate this as a linear programming problem, stating the objective and listing the constraints as simplified inequalities with integer coefficients. (5)
June 2023 · Paper 3D (Decision 1) · Q7(b) 6 marks linear programming
The publisher decides to solve this linear programming problem by using the two-stage simplex method. (b) Set up an initial tableau for solving this problem using the two-stage simplex method. As part of your solution, you must show how • the constraints have been made into equations by using slack variables, exactly two surplus variables and exactly two artificial variables • the rows for the two objective functions are formed (6)
June 2023 · Paper 3D (Decision 1) · Q7(c) 5 marks linear programming
The following tableau is obtained after two iterations of the first stage of the two-stage simplex method. b.v. x y z s1 s2 s3 s4 a1 a2 Value s1 –1 –3 -1 -1 2000 z -12 -1 15600 x -1 -12 15600 s4 -4 -32 -56 204800 P I (c) Taking the most negative number in the profit row to indicate the pivot column, perform one complete iteration of the second stage of the two-stage simplex method to obtain a new tableau. Make your method clear by stating the row operations you use. (5)
June 2023 · Paper 3D (Decision 1) · Q7(d) 2 marks linear programming
After three iterations of the second stage of the two-stage simplex method, the following tableau is obtained. b.v. x y z s1 s2 s3 s4 Value s2 -1 z -3 -9 -7 x 1125 -1 -3 y P 20500 Given that the publisher produces the optimal number of each version of the book, (d) (i) state the maximum profit the publisher can earn, (ii) find the number of hours the binding machine will be used. (2)
June 2023 · Paper 3D (Decision 1) · Q7(e) 1 mark linear programming
(e) Give a reason why the publisher may not earn the profit stated in (d)(i). (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.