October 2021 QP
October 2021 QP
Mathematics
International Advanced Subsidiary/Advanced Level
Decision Mathematics D1
*P69351A*
P69351A
©2021 Pearson Education Ltd.
E:1/1/1/
PMT
B 13 E
8 5
23
5
F 16
A H
15
5 9
C 10
17 7
27
19
9
D 6 G 15 J
Figure 1
Figure 1 represents a network of roads. The number on each arc represents the length, in km, of the
corresponding road. Piatrice wishes to travel from A to J.
(b) Use Dijkstra’s algorithm to find the shortest path Piatrice could take from A to J.
State your path and its length.
(6)
(c) Find the shortest path Piatrice could take from J to A via G and state its length.
(2)
(Total 10 marks)
P69351A 2
PMT
2. Chris has been asked to design a badge in the shape of a triangle XYZ subject to the following
constraints.
• Angle Y should be at least three times the size of angle X
• Angle Z should be at least 50° larger than angle X
• Angle Y must be at most 120°
Chris has been asked to maximise the sum of the angles X and Y.
Formulate this information as a linear programming problem in x and y only. State the objective
and list the constraints as simplified inequalities with integer coefficients.
(Total 6 marks)
3. The table below represents a complete network that shows the least costs of travelling between
eight cities, A, B, C, D, E, F, G and H.
A B C D E F G H
A – 36 38 40 23 39 38 35
B 36 – 35 36 35 34 41 38
C 38 35 – 39 25 32 40 40
D 40 36 39 – 37 37 26 33
E 23 35 25 37 – 42 24 43
F 39 34 32 37 42 – 45 38
G 38 41 40 26 24 45 – 40
H 35 38 40 33 43 38 40 –
Srinjoy must visit each city at least once. He will start and finish at A and wishes to minimise his
total cost.
(a) Use Prim’s algorithm, starting at A, to find a minimum spanning tree for this network. You
must list the arcs that form the tree in the order in which you select them.
(3)
(c) Use your answer to (b) to help you calculate an initial upper bound for the total cost of Srinjoy’s
route.
(1)
(d) Show that there are two nearest neighbour routes that start from A. You must make the routes
and their corresponding costs clear.
(4)
(e) State the best upper bound that can be obtained by using your answers to (c) and (d).
(1)
(f) Starting by deleting A and all of its arcs, find a lower bound for the total cost of Srinjoy’s route.
You must make your method and working clear.
(3)
(g) Use your results to write down the smallest interval that must contain the optimal cost of
Srinjoy’s route.
(2)
(Total 15 marks)
P69351A 4
PMT
BLANK PAGE
4.
12 F(w) y
13 z
G(5) K(6)
C(v)
5 13 H(7) 20 L(5) 25
x D(4) 13 20 25
A(5) E(7)
I(10) M(4)
0 6 20
0 B(6) 6 J(4) 21
Figure 2
The network in Figure 2 shows the activities that need to be carried out by a company to complete
a project. Each activity is represented by an arc, and the duration, in days, is shown in brackets.
Each activity requires one worker. The early event times and the late event times are shown at each
vertex.
P69351A 6
PMT
0 2 4 6 8 10 12 14 16 18 20 22 24 26
B E H L
A
C
D
F
G
I
J
K
M
Grid 1
The project is to be completed in the minimum time using as few workers as possible.
(c) Calculate a lower bound for the minimum number of workers required. You must show your
working.
(1)
(d) On Grid 2 in your answer book, construct a scheduling diagram for this project.
(3)
Before the project begins it is found that activity F will require an additional 5 hours to complete.
The durations of all other activities are unchanged. The project is still to be completed in the
shortest possible time using as few workers as possible.
(e) State the new minimum project completion time and state the new critical path.
(2)
(Total 11 marks)
5.
B 15 E
7 1
8
16
H
17
15 C 10 F
A 19
11 8
5 4 10
5
D 3 G 12 J
Figure 3
Figure 3 models a network of cycle lanes that must be inspected. The number on each arc represents
the length, in km, of the corresponding cycle lane. Lance needs to cycle along each lane at least
once and wishes to minimise the length of his inspection route.
(a) Use an appropriate algorithm to find the length of the route. State the cycle lanes that Lance
will need to traverse twice. You should make your method and working clear.
(6)
(b) State the number of times that vertex C appears in Lance’s route.
(1)
It is now decided that the inspection route may finish at any vertex. Lance will still start at A and
must cycle along each lane at least once.
(c) Determine the finishing point so that the length of the route is minimised. You must give
reasons for your answer and state the length of this new minimum route.
(3)
(Total 10 marks)
P69351A 8
PMT
subject to: 3y x
x + 2y 130
4x + y 100
4x + 3y 300
(a) Add lines and shading to Diagram 1 in the answer book to represent these constraints. Hence
determine the feasible region and label it R.
(4)
(i) use the objective line method to find the optimal vertex, V, of the feasible region. You must
draw and label your objective line and label vertex V clearly.
(2)
(ii) calculate the coordinates of V and hence calculate the corresponding value of P at V.
(3)
(c) determine the range of possible values for k. You must make your method and working clear.
(4)
(Total 13 marks)
7. The numbers listed below are to be packed into bins of size n, where n is a positive integer.
14 20 23 17 15 22 19 25 13 28 32
(a) Determine the range of possible values of n. You must make your method clear.
(3)
(b) 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)
When the first‑fit bin packing algorithm is applied to the original list of numbers, the following
allocation is achieved.
Bin 1: 14 20 23 15
Bin 2: 17 22 19 13
Bin 3: 25 28
Bin 4: 32
When the first-fit decreasing bin packing algorithm is applied to the sorted list of numbers,
the following allocation is achieved.
Bin 1: 32 28
Bin 2: 25 23 22
Bin 3: 20 19 17 15
Bin 4: 14 13
(c) Determine the value of n. You must explain your reasoning fully.
(3)
(Total 10 marks)
TOTAL FOR PAPER: 75 MARKS
END
P69351A 10
PMT
BLANK PAGE
P69351A 11
PMT
BLANK PAGE
P69351A 12
PMT
Please check the examination details below before entering your candidate information
Candidate surname Other names
Turn over
*P69351A0120*
P69351A
©2021 Pearson Education Ltd.
E:1/1/1/
PMT
Leave
blank
1.
(a) ________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
Key:
Order of Final
Vertex
labelling value
Working values
B 13 E
8 5
23
5 16
A F H
15
5 9
27 7
C
10
17 19 J
9 G
15
6
D
2
*P69351A0220*
PMT
Leave
blank
Question 1 continued
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
Q1
________________________________________________________________________
(Total 10 marks)
3
*P69351A0320* Turn over
PMT
Leave
blank
2.
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
4
*P69351A0420*
PMT
Leave
blank
Question 2 continued
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
Q2
________________________________________________________________________
(Total 6 marks)
5
*P69351A0520* Turn over
PMT
Leave
blank
3.
A B C D E F G H
A – 36 38 40 23 39 38 35
B 36 – 35 36 35 34 41 38
C 38 35 – 39 25 32 40 40
D 40 36 39 – 37 37 26 33
E 23 35 25 37 – 42 24 43
F 39 34 32 37 42 – 45 38
G 38 41 40 26 24 45 – 40
H 35 38 40 33 43 38 40 –
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
6
*P69351A0620*
PMT
Leave
blank
Question 3 continued
A B C D E F G H
A – 36 38 40 23 39 38 35
B 36 – 35 36 35 34 41 38
C 38 35 – 39 25 32 40 40
D 40 36 39 – 37 37 26 33
E 23 35 25 37 – 42 24 43
F 39 34 32 37 42 – 45 38
G 38 41 40 26 24 45 – 40
H 35 38 40 33 43 38 40 –
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
7
*P69351A0720* Turn over
PMT
Leave
blank
Question 3 continued
A B C D E F G H
A – 36 38 40 23 39 38 35
B 36 – 35 36 35 34 41 38
C 38 35 – 39 25 32 40 40
D 40 36 39 – 37 37 26 33
E 23 35 25 37 – 42 24 43
F 39 34 32 37 42 – 45 38
G 38 41 40 26 24 45 – 40
H 35 38 40 33 43 38 40 –
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
8
*P69351A0820*
PMT
Leave
blank
Question 3 continued
A B C D E F G H
A – 36 38 40 23 39 38 35
B 36 – 35 36 35 34 41 38
C 38 35 – 39 25 32 40 40
D 40 36 39 – 37 37 26 33
E 23 35 25 37 – 42 24 43
F 39 34 32 37 42 – 45 38
G 38 41 40 26 24 45 – 40
H 35 38 40 33 43 38 40 –
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
Q3
________________________________________________________________________
(Total 15 marks)
9
*P69351A0920* Turn over
PMT
Leave
blank
4.
12 F(w) y
13 z
G(5) K(6)
C(v)
5 13 H(7) 20 L(5) 25
x D(4) 13 20 25
A(5) E(7)
I(10) M(4)
0 6 20
0 B(6) 6 J(4) 21
Figure 2
(a)
A F K
B G L
C H M
D I
E J
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
10
*P69351A01020*
PMT
Leave
blank
Question 4 continued
0 2 4 6 8 10 12 14 16 18 20 22 24 26
Grid 2
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
Q4
________________________________________________________________________
(Total 11 marks)
11
*P69351A01120* Turn over
PMT
Leave
blank
5.
B 15 E
7 1
8
16
H
17
15 C 10 F
A 19
11 8
5 4 10
5
D 3 G 12 J
Figure 3
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
12
*P69351A01220*
PMT
Leave
blank
Question 5 continued
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
Q5
________________________________________________________________________
(Total 10 marks)
13
*P69351A01320* Turn over
PMT
Leave
blank
6.
y
140
130
120
110
100
90
80
70
60
50
40
30
20
10
0
x
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180
Diagram 1
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
14
*P69351A01420*
PMT
Leave
blank
Question 6 continued
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
15
*P69351A01520* Turn over
PMT
Leave
blank
Question 6 continued
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
16
*P69351A01620*
PMT
Leave
blank
Question 6 continued
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
Q6
________________________________________________________________________
(Total 13 marks)
17
*P69351A01720* Turn over
PMT
Leave
blank
7.
14 20 23 17 15 22 19 25 13 28 32
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
18
*P69351A01820*
PMT
Leave
blank
Question 7 continued
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
19
*P69351A01920* Turn over
PMT
Leave
blank
Question 7 continued
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________
________________________________________________________________________ Q7
(Total 10 marks)
TOTAL FOR PAPER: 75 MARKS
END
20
*P69351A02020*