OCR
GCSE
Further Mathematics A
Y534/01: Discrete Mathematics
*1919801847*
AS Level
INSTRUCTIONS
• Use black ink. You can use an HB pencil, but only for graphs and diagrams.
• Write your answer to each question in the space provided in the Printed Answer
Booklet. If you need extra space use the lined pages at the end of the Printed Answer
Booklet. The question numbers must be clearly shown.
• Fill in the boxes on the front of the Printed Answer Booklet.
• Answer all the questions.
• Where appropriate, your answer should be supported with working. Marks might be
given for using a correct method, even if your answer is wrong.
• Give non-exact numerical answers correct to 3 significant figures unless a different
degree of accuracy is specified in the question.
• The acceleration due to gravity is denoted by g m s–2. When a numerical value is
needed use g = 9.8 unless a different value is specified in the question.
• Do not send this Question Paper for marking. Keep it in the centre or recycle it.
INFORMATION
• The total mark for this paper is 60.
• The marks for each question are shown in brackets [ ].
• This document has 8 pages.
ADVICE
• Read each question carefully before you start your answer.
© OCR 2025 [D/508/5500] DC (SL/CT) 360294/3
OCR is an exempt Charity
Turn over
1 A builder has some pieces of wood that are 6 m in length. The builder needs to cut
smaller pieces to use in a project. The lengths of the smaller pieces required are
shown below.
2.5 m 2m 4.5 m 3m 1.5 m 3.5 m
2m
, 2
(a) Use the first-fit decreasing algorithm to determine the smallest number of
6 m lengths of
wood needed to cut the seven smaller pieces.
(b) First-fit decreasing is a heuristic algorithm. Explain what this means.
[1]
The first-fit decreasing algorithm is order O(n2).
(c) It takes a computer 3.2 seconds to solve an allocation problem involving
200 items of data
using the first-fit decreasing algorithm. Calculate approximately how long it
would take to
solve an allocation problem involving 1000 items of data.
2 A student has six cards numbered from 1– 6. The cards are shown below.
1 2 3 4 5 6
(a) The student chooses four cards at random.
Use the Pigeonhole Principle to explain why they must have at least two cards
whose
numbers add to seven.
(b) The student now chooses two cards and places them side by side to form a
two-digit number.
(i) Determine the number of different two-digit numbers that the student
can make. [2]
(ii) Determine the number of different even two-digit numbers that the
student can make. [2] 3 The table shows the lengths in km of
footpaths between six places, A to F, in a town.
A B C D E F
A – 5 3 5 8 10
B 5 – 6 2 7 5
C 3 6 – 1 10 8
D 5 2 1 – 9 4
E 8 7 10 9 – 3
© OCR 2025 Y534/01 Jun25
, 3
F 10 5 8 4 3 –
(a) Apply the tabular form of Prim’s algorithm, starting at A, to the copy of the
table in the Printed Answer Booklet to construct a minimum spanning
tree for the six places in the town. You should state the order in which the
arcs are added to the tree.
Draw the minimum spanning tree and find its weight.
(b) Sam needs to walk from A to F.
Give an example of a question Sam could ask which leads to an enumeration
problem. [1]
(c) Use an appropriate algorithm to find the shortest route from A to F. You
must state its length.
© OCR 2025 Y534/01 Jun25 Turn over
, 4
4 Ryan and Casey play a game.
They can each choose to play one of three options.
Ryan can play options A, B and C and Casey can play options X, Y and Z.
The scores for each player for each combination of choices are shown in the pay-off
matrices below:
Scores for Ryan
Casey’s
Options
X Y Z
Ryan’s A 1 4 3
Options B 5 3 4
C 3 1 3
Scores for Casey
Casey’s
Options
X Y Z
Ryan’s A 5 2 3
Options B 1 3 2
(a) Explain C 3 5 3 how the game between Ryan and Casey
can be expressed as the zero-sum game with the pay-off matrix below (the entries
represent pay-offs for Ryan). [1]
Casey’s
Options
X Y Z
Ryan’s A –2 1 0
Options B 2 0 1
C 0 –2 0
(b) If Casey knows that Ryan will play option A, state the option that Casey should play.
[1]
(c) Find the play-safe strategies for both players. [3]
(d) Determine whether or not the game is stable. [1]
#
(e) Use a dominance argument to reduce the zero-sum game to a 2 3 game. [1]
(f) Let p be the probability that Ryan plays option A on the reduced game from part (e).
© OCR 2025 Y534/01 Jun25
GCSE
Further Mathematics A
Y534/01: Discrete Mathematics
*1919801847*
AS Level
INSTRUCTIONS
• Use black ink. You can use an HB pencil, but only for graphs and diagrams.
• Write your answer to each question in the space provided in the Printed Answer
Booklet. If you need extra space use the lined pages at the end of the Printed Answer
Booklet. The question numbers must be clearly shown.
• Fill in the boxes on the front of the Printed Answer Booklet.
• Answer all the questions.
• Where appropriate, your answer should be supported with working. Marks might be
given for using a correct method, even if your answer is wrong.
• Give non-exact numerical answers correct to 3 significant figures unless a different
degree of accuracy is specified in the question.
• The acceleration due to gravity is denoted by g m s–2. When a numerical value is
needed use g = 9.8 unless a different value is specified in the question.
• Do not send this Question Paper for marking. Keep it in the centre or recycle it.
INFORMATION
• The total mark for this paper is 60.
• The marks for each question are shown in brackets [ ].
• This document has 8 pages.
ADVICE
• Read each question carefully before you start your answer.
© OCR 2025 [D/508/5500] DC (SL/CT) 360294/3
OCR is an exempt Charity
Turn over
1 A builder has some pieces of wood that are 6 m in length. The builder needs to cut
smaller pieces to use in a project. The lengths of the smaller pieces required are
shown below.
2.5 m 2m 4.5 m 3m 1.5 m 3.5 m
2m
, 2
(a) Use the first-fit decreasing algorithm to determine the smallest number of
6 m lengths of
wood needed to cut the seven smaller pieces.
(b) First-fit decreasing is a heuristic algorithm. Explain what this means.
[1]
The first-fit decreasing algorithm is order O(n2).
(c) It takes a computer 3.2 seconds to solve an allocation problem involving
200 items of data
using the first-fit decreasing algorithm. Calculate approximately how long it
would take to
solve an allocation problem involving 1000 items of data.
2 A student has six cards numbered from 1– 6. The cards are shown below.
1 2 3 4 5 6
(a) The student chooses four cards at random.
Use the Pigeonhole Principle to explain why they must have at least two cards
whose
numbers add to seven.
(b) The student now chooses two cards and places them side by side to form a
two-digit number.
(i) Determine the number of different two-digit numbers that the student
can make. [2]
(ii) Determine the number of different even two-digit numbers that the
student can make. [2] 3 The table shows the lengths in km of
footpaths between six places, A to F, in a town.
A B C D E F
A – 5 3 5 8 10
B 5 – 6 2 7 5
C 3 6 – 1 10 8
D 5 2 1 – 9 4
E 8 7 10 9 – 3
© OCR 2025 Y534/01 Jun25
, 3
F 10 5 8 4 3 –
(a) Apply the tabular form of Prim’s algorithm, starting at A, to the copy of the
table in the Printed Answer Booklet to construct a minimum spanning
tree for the six places in the town. You should state the order in which the
arcs are added to the tree.
Draw the minimum spanning tree and find its weight.
(b) Sam needs to walk from A to F.
Give an example of a question Sam could ask which leads to an enumeration
problem. [1]
(c) Use an appropriate algorithm to find the shortest route from A to F. You
must state its length.
© OCR 2025 Y534/01 Jun25 Turn over
, 4
4 Ryan and Casey play a game.
They can each choose to play one of three options.
Ryan can play options A, B and C and Casey can play options X, Y and Z.
The scores for each player for each combination of choices are shown in the pay-off
matrices below:
Scores for Ryan
Casey’s
Options
X Y Z
Ryan’s A 1 4 3
Options B 5 3 4
C 3 1 3
Scores for Casey
Casey’s
Options
X Y Z
Ryan’s A 5 2 3
Options B 1 3 2
(a) Explain C 3 5 3 how the game between Ryan and Casey
can be expressed as the zero-sum game with the pay-off matrix below (the entries
represent pay-offs for Ryan). [1]
Casey’s
Options
X Y Z
Ryan’s A –2 1 0
Options B 2 0 1
C 0 –2 0
(b) If Casey knows that Ryan will play option A, state the option that Casey should play.
[1]
(c) Find the play-safe strategies for both players. [3]
(d) Determine whether or not the game is stable. [1]
#
(e) Use a dominance argument to reduce the zero-sum game to a 2 3 game. [1]
(f) Let p be the probability that Ryan plays option A on the reduced game from part (e).
© OCR 2025 Y534/01 Jun25
