Questions - OCR Further Discrete AS

A medium jar takes up the same space as four small jars.
A large jar takes up the same space as nine small jars.

Each crate can hold:

at most 12 small jars,
or at most 3 medium jars,
or at most 1 large jar (and 3 small jars),
or a mixture of jars of different sizes.
1. One strategy is to fill as many crates as possible with small jars first, then continue using the medium jars and finally the large jars.

Show that this method will use seven crates. The jars can be packed using fewer than seven crates.

The jars are to be packed in the minimum number of crates possible.

Describe how the jars can be packed in the minimum number of crates.
Explain how you know that this is the minimum number of crates.

Some other numbers of the small, medium and large jars need to be packed into boxes.
The number of jars that a box can hold is the same as for a crate, except that

a box cannot hold 3 medium jars.
Describe a packing strategy that will minimise the number of boxes needed.

OCR Further Discrete AS 2018 June Q2

2 Mo eats exactly 6 doughnuts in 4 days.

What does the pigeonhole principle tell you about the number of doughnuts Mo eats in a day? Mo eats exactly 6 doughnuts in 4 days, eating at least 1 doughnut each day.
Show that there must be either two consecutive days or three consecutive days on which Mo eats a total of exactly 4 doughnuts. Mo eats exactly 3 identical jam doughnuts and exactly 3 identical iced doughnuts over the 4 days.
The number of jam doughnuts eaten on the four days is recorded as a list, for example $1,0,2,0$. The number of iced doughnuts eaten is not recorded.
Show that 20 different such lists are possible.

OCR Further Discrete AS 2018 June Q3

3 In the pay-off matrix below, the entry in each cell is of the form $( r , c )$, where $r$ is the pay-off for the player on rows and $c$ is the pay-off for the player on columns when they play that cell.

	P	Q	R
X	$( 1,4 )$	$( 5,3 )$	$( 2,6 )$
Y	$( 5,2 )$	$( 1,3 )$	$( 0,1 )$
Z	$( 4,3 )$	$( 3,1 )$	$( 2,1 )$

Show that the play-safe strategy for the player on columns is P .
Demonstrate that the game is not stable. The pay-off for the cell in row Y , column P is changed from $( 5,2 )$ to $( y , p )$, where $y$ and $p$ are real numbers.
What is the largest set of values $A$, so that if $y \in A$ then row Y is dominated by another row?
Explain why column P can never be redundant because of dominance.

OCR Further Discrete AS 2018 June Q4

4 The complete bipartite graph $K _ { 3,4 }$ connects the vertices $\{ 2,4,6 \}$ to the vertices $\{ 1,3,5,7 \}$.

How many arcs does the graph $K _ { 3,4 }$ have?
Deduce how many different paths are there that pass through each of the vertices once and once only. The direction of travel of the path does not matter. The arcs are weighted with the product of the numbers at the vertices that they join.
(a) Use an appropriate algorithm to find a minimum spanning tree for this network.
(b) Give the weight of the minimum spanning tree.

OCR Further Discrete AS 2018 June Q5

5 Greetings cards are sold in luxury, standard and economy packs.
The table shows the cost of each pack and number of cards of each kind in the pack.

Pack	Cost (£)	Handmade cards	Cards with flowers	Cards with animals	Other cards	Total number of cards
Luxury	6.50	10	5	5	0	20
Standard	5.00	5	10	5	10	30
Economy	4.00	0	10	10	20	40

Alice needs 25 cards, of which at least 8 must be handmade cards, at least 8 must be cards with flowers and at least 4 must be cards with animals.

Explain why Alice will need to buy at least two packs of cards. Alice does not want to spend more than $\pounds 12$ on the cards.
(a) List the combinations of packs that satisfy all Alice's requirements.
(b) Which of these is the cheapest? Ben offers to buy any cards that Alice buys but does not need. He will pay 12 pence for each handmade card and 5 pence for any other card. Alice does not want her net expenditure (the amount she spends minus the amount that Ben pays her) on the cards to be more than $\pounds 12$.
Show that Alice could now buy two luxury packs. Alice decides to buy exactly 2 packs, of which $x$ are luxury packs, $y$ are standard packs and the rest are economy packs.
Give an expression, in terms of $x$ and $y$ only, for the number of cards of each type that Alice buys. Alice wants to minimise her net expenditure.
Find, and simplify, an expression for Alice's minimum net expenditure in pence, in terms of $x$ and $y$. You may assume that Alice buys enough cards to satisfy her own requirements.
Find Alice's minimum net expenditure.

OCR Further Discrete AS 2018 June Q6

6 Sheona and Tim are making a short film. The activities involved, their durations and immediate predecessors are given in the table below.

	Activity	Duration (days)	Immediate predecessors	S	T
A	Planning	2	-	✓	✓
B	Write script	1	A	✓
C	Choose locations	1	A		✓
D	Casting	0.5	A	✓
E	Rehearsals	2	B, D	✓
F	Get permissions	1	C		✓
G	First day filming	1	E, F	✓
H	First day edits	1	G		✓
I	Second day filming	0.5	G	✓
J	Second day edits	2	H, I		✓
K	Finishing	1	J	✓	✓

By using an activity network, find:
- the minimum project completion time
- the critical activities
- the float on each non-critical activity.
- Give two reasons why the filming may take longer than the minimum project completion time.
Each activity will involve either Sheona or Tim or both.
- The activities that Sheona will do are ticked in the S column.
- The activities that Tim will do are ticked in the T column.
- They will do the planning and finishing together.
- Some of the activities involve other people as well.
An additional restriction is that Sheona and Tim can each only do one activity at a time.
Explain why the minimum project completion is longer than in part (i) when this additional restriction is taken into account.
The project must be completed in 14 days. Find:
(a) the longest break that either Sheona or Tim can take,
(b) the longest break that Sheona and Tim can take together,
(c) the float on each activity.

OCR Further Discrete AS 2019 June Q1

1 Alfie has a set of 15 cards numbered consecutively from 1 to 15.
He chooses two of the cards.

How many different sets of two cards are possible? Alfie places the two cards side by side to form a number with 2,3 or 4 digits.
Explain why there are fewer than ${ } ^ { 15 } \mathrm { P } _ { 2 } = 210$ possible numbers that can be made.
Explain why, with these cards, 1 is the lead digit more often than any other digit. Alfie makes the number 113, which is a 3-digit prime number. Alfie says that the problem of working out how many 3-digit prime numbers can be made using two of the cards is a construction problem, because he is trying to find all of them.
Explain why Alfie is wrong to say this is a construction problem.

OCR Further Discrete AS 2019 June Q2

2 Two graphs are shown below. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{8473d9aa-a4db-4001-ac71-e5fbbaee530c-2_396_353_1343_479} \captionsetup{labelformat=empty} \caption{Graph G1}

\end{figure} \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{8473d9aa-a4db-4001-ac71-e5fbbaee530c-2_399_328_1340_1233} \captionsetup{labelformat=empty} \caption{Graph G2}

\end{figure}

List the vertex degrees for each graph.
Prove that the graphs are non-isomorphic. The two graphs are joined together by adding an arc connecting J and T .
1. Explain how you know that the resulting graph is not Eulerian.
2. Describe how the graph can be made Eulerian by adding one more arc. The vertices of the graph $K _ { 3 }$ are connected to the vertices of the graph $K _ { 4 }$ to form the graph $K _ { 7 }$.
Explain why 12 arcs are needed connecting $K _ { 3 }$ to $K _ { 4 }$.

OCR Further Discrete AS 2019 June Q3

Give an example of a standard sorting algorithm that can be used when some of the values are not known until after the sorting has been started. Becky needs to sort a list of numbers into increasing order.
She uses the following algorithm:
STEP 1: Let $L$ be the first value in the input list.
Write this as the first value in the output list and delete it from the input list.
STEP 2: If the input list is empty go to STEP 7.
Otherwise let $N$ be the new first value in the input list and delete this value from the input list. STEP 3: $\quad$ Compare $N$ with $L$.
STEP 4: If $N$ is less than or equal to $L$
- write the value of $N$ immediately before $L$ in the output list,
- replace $L$ with the first value in the new output list,
- then go to STEP 2.
STEP 5: If $N$ is greater than $L$
- if $L$ is the value of the last number in the output list, go to STEP 6;
- otherwise, replace $L$ with the next value in the output list and then go to STEP 3.
STEP 6: $\quad$ Write the value of $N$ immediately after $L$ in the output list. Let $L$ be the first value in the new output list and then go to STEP 2. STEP 7: Print the output list and STOP.
Trace through Becky's algorithm when the input list is $$\begin{array} { l l l l l l } 6 & 9 & 5 & 7 & 6 & 4 \end{array}$$ Complete the table in the Printed Answer Booklet, starting a new row each time that STEP 3 or STEP 7 is used.
You should not need all the lines in the Answer Booklet. Becky measures the efficiency of her sort by counting using the number of times that STEP 3 is used.
1. How many times did Becky use STEP 3 in sorting the list from part (b)?
2. What is the greatest number of times that STEP 3 could be used in sorting a list of 6 values? A computer takes 15 seconds to sort a list of 60 numbers using Becky's algorithm.
Approximately how long would you expect it to take the computer to sort a list of 300 numbers using the algorithm?

OCR Further Discrete AS 2019 June Q4

4 The table shows the activities involved in a project, their durations in hours and their immediate predecessors. The activities can be represented as an activity network.

Activity	A	B	C	D	E	F	G	H
Duration	2	4	5	4	3	3	2	4
Immediate predecessors	-	A	-	A, C	B, C	B, D	D, E	F, G

Use standard algorithms to find the activities that form
- the longest path(s)
- the shortest path(s)
  through the activity network.
You must show working to demonstrate the use of the algorithms. Only one of the paths from part (a) has a practical interpretation.
What is the practical interpretation of the total weight of that path? The duration of activity E can be changed. No other durations change.
What is the smallest increase to the duration of E that will make activity E become part of a longest path through the network?

OCR Further Discrete AS 2019 June Q5

5 Corey is training for a race that starts in 18 hours time. He splits his training between gym work, running and swimming.

At most 8 hours can be spent on gym work.
At least 4 hours must be spent running.
The total time spent on gym work and swimming must not exceed the time spent running.

Corey thinks that time spent on gym work is worth 3 times the same time spent running or 2 times the same time spent swimming. Corey wants to maximise the worth of the training using this model.

Formulate a linear programming problem to represent Corey's problem. Your formulation must include defining the variables that you are using. Suppose that Corey spends the maximum of 8 hours on gym work.
1. Use a graphical method to determine how long Corey should spend running and how long he should spend swimming.
2. Describe why this solution is not practical.
3. Describe how Corey could refine the LP model to make the solution more realistic.

OCR Further Discrete AS 2019 June Q6

6 Drew and Emma play a game in which they each choose a strategy and then use the tables below to determine the pay-off that each receives.

Drew's pay-off		Emma
		X	Y	Z
\cline { 2 - 5 } \multirow{2}{*}{Drew}	P	3	14	11
	Q	12	4	7
	R	11	4	6

Emma's pay-off		Emma
		X	Y	Z
\cline { 2 - 5 } \multirow{3}{*}{Drew}	P	13	2	5
	Q	4	12	9
	R	5	12	10

Convert the game into a zero-sum game, giving the pay-off matrix for Drew.
Determine the optimal mixed strategy for Drew.
Determine the optimal mixed strategy for Emma.

OCR Further Discrete AS 2022 June Q1

1 The flowchart below has positive inputs $X , Y$ and $M$.
\includegraphics[max width=\textwidth, alt={}, center]{74b6f747-7045-4902-8b21-0b59c007f7f6-2_1274_643_392_242}

Trace through the flowchart above using the inputs $X = 1 , Y = 2$ and $M = 2$. You only need to record values when they change.
Explain why the process in the flowchart is finite.

OCR Further Discrete AS 2022 June Q2

2 The activities involved in a project and their durations, in hours, are represented in the activity network below.
\includegraphics[max width=\textwidth, alt={}, center]{74b6f747-7045-4902-8b21-0b59c007f7f6-3_446_1139_338_230}

Carry out a forward pass and a backward pass through the network.
Calculate the float for each activity. A delay means that activity B cannot finish until $t$ hours have elapsed from the start of the project.
Determine the maximum value of $t$ for which the project can be completed in 16 hours.

OCR Further Discrete AS 2022 June Q3

The list below is to be sorted into increasing order using bubble sort.
$\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}$
1. Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
2. Write down the number of comparisons and the number of swaps used in each of these passes.
The list below is to be sorted into increasing order using shuttle sort.
$\begin{array} { l l l l l l l l l l } 52 & 38 & 15 & 61 & 27 & 49 & 10 & 33 & 96 & 74 \end{array}$
1. Determine the list that results at the end of the first, second and third passes. You do not need to show the individual swaps in each pass.
2. Write down the number of comparisons and the number of swaps used in each of these passes.
Use the results from parts (a) and (b) to compare the efficiency of bubble sort with the efficiency of shuttle sort for the first three passes of this list. You do not need to consider what happens after these three passes.

OCR Further Discrete AS 2022 June Q4

4 Kareem and Sam play a game in which each holds a hand of three cards.

Kareem's cards are numbered 1, 2 and 5.
Sam's cards are numbered 3, 4 and 6 .

In each round Kareem and Sam simultaneously choose a card from their hand, they show their chosen card to the other player and then return the card to their own hand.

If the sum of the numbers on the cards shown is even then the number of points that Kareem scores is $2 k$, where $k$ is the number on Kareem's card.
If the sum of the numbers on the cards shown is odd then the number of points that Kareem scores is $4 - s$, where $s$ is the number on Sam's card.
1. Complete the pay-off matrix for this game, to show the points scored by Kareem.
2. Write down which card Kareem should play to maximise the number of points that he scores for each of Sam’s choices.
3. Determine the play-safe strategy for Kareem.
4. Explain why Kareem should never play the card numbered 1.

Sam chooses a card at random, so each of Sam’s three cards is equally likely.

Calculate Kareem's expected score for each of his remaining choices.

OCR Further Discrete AS 2022 June Q5

5 A baker makes three types of jam-and-custard doughnuts.

Each batch of type X uses 6 units of jam and 4 units of custard.
Each batch of type Y uses 7 units of jam and 3 units of custard.
Each batch of type Z uses 8 units of jam and 2 units of custard.

The baker has 360 units of jam and 180 units of custard available. The baker has plenty of doughnut batter, so this does not restrict the number of batches made. From past experience the baker knows that they must make at most 30 batches of type X and at least twice as many batches of type Y as batches of type Z . Let $x =$ number of batches of type X made
$y =$ number of batches of type Y made
$z =$ number of batches of type Z made.

Set up an LP formulation for the problem of maximising the total number of batches of doughnuts made. The baker finds that type Z doughnuts are not popular and decides to make zero batches of type Z .
Use a graphical method to find how many batches of each type the baker should make to maximise the total number of batches of doughnuts made.
Give a reason why this solution may not be practical. The baker finds that some of the jam has been used so there are only $k$ units of jam (where $k < 360$ ).
There are still 180 units of custard available and the baker still makes zero batches of type Z .
Find the values of $k$ if exactly one of the other (non-trivial) constraints is redundant. Express your answer using inequalities.

OCR Further Discrete AS 2022 June Q6

6 Eight footpaths connect six villages. The lengths of these footpaths, in km , are given in the table.

Villages connected	A B	A D	B E	B F	C D	C E	D E	E F
Length of footpath, km	3	2	4	6	5	7	3	1

The shortest route from B to C using these footpaths has length 10 km . Without using an algorithm, write down this shortest route from B to C.
Use an appropriate algorithm to find the shortest route from A to F .
Write down all the pairs of villages for which the shortest route between them uses at least one footpath that is not in the minimum spanning tree for the six villages.

OCR Further Discrete AS 2022 June Q7

1 marks

List the 15 partitions of the set $\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } \}$ in which A and E are in the same subset.
By considering the number of subsets in each of the partitions in part (a), or otherwise, explain why there are 8 partitions of the set $\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } \}$ into two subsets with A and E in different subsets. Ali says that each of the 15 partitions from part (a) can be used to give two partitions in which A and E are in different subsets by moving E into a subset on its own or by moving E into another subset.
[0pt]
1. By considering the partition from part (a) into just one subset, show that Ali is wrong. [1]
2. By considering a partition from part (a) into more than two subsets, show that Ali is wrong.

OCR Further Discrete AS 2023 June Q1

1 Jane wants to travel from home to the local town. Jane can do this by train, by bus or by both train and bus.

Give an example of a problem that Jane could be answering that would give a construction problem. A website gives Jane all the possible buses and trains that she could use.
Jane finds 7 possible ways to make the journey.
- 2 of the 7 journeys involve travelling by train for at least part of the journey
- 6 of the 7 journeys involve travelling by bus for at least part of the journey
- Use the inclusion-exclusion principle to find how many of the 7 journeys involve travelling by both train and bus.

OCR Further Discrete AS 2023 June Q2

2 A network is shown below.
\includegraphics[max width=\textwidth, alt={}, center]{c9fb5dad-1069-46cd-b167-80b77016f03c-2_533_869_1160_244}

Use an appropriate algorithm to find the least weight (shortest) path from A to D.
Use Kruskal's algorithm to find a minimum spanning tree for the network.

OCR Further Discrete AS 2023 June Q3

3 The list of numbers below is to be sorted into increasing order.
$\begin{array} { l l l l l l l l } 23 & 10 & 18 & 7 & 62 & 54 & 31 & 82 \end{array}$

Sort the list using bubble sort. You do not need to show intermediate working.
1. Record the list that results at the end of each pass.
2. Record the number of swaps used in each pass.
Now sort the original list using shuttle sort. You do not need to show intermediate working.
1. Record the list that results at the end of each pass.
2. Record the number of swaps used in each pass.
Using the total number of comparisons plus the total number of swaps as a measure of efficiency, explain why shuttle sort is more efficient than bubble sort for sorting this particular list. Bubble sort and shuttle sort are both $\mathrm { O } \left( n ^ { 2 } \right)$.
Explain what this means for the run-time of the algorithms when the length of the list being sorted changes from 1000 to 3000.

OCR Further Discrete AS 2023 June Q4

4 Graph G is a simply connected Eulerian graph with 4 vertices.

1. Explain why graph G cannot be a complete graph.
2. Determine the number of arcs in graph G, explaining your reasoning.
3. Show that graph G is a bipartite graph. Graph H is a digraph with 4 vertices and no undirected arcs. The adjacency matrix below shows the number of arcs that directly connect each pair of vertices in digraph H . From \begin{table}[h]
  \captionsetup{labelformat=empty} \caption{To}
  A B C D
  A 0 1 0 1
  B 0 0 2 0
  C 2 1 0 1
  D 0 1 1 0
  \end{table}
1. Write down a feature of the adjacency matrix that shows that H has no loops.
2. Find the number of $\operatorname { arcs }$ in H .
3. Draw a possible digraph H .
4. Show that digraph H is semi-Eulerian by writing down a suitable trail.

OCR Further Discrete AS 2023 June Q5

5 Hiro has been asked to organise a quiz.
The table below shows the activities involved, together with the immediate predecessors and the duration of each activity in hours.

	Activity	Immediate predecessors	Duration (hours)
A	Choose the topics	-	0.5
B	Find questions for round 1	A	2
C	Check answers for round 1	B	2.5
D	Find questions for round 2	A	2
E	Check answers for round 2	D	2.5
F	Choose pictures for picture round	A	1
G	Get permission to use pictures	F	1.5
H	Choose music for music round	A	2
I	Get permission to use music	H	1.5
J	Produce answer sheets	G	0.5

A sketch of the activity network is provided in the Printed Answer Booklet. Apply a forward pass to determine the minimum project completion time.
Use a backward pass to determine the critical activities. You can show your working on the activity network from part (a).
Give the total float for each non-critical activity. Hiro decides that there should be a final check of the answers which he will include as activity $L$. Activity L needs to be done after checking the answers for rounds 1 and 2 and also after getting permission to use the pictures and music but before producing the answer sheets.
1. Complete the activity network provided in the Printed Answer Booklet to show the new precedences, with the final check of the answers included as activity $L$.
2. As a result of including L , the minimum project completion time found in part (a) increases by 2.5 hours. Determine the duration of L .

OCR Further Discrete AS 2023 June Q6

6 Ryan and Casey are playing a card game in which they each have four cards.

Ryan's cards have the letters A, B, C and D.
Casey's cards have the letters W, X, Y and Z.

Each player chooses one of their four cards and they simultaneously reveal their choices. The table shows the number of points won by Ryan for each combination of strategies. \begin{table}[h]

\captionsetup{labelformat=empty} \caption{Casey}

		W	X	Y	Z
\cline { 2 - 6 } Ryan	A	4	0	2	1
	B	0	2	- 3	4
	C	1	4	- 4	5
	D	6	- 1	5	0

\end{table} For example, if Ryan chooses A and Casey chooses W then Ryan wins 4 points (and Casey loses 4 points). Both Ryan and Casey are trying to win as many points as possible.

Use dominance to reduce the $4 \times 4$ table for the zero-sum game above to a $4 \times 2$ table.
Determine an optimal mixed strategy for Casey.

	P	Q	R
X	\(( 1,4 )\)	\(( 5,3 )\)	\(( 2,6 )\)
Y	\(( 5,2 )\)	\(( 1,3 )\)	\(( 0,1 )\)
Z	\(( 4,3 )\)	\(( 3,1 )\)	\(( 2,1 )\)

Questions — OCR Further Discrete AS (52 questions)

Browse by module

Browse by board

OCR Further Discrete AS 2018 June Q1

OCR Further Discrete AS 2018 June Q2

OCR Further Discrete AS 2018 June Q3

OCR Further Discrete AS 2018 June Q4

OCR Further Discrete AS 2018 June Q5

OCR Further Discrete AS 2018 June Q6

OCR Further Discrete AS 2019 June Q1

OCR Further Discrete AS 2019 June Q2

OCR Further Discrete AS 2019 June Q3

OCR Further Discrete AS 2019 June Q4

OCR Further Discrete AS 2019 June Q5

OCR Further Discrete AS 2019 June Q6

OCR Further Discrete AS 2022 June Q1

OCR Further Discrete AS 2022 June Q2

OCR Further Discrete AS 2022 June Q3

OCR Further Discrete AS 2022 June Q4

OCR Further Discrete AS 2022 June Q5

OCR Further Discrete AS 2022 June Q6

OCR Further Discrete AS 2022 June Q7

OCR Further Discrete AS 2023 June Q1

OCR Further Discrete AS 2023 June Q2

OCR Further Discrete AS 2023 June Q3

OCR Further Discrete AS 2023 June Q4

OCR Further Discrete AS 2023 June Q5

OCR Further Discrete AS 2023 June Q6