Questions - OCR Further Discrete

Browse by module

All questions AEA AS Paper 1 AS Paper 2 AS Pure C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Extra Pure Further Mechanics Further Mechanics A AS Further Mechanics AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics Further Paper 4 Further Pure Core Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Pure with Technology Further Statistics Further Statistics A AS Further Statistics AS Further Statistics B AS Further Statistics Major Further Statistics Minor Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 H240/01 H240/02 H240/03 M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 S1 S2 S3 S4 Unit 1 Unit 2 Unit 3 Unit 4

Browse by board

AQA AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further AS Paper 1 Further AS Paper 2 Discrete Further AS Paper 2 Mechanics Further AS Paper 2 Statistics Further Paper 1 Further Paper 2 Further Paper 3 Discrete Further Paper 3 Mechanics Further Paper 3 Statistics M1 M2 M3 Paper 1 Paper 2 Paper 3 S1 S2 S3 CAIE FP1 FP2 Further Paper 1 Further Paper 2 Further Paper 3 Further Paper 4 M1 M2 P1 P2 P3 S1 S2 Edexcel AEA AS Paper 1 AS Paper 2 C1 C12 C2 C3 C34 C4 CP AS CP1 CP2 D1 D2 F1 F2 F3 FD1 FD1 AS FD2 FD2 AS FM1 FM1 AS FM2 FM2 AS FP1 FP1 AS FP2 FP2 AS FP3 FS1 FS1 AS FS2 FS2 AS M1 M2 M3 M4 M5 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 OCR AS Pure C1 C2 C3 C4 D1 D2 FD1 AS FM1 AS FP1 FP1 AS FP2 FP3 FS1 AS Further Additional Pure Further Additional Pure AS Further Discrete Further Discrete AS Further Mechanics Further Mechanics AS Further Pure Core 1 Further Pure Core 2 Further Pure Core AS Further Statistics Further Statistics AS H240/01 H240/02 H240/03 M1 M2 M3 M4 PURE S1 S2 S3 S4 OCR MEI AS Paper 1 AS Paper 2 C1 C2 C3 C4 D1 D2 FP1 FP2 FP3 Further Extra Pure Further Mechanics A AS Further Mechanics B AS Further Mechanics Major Further Mechanics Minor Further Numerical Methods Further Pure Core Further Pure Core AS Further Pure with Technology Further Statistics A AS Further Statistics B AS Further Statistics Major Further Statistics Minor M1 M2 M3 M4 Paper 1 Paper 2 Paper 3 S1 S2 S3 S4 Pre-U Pre-U 9794/1 Pre-U 9794/2 Pre-U 9794/3 Pre-U 9795 Pre-U 9795/1 Pre-U 9795/2 WJEC Further Unit 1 Further Unit 2 Further Unit 3 Further Unit 4 Further Unit 5 Further Unit 6 Unit 1 Unit 2 Unit 3 Unit 4

Sort by: Default | Easiest first | Hardest first

OCR Further Discrete 2024 June Q5

18 marks Moderate -0.3

Write down a way in which the nearest neighbour method can fail to solve the problem of finding a least weight cycle through all the vertices of a network.
Explain why, when trying to find a least weight cycle through all the vertices of a network, an ad hoc method may be preferable to an algorithmic approach. The distance matrix below represents a network connecting six viewpoints $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }$ and F . The distance matrix shows the direct distances between each pair of viewpoints where a direct route exists.
The distances are measured in km.
A blank shows that there is no direct route between the two viewpoints.
A B C D E F
A 6 4
B 6 5 2 9
C 5 15 7 6
D 4 2 15 5
E 9 7 5
F 6
Draw the network on the vertices given in the Printed Answer Booklet.
Apply the nearest neighbour method, starting from A. A hiker wants to travel between the six viewpoints, starting and finishing at A.
The hiker must visit every viewpoint at least once, but may visit a viewpoint more than once.
Show that the hiker does not need to travel as far as 50 km .
Use an appropriate algorithm to find the shortest distance from F to each of the other viewpoints.
Complete the table in the Printed Answer Book to show the shortest distance between each pair of viewpoints.
Use your answer to part (g) to find a lower bound for the distance the hiker must travel by initially deleting vertex A.

OCR Further Discrete 2024 June Q6

16 marks Challenging +1.2

6 Sasha is making three identical bead bracelets using amber, brown and red coloured beads. Sasha has 20 amber beads, 12 brown beads and 10 red beads. Each bracelet must use exactly 12 beads.
The profit from selling a bracelet is 6 pence for each amber bead used plus 2 pence for each brown bead used plus 3 pence for each red bead used. Sasha wants to maximise the total profit from selling the three bracelets.

Express Sasha's problem as a linear programming formulation in two variables $a$ and $b$, where $a$ represents the number of amber beads in each bracelet and $b$ represents the number of brown beads in each bracelet.
Determine how many beads of each colour will be used in each bracelet.
By listing all the feasible solutions, identify an aspect of the optimal solution, other than the profit, that is different from all the other feasible solutions. The beads that are not used in making the bracelets can be sold. The profit from selling each amber bead is $k$ pence, where $k$ is an integer, but nothing for each brown or red bead sold. All the previous constraints still apply. Instead of maximising the profit from the bracelets, Sasha wants to maximise the total profit from selling the bracelets and any left over beads. You are given that the optimal solution to the earlier problem does not maximise the total profit from selling the bracelets and any left over beads.
Determine the least possible value of Sasha's maximum total profit.
Why might Sasha not achieve this maximum profit?

OCR Further Discrete 2020 November Q1

9 marks Challenging +1.2

1 This question is about the planar graph shown below. \includegraphics[max width=\textwidth, alt={}, center]{cc58fb7a-efb6-4548-a8e1-e40abe1eb722-2_567_1317_395_374}

1. Apply Kuratowski's theorem to verify that the graph is planar.
2. Use Euler's formula to calculate the number of regions in a planar representation of the graph.
1. Write down a Hamiltonian cycle for the graph.
2. By finding a suitable pair of vertices, show that Ore's theorem cannot be used to prove that the graph, as shown above, is Hamiltonian.
1. Draw the graph formed by using the contractions AB and CF .
2. Use Ore's theorem to show that this contracted graph is Hamiltonian.

OCR Further Discrete 2020 November Q2

14 marks Challenging +1.2

2 Annie and Brett play a two-person, simultaneous play game. The table shows the pay-offs for Annie and Brett in the form ( $a , b$ ). So, for example, if Annie plays strategy K and Brett plays strategy S, Annie wins 2 points and Brett wins 6 points.

		Brett
		R	S	T
\cline { 3 - 5 } \multirow{3}{*}{Annie}	K	$( 7,3 )$	$( 2,6 )$	$( 5,3 )$
\cline { 3 - 5 }	L	$( 1,5 )$	$( 8,2 )$	$( 2,5 )$
\cline { 3 - 5 }	M	$( 3,2 )$	$( 1,5 )$	$( 4,6 )$
\cline { 3 - 5 }
\cline { 3 - 5 }

1. Determine the play-safe strategy for Annie.
2. Show that the play-safe strategy for Brett is T.
1. If Annie knows that Brett is planning on playing strategy T, which strategy should Annie play to maximise her points?
2. If Brett knows that Annie is planning on playing the strategy identified in part (b)(i), which strategy should Brett play to maximise his points?
Show that, for Brett, strategy R is weakly dominated.
Using a graphical method, determine the optimal mixed strategy for Brett.
Show that the game has no Nash equilibrium points.

OCR Further Discrete 2020 November Q3

12 marks Standard +0.3

3 An initial simplex tableau is shown below.

$P$	$x$	$y$	$z$	$s$	$t$	RHS
1	-3	1	0	0	0	0
0	2	0	1	1	0	18
0	-1	2	3	0	1	20

Write down the objective for the problem that is represented by this initial tableau. Variables $s$ and $t$ are slack variables.
Use the final row of the initial tableau to explain what a slack variable is.
Carry out one iteration of the simplex algorithm and hence:

OCR Further Discrete 2020 November Q4

10 marks Challenging +1.2

Show that there are 127 ways to partition a set of 8 distinct elements into two non-empty subsets. A group of 8 people ( $\mathrm { A } , \mathrm { B } , \ldots$ ) have 8 reserved seats ( $1,2 , \ldots$ ) on a coach. Seat 1 is reserved for person A , seat 2 for person B , and so on. The reserved seats are labelled but the individual people do not know which seat has been reserved for them. The first 4 people, $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D , choose their seats at random from the 8 reserved seats.
Determine how many different arrangements there are for the seats chosen by $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D . The group organiser moves $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D to their correct seats (A in seat $1 , \mathrm {~B}$ in seat $2 , \mathrm { C }$ in seat 3 and D in seat 4).
The other 4 people ( $\mathrm { E } , \mathrm { F } , \mathrm { G }$ and H ) then choose their seats at random from the remaining 4 reserved seats ( $5,6,7$ and 8 ).
List the 9 derangements of $\{ \mathrm { E } , \mathrm { F } , \mathrm { G } , \mathrm { H } \}$, where none of these four people is in the seat that has been reserved for them. Suppose, instead, that the 8 people had chosen their seats at random from the 8 reserved seats, without the organiser intervening.
Determine the total number of ways in which the seats can be chosen so that 4 of the people are in their correct seats and 4 are not in their correct seats.

OCR Further Discrete 2020 November Q5

17 marks Moderate -0.3

5 The manager of a farm shop wants to pave routes on the farm so that, after visiting the shop, customers can visit the animals in fields A, B, C, D and E.
The table shows the cost, in $\pounds$, of making a paved path between each pair of fields.
A river means that it is not possible to make a paved path between C and E .

$\mathrm { A } , \mathrm { B }$	$\mathrm { A } , \mathrm { C }$	$\mathrm { A } , \mathrm { D }$	$\mathrm { A } , \mathrm { E }$	$\mathrm { B } , \mathrm { C }$	$\mathrm { B } , \mathrm { D }$	$\mathrm { B } , \mathrm { E }$	$\mathrm { C } , \mathrm { D }$	$\mathrm { C } , \mathrm { E }$	$\mathrm { D } , \mathrm { E }$
300	500	900	700	200	600	400	500	-	100

Determine the minimum cost of connecting the fields.
1. By applying the lower bound algorithm to each vertex in turn, determine a best lower bound for $P$, the minimum cost of making a circular tour (cycle) of paved paths that visits each field once.
2. By applying the nearest neighbour algorithm, starting at each vertex in turn, find a best upper bound for $P$. You do not need to attempt any route improvements.
3. Give the order in which the fields are visited in a circular tour of paved paths that corresponds to the best upper bound found in part (b)(ii).
Give a practical reason why the total cost of paving for the project might be more than the best upper bound found in part (b)(ii). It becomes possible to use an existing bridge to make a paved route between C and E . Using this bridge, there is a new indirect route from A to D that costs less than $\pounds 900$ to pave.
When this bridge is used, what can be determined about the minimum cost of
1. paving the route between C and E
2. connecting all the fields?

OCR Further Discrete 2020 November Q6

13 marks Standard +0.3

6 A project is represented by the activity on arc network below. \includegraphics[max width=\textwidth, alt={}, center]{cc58fb7a-efb6-4548-a8e1-e40abe1eb722-7_410_1095_296_486} The duration of each activity (in minutes) is shown in brackets, apart from activity I.

Suppose that the minimum completion time for the project is 15 minutes.
1. By calculating the early event times, determine the range of values for $x$.
2. By calculating the late event times, determine which activities must be critical. The table shows the number of workers needed for each activity.
  Activity A B C D E F G H I J K
  Workers 2 1 1 2 $n$ 1 2 1 1 1 4
Determine the maximum possible value for $n$ if 5 workers can complete the project in 15 minutes. Explain your reasoning. The duration of activity F is reduced to 1.5 minutes, but only 4 workers are available. The minimum completion time is no longer 15 minutes.
Determine the minimum project completion time in this situation.
Find the maximum possible value for $x$ for this minimum project completion time.
Find the maximum possible value for $n$ for this minimum project completion time.

OCR Further Discrete 2021 November Q1

8 marks Moderate -0.3

1 Sam is packing for a holiday. The table shows the mass of each item to be packed.

Item	$A$	$B$	$C$	$D$	$E$	$F$	$G$	$H$
Mass (kg)	3	4	3.5	2.5	6	7.5	8	5

Sam's bags can each carry 10 kg , but no more.

Use first-fit to show a possible packing that Sam could use. Indicate the items by using the letters $A , B , \ldots$ rather than their masses. The total mass of the 8 items is 39.5 kg . Sam says that this means they can be packed using just 4 bags.
Explain why Sam cannot pack the items using just 4 bags. Sam is only allowed to take 4 bags. Each item is given a value out of 20 representing how important it is to Sam.
Item $A$ $B$ $C$ $D$ $E$ $F$ $G$ $H$
Mass (kg) 3 4 3.5 2.5 6 7.5 8 5
Value 6 10 12 10 16 12 20 14
Sam wishes to pack items with a large total value.

OCR Further Discrete 2021 November Q2

8 marks Standard +0.3

2 A simply connected semi-Eulerian graph G has 6 vertices and 8 arcs. Two of the vertex degrees are 3 and 4.

1. Determine the minimum possible vertex degree.
2. Determine the maximum possible vertex degree.
Write down the two possible degree sequences (ordered lists of vertex degrees). The adjacency matrix for a digraph H is given below.
\multirow{7}{*}{From} \multirow{2}{*}{} To
J K L M N
J 0 1 1 0 0
K 1 0 1 0 0
L 1 0 0 0 1
M 0 0 2 1 1
N 0 1 0 1 0
Write down the indegree and the outdegree of each vertex of H .
1. Use the indegrees and outdegrees to determine whether graph H is Eulerian.
2. Use the adjacency matrix to determine whether graph H is simply connected.

OCR Further Discrete 2021 November Q3

8 marks Standard +0.3

3 Six people play a game with 150 cards. Each player has a stack of cards in front of them and the remainder of the cards are in another stack on the table.

Use the pigeonhole principle to explain why at least one of the stacks must have at least 22 cards in it. The set of cards is numbered from 1 to 150 . Each digit '2', '3' and '5', whether as a units digit or a tens digit, is coloured red.
So, for example
The cards are put into a Venn diagram with three intersecting sets: $\mathrm { A } = \{$ cards with a number that is a multiple of $2 \}$ $\mathrm { B } = \{$ cards with a number that is a multiple of $3 \}$ $\mathrm { C } = \{$ cards with a number that is a multiple of $5 \}$ For example

OCR Further Discrete 2021 November Q4

13 marks Moderate -0.3

4 One of these graphs is isomorphic to $\mathrm { K } _ { 2,3 }$. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{133395d2-5020-4054-a229-70168f1d0f95-5_175_195_285_242} \captionsetup{labelformat=empty} \caption{Graph A}

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

\includegraphics[alt={},max width=\textwidth]{133395d2-5020-4054-a229-70168f1d0f95-5_170_195_285_635} \captionsetup{labelformat=empty} \caption{Graph B}

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

\includegraphics[alt={},max width=\textwidth]{133395d2-5020-4054-a229-70168f1d0f95-5_168_191_287_1027} \captionsetup{labelformat=empty} \caption{Graph C}

\end{figure}

Explain how you know that each of the other graphs is not isomorphic to $\mathrm { K } _ { 2,3 }$. The arcs of the complete graph $\mathrm { K } _ { 5 }$ can be partitioned as the complete bipartite graph $\mathrm { K } _ { 2,3 }$ and a graph G.
Draw the graph G.
Explain carefully how you know that the graph $\mathrm { K } _ { 5 }$ has thickness 2 . The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, $\alpha$ and $\beta$. STEP 1 Choose a vertex and assign it colour $\alpha$.
STEP 2 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour $\beta$ to each vertex that is adjacent to a vertex with colour $\alpha$. STEP 3 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour $\alpha$ to each vertex that is adjacent to a vertex with colour $\beta$. STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.
STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite. Otherwise the graph is not bipartite. STEP 6 Stop.
Apply this algorithm to graph A, starting with the vertex in the top left corner, to determine whether graph A is bipartite or not. A measure of the efficiency of the colouring algorithm is given by the number of passes through STEP 4.
Write down how many passes through STEP 4 are needed for the bipartite graph $\mathrm { K } _ { 2,3 }$. The worst case is when the graph is a path that starts at one vertex and ends at another, having passed through each of the other vertices once.
What can you deduce about the efficiency of the colouring algorithm in this worst case? The colouring algorithm is used on two graphs, X and Y . It takes 10 seconds to run for graph X and 60 seconds to run for graph Y. Graph X has 1000 vertices.
Estimate the number of vertices in graph Y . A different algorithm has efficiency $\mathrm { O } \left( 2 ^ { n } \right)$. This algorithm takes 10 seconds to run for graph X .
Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y .

OCR Further Discrete 2021 November Q5

12 marks Challenging +1.8

5 Alex and Beth play a zero-sum game. Alex chooses a strategy P, Q or R and Beth chooses a strategy $\mathrm { X } , \mathrm { Y }$ or Z . The table shows the number of points won by Alex for each combination of strategies. The entry for cell $( \mathrm { P } , \mathrm { X } )$ is $x$, where $x$ is an integer. \begin{table}[h]

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

		X	Y	Z
\cline { 3 - 5 }	P	$x$	3	2
\cline { 3 - 5 }	Q	4	0	- 2
\cline { 3 - 5 }	R	- 3	- 1	- 3
\cline { 3 - 5 }
\cline { 3 - 5 }

\end{table} Suppose that P is a play-safe strategy.

1. Determine the values of $x$ for which the game is stable.
2. Determine the values of $x$ for which the game is unstable. The game can be reduced to a $2 \times 3$ game using dominance.
Write down the pay-off matrix for the reduced game. When the game is unstable, Alex plays strategy P with probability $p$.
Determine, as a function of $x$, the value of $p$ for the optimal mixed strategy for Alex. Suppose, instead, that P is not a play-safe strategy and the value of $x$ is - 5 .
Show how to set up a linear programming formulation that could be used to find the optimal mixed strategy for Alex.

OCR Further Discrete 2021 November Q6

11 marks Moderate -0.5

6 An initial simplex tableau is shown below.

$P$	$x$	$y$	$s$	$t$	$u$	RHS
1	2	-5	0	0	0	0
0	2	1	1	0	0	25.8
0	-1	3	0	1	0	13.8
0	4	-3	0	0	1	18.8

The variables $s , t$ and $u$ are slack variables.

For the LP problem that this tableau represents, write down the following, in terms of $x$ and $y$ only.
The graph below shows the feasible region for the problem (as the unshaded region, and its boundaries), and objective lines $P = 10$ and $P = 20$ (shown as dotted lines). \includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-7_883_1043_1272_244} The optimal solution is $P = 23$, when $x = 0$ and $y = 4.6$.
Complete the first three rows of branch-and-bound in the Printed Answer Booklet, branching on $y$ first, to determine an optimal solution when $x$ and $y$ are constrained to take integer values. In your working, you should show non-integer values to $\mathbf { 2 }$ decimal places. The tableau entry 18.8 is reduced to 0 .
Describe carefully what changes, if any, this makes to the following.

OCR Further Discrete 2021 November Q7

15 marks Moderate -0.8

7 A network is formed by weighting the graph below using the listed arc weights. \includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-8_168_190_310_258} $\begin{array} { l l l l l l l l } 2.9 & 0.9 & 1.5 & 3.5 & 4.2 & 5.3 & 4.7 & 2.3 \end{array}$

1. Show the result after the first pass and after the second pass, when the list of weights is sorted into increasing order using bubble sort.
2. Show the result after the first pass and after the second pass, when the list of weights is sorted into increasing order using shuttle sort. In the remaining passes of bubble sort another 14 comparisons are made.
  In the remaining passes of shuttle sort another 11 comparisons are made.
  The total number of swaps needed is the same for both sorting methods.
Use the total number of comparisons and the total number of swaps to compare the efficiency of bubble sort and shuttle sort for sorting this list of weights. The sorted list of arc weights for the network is as follows. $\begin{array} { l l l l l l l l } 0.9 & 1.5 & 2.3 & 2.9 & 3.5 & 4.2 & 4.7 & 5.3 \end{array}$ These weights can be given to the arcs of the graph in several ways to form different networks.
1. What is the smallest weight that does not have to appear in a minimum spanning tree for any of these networks? You must explain your reasoning.
2. Show a way of weighting the arcs, using the weights in the list, that results in the largest possible total for a minimum spanning tree. You should state the total weight of your minimum spanning tree.
3. Determine the total weight of an optimal solution of the route inspection problem for the network found in part (c)(ii). \section*{END OF QUESTION PAPER}

OCR Further Discrete Specimen Q1

13 marks Moderate -0.3

1 Fiona is a mobile hairdresser. One day she needs to visit five clients, A to E, starting and finishing at her own house at F . She wants to find a suitable route that does not involve her driving too far.

Which standard network problem does Fiona need to solve? The shortest distances between clients, in km, are given in the matrix below.
A B C D E
A - 12 8 6 4
B 12 - 10 8 10
C 8 10 - 13 10
D 6 8 13 - 10
E 4 10 10 10 -
Use the copy of the matrix in the Printed Answer Booklet to construct a minimum spanning tree for these five client locations.
State the algorithm you have used, show the order in which you build your tree and give its total weight. Draw your minimum spanning tree. The distance from Fiona's house to each client, in km, is given in the table below.
A B C D E
F 2 11 9 7 5
Use this information together with your answer to part (ii) to find a lower bound for the length of Fiona's route.
(a) Find all the cycles that result from using the nearest neighbour method, starting at F .
(b) Use these to find an upper bound for the length of Fiona's route.
Fiona wants to drive less than 35 km . Using the information in your answers to parts (iii) and (iv) explain whether or not a route exists which is less than 35 km in length.

OCR Further Discrete Specimen Q2

13 marks Standard +0.3

2 Kirstie has bought a house that she is planning to renovate. She has broken the project into a list of activities and constructed an activity network, using activity on arc.

Activity
$A$	Structural survey
$B$	Replace damp course
$C$	Scaffolding
$D$	Repair brickwork
$E$	Repair roof
$F$	Check electrics
$G$	Replaster walls

Activity
$H$	Planning
$I$	Build extension
$J$	Remodel internal layout
$K$	Kitchens and bathrooms
$L$	Decoration and furnishing
$M$	Landscape garden

\includegraphics[max width=\textwidth, alt={}, center]{0c9513fe-a471-427e-ba30-b18df11271e3-3_887_1751_1030_207}

Construct a cascade chart for the project, showing the float for each non-critical activity.
Calculate the float for remodelling the internal layout stating how much of this is independent float and how much is interfering float. Kirstie needs to supervise the project. This means that she cannot allow more than three activities to happen on any day.
Describe how Kirstie should organise the activities so that the project is completed in the minimum project completion time and no more than three activities happen on any day.

OCR Further Discrete Specimen Q3

9 marks Standard +0.8

3 Bob has been given a pile of five letters addressed to five different people. He has also been given a pile of five envelopes addressed to the same five people. Bob puts one letter in each envelope at random.

How many different ways are there to pair the letters with the envelopes?
Find the number of arrangements with exactly three letters in the correct envelopes.
(a) Show that there are two derangements of the three symbols A , B and C .
(b) Hence find the number of arrangements with exactly two letters in the correct envelopes. Let $\mathrm { D } _ { n }$ represent the number of derangements of $n$ symbols.
Explain why $\mathrm { D } _ { n } = ( n - 1 ) \times \left( \mathrm { D } _ { n - 1 } + \mathrm { D } _ { n - 2 } \right)$.
Find the number of ways in which all five letters are in the wrong envelopes.

OCR Further Discrete Specimen Q4

11 marks Standard +0.8

4 The table shows the pay-off matrix for player $A$ in a two-person zero-sum game between $A$ and $B$. Player $A$ Player $B$

	Strategy $X$	Strategy $Y$	Strategy $Z$
Strategy $P$	4	5	- 4
Strategy $Q$	3	- 1	2
Strategy $R$	4	0	2

Find the play-safe strategy for player $A$ and the play-safe strategy for player $B$. Use the values of the play-safe strategies to determine whether the game is stable or unstable.
If player $B$ knows that player $A$ will use their play-safe strategy, which strategy should player $B$ use?
Suppose that the value in the cell where both players use their play-safe strategies can be changed, but all other entries are unchanged. Show that there is no way to change this value that would make the game stable.
Suppose, instead, that the value in one cell can be changed, but all other entries are unchanged, so that the game becomes stable. Identify a suitable cell and write down a new pay-off value for that cell which would make the game stable.
Show that the zero-sum game in the table above has a Nash equilibrium and explain what this means for the players.

OCR Further Discrete Specimen Q5

13 marks Standard +0.3

5 A garden centre sells tulip bulbs in mixed packs. The cost of each pack and the number of tulips of each colour are given in the table.

	Cost $( \pounds )$	Red	White	Yellow	Pink
Pack A	50	25	25	25	25
Pack B	48	40	30	30	0
Pack C	53	20	30	40	10

Dirk is designing a floral display in which he will need the number of red tulips to be at most 50 more than the number of white tulips, and the number of white tulips to be less than or equal to twice the number of pink tulips. He has a budget of $\pounds 240$ and wants to find out which packs to buy to maximise the total number of bulbs. Dirk uses the variables $x , y$ and $z$ to represent, respectively, how many of pack A , pack B and pack C he buys. He sets up his problem as an initial simplex tableau, which is shown below. Initial tableau
Row 1
Row 2
Row 3
Row 4

$P$	$x$	$y$	$z$	$s$	$t$	$u$	RHS
1	- 1	- 1	- 1	0	0	0	0
0	0	1	- 1	1	0	0	5
0	- 5	6	2	0	1	0	0
0	50	48	53	0	0	1	240

Show how the constraint on the number of red tulips leads to one of the rows of the tableau. The tableau that results after the first iteration is shown below.
After first iteration
Row 5
Row 6
Row 7
Row 8
$P$ $x$ $y$ $z$ $s$ $t$ $u$ RHS
1 0 - 0.04 0.06 0 0 0.02 4.8
0 0 1 - 1 1 0 0 5
0 0 10.8 7.3 0 1 0.1 24
0 1 0.96 1.06 0 0 0.02 4.8
Which cell was used as the pivot?
Explain why row 2 and row 6 are the same.
(a) Read off the values of $x , y$ and $z$ after the first iteration.
(b) Interpret this solution in terms of the original problem.
Identify the variable that has become non-basic. Use the pivot row of the initial tableau to eliminate $x$ algebraically from the equation represented by Row 1 of the initial tableau. The feasible region can be represented graphically in three dimensions, with the variables $x , y$ and $z$ corresponding to the $x$-axis, $y$-axis and $z$-axis respectively. The boundaries of the feasible region are planes. Pairs of these planes intersect in lines and at the vertices of the feasible region these lines intersect.
The planes defined by each of the new basic variables being set equal to 0 intersect at a point. Show how the equations from part (v) are used to find the values $P$ and $x$ at this point. A planar graph $G$ is described by the adjacency matrix below. $\quad$ $A$ $B$ $C$ $D$ $E$ $F$ $\left( \begin{array} { c c c c c c } A & B & C & D & E & F \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \end{array} \right)$
Draw the graph $G$.
Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it.
Explain why graph $G$ cannot have a Hamiltonian cycle that includes the edge $A B$. Deduce how many Hamiltonian cycles graph $G$ has. A colouring algorithm is given below. STEP 1: Choose a vertex, colour this vertex using colour 1. STEP 2: If all vertices are coloured, STOP. Otherwise use colour 2 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 1 . STEP 3: If all vertices are coloured, STOP. Otherwise use colour 1 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 2 . STEP 4: Go back to STEP 2.
Apply this algorithm to graph $G$, starting at $E$. Explain how the colouring shows you that graph $G$ is not bipartite. By removing just one edge from graph $G$ it is possible to make a bipartite graph.
Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph. Graph $G$ is augmented by the addition of a vertex $X$ joined to each of $A , B , C , D , E$ and $F$.
Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2.

OCR Further Discrete 2018 September Q1

7 marks Standard +0.3

1 The design for the lines on a playing area for a game is shown below. The letters are not part of the design. \includegraphics[max width=\textwidth, alt={}, center]{22571082-016b-409b-bfeb-e7ebf48ccac7-2_350_855_388_605} Priya paints the lines by pushing a machine. When she is pushing the machine she is about a metre behind the point being painted. She must not duplicate any line by painting it twice.

To relocate the machine, it must be stopped and then started again to continue painting the lines.
When the machine is being relocated it must still be pushed along the lines of the design, and not 'cut across' on a diagonal for example.
The machine can be turned through $90 ^ { \circ }$ without having to be stopped.
1. What is the minimum number of times that the machine will need to be started to paint the design?

The design is horizontally and vertically symmetric. $$\mathrm { AB } = 6 \text { metres, } \mathrm { AE } = 26 \text { metres, } \mathrm { AF } = 1.5 \text { metres and } \mathrm { AS } = 9 \text { metres. }$$

(a) Find the minimum distance that Priya needs to walk to paint the design. You should show enough working to make your reasoning clear but you do not need to use an algorithmic method.
(b) Why, in practice, will the distance be greater than this?
(c) What additional information would you need to calculate a more accurate shortest distance?

OCR Further Discrete 2018 September Q2

8 marks Standard +0.8

2 A list is used to demonstrate how different sorting algorithms work.
After two passes through shuttle sort the resulting list is $$\begin{array} { l l l l l l l } 17 & 23 & 84 & 21 & 66 & 35 & 12 \end{array}$$

How many different possibilities are there for the original list? Suppose, instead, that the same sort was carried out using bubble sort on the original list.
Write down the list after two passes through bubble sort. The number of comparisons made is used as a measure of the run-time for a sorting algorithm.
For a list of six values, what is the maximum total number of comparisons made in the first two passes of
1. shuttle sort
2. bubble sort? Steve used both shuttle sort and bubble sort on a list of five values. He says that shuttle sort is more efficient than bubble sort because it made fewer comparisons in the first two passes.
3. Comment on what Steve said. The number of comparisons made when shuttle sort and bubble sort are used to sort every permutation of a list of four values is shown in the table below.
  Number of comparisons 3 4 5 6
  Shuttle sort Number of permutations 2 6 8 8
  Bubble sort Number of permutations 1 0 7 16
4. Use the information in the table to decide which algorithm you would expect to have the quicker run-time. Justify your answer with calculations.

OCR Further Discrete 2018 September Q3

9 marks Challenging +1.2

3 The pay-off matrix for a zero-sum game is

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

Show that the game does not have a stable solution.
Use a graphical technique to find the optimal mixed strategy for the player on columns.
Formulate an initial simplex tableau for the problem of finding the optimal mixed strategy for the player on rows.

OCR Further Discrete 2018 September Q4

19 marks Moderate -0.3

4 A project is represented by the activity network below. The times are in days. \includegraphics[max width=\textwidth, alt={}, center]{22571082-016b-409b-bfeb-e7ebf48ccac7-4_384_935_1110_566}

Explain the reason for each dummy activity.
Calculate the early and late event times.
Identify the critical activities.
Calculate the independent float and interfering float on activity A .
(a) Draw a cascade chart to represent the project, using the grid in the Printed Answer Booklet.
(b) Describe the effect on
The number of workers needed for each activity is shown below.
Activity A B C D E F G H
Workers 2 1 1 2 1 1 1 1
The project needs to be completed in at most 3 weeks ( 21 days).
The duration of activity D is 9 days.
Find the minimum number of workers needed. You should explain your reasoning carefully.

OCR Further Discrete 2018 September Q5

10 marks Moderate -0.8

5 Consider the problem given below: $$\begin{array} { l l } \text { Minimise } & 4 \mathrm { AB } + 7 \mathrm { AC } + 8 \mathrm { BD } + 5 \mathrm { CD } + 5 \mathrm { CE } + 6 \mathrm { DF } + 3 \mathrm { EF } \\ \text { subject to } & \mathrm { AB } , \mathrm { AC } , \mathrm { BD } , \mathrm { CD } , \mathrm { CE } , \mathrm { DF } \text { and } \mathrm { EF } \text { are each either } 0 \text { or } 1 \\ & \mathrm { AB } + \mathrm { AC } + \mathrm { BD } + \mathrm { CD } + \mathrm { CE } + \mathrm { DF } + \mathrm { EF } = 5 \\ & \mathrm { AB } + \mathrm { AC } \geqslant 1 , \quad \mathrm { AB } + \mathrm { BD } \geqslant 1 , \quad \mathrm { AC } + \mathrm { CD } + \mathrm { CE } \geqslant 1 , \\ & \mathrm { BD } + \mathrm { CD } + \mathrm { DF } \geqslant 1 , \quad \mathrm { CE } + \mathrm { EF } \geqslant 1 , \quad \mathrm { DF } + \mathrm { EF } \geqslant 1 \end{array}$$

Explain why this is not a standard LP formulation that could be set up as a Simplex tabulation. The variables $\mathrm { AB } , \mathrm { AC } , \ldots$ correspond to arcs in a network. The weight on each arc is the coefficient of the corresponding variable in the objective function.
Draw the network on the vertices in the Printed Answer Booklet. A variable that takes the value 1 corresponds to an arc that is used in the solution and a variable with the value 0 corresponds to an arc that is not used in the solution.
Explain what is ensured by the constraint $\mathrm { AB } + \mathrm { AC } \geqslant 1$. Julie claims that the solution to the problem will give the minimum spanning tree for the network.
Find the minimum spanning tree for the network.
- State the algorithm you have used.
- Show your method clearly.
- Draw the tree.
- State the total weight of the tree.
- Find the solution to the problem given at the start of the question.
- You do not need to use a formal method.
- Draw the arcs in the solution.
- State the minimum value of the objective function.
Kim has a different network, exactly one of the arcs in this network is a directed arc.
Kim wants to find a minimum weight set of arcs such that it is possible to get from any vertex to any other vertex.
Explain why, if Kim's problem has a solution, the directed arc cannot be part of it.

		Brett
		R	S	T
\cline { 3 - 5 } \multirow{3}{*}{Annie}	K	\(( 7,3 )\)	\(( 2,6 )\)	\(( 5,3 )\)
\cline { 3 - 5 }	L	\(( 1,5 )\)	\(( 8,2 )\)	\(( 2,5 )\)
\cline { 3 - 5 }	M	\(( 3,2 )\)	\(( 1,5 )\)	\(( 4,6 )\)
\cline { 3 - 5 }
\cline { 3 - 5 }

\(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	RHS
1	-3	1	0	0	0	0
0	2	0	1	1	0	18
0	-1	2	3	0	1	20

\(\mathrm { A } , \mathrm { B }\)	\(\mathrm { A } , \mathrm { C }\)	\(\mathrm { A } , \mathrm { D }\)	\(\mathrm { A } , \mathrm { E }\)	\(\mathrm { B } , \mathrm { C }\)	\(\mathrm { B } , \mathrm { D }\)	\(\mathrm { B } , \mathrm { E }\)	\(\mathrm { C } , \mathrm { D }\)	\(\mathrm { C } , \mathrm { E }\)	\(\mathrm { D } , \mathrm { E }\)
300	500	900	700	200	600	400	500	-	100

Item	\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)	\(G\)	\(H\)
Mass (kg)	3	4	3.5	2.5	6	7.5	8	5

	Strategy \(X\)	Strategy \(Y\)	Strategy \(Z\)
Strategy \(P\)	4	5	- 4
Strategy \(Q\)	3	- 1	2
Strategy \(R\)	4	0	2

\multirow{7}{*}{From}	\multirow{2}{*}{}	To
		J	K	L	M	N
	J	0	1	1	0	0
	K	1	0	1	0	0
	L	1	0	0	0	1
	M	0	0	2	1	1
	N	0	1	0	1	0

	Cost \(( \pounds )\)	Red	White	Yellow	Pink
Pack A	50	25	25	25	25
Pack B	48	40	30	30	0
Pack C	53	20	30	40	10

	Number of comparisons	3	4	5	6
Shuttle sort	Number of permutations	2	6	8	8
Bubble sort	Number of permutations	1	0	7	16

Activity	A	B	C	D	E	F	G	H	I	J	K
Workers	2	1	1	2	\(n\)	1	2	1	1	1	4

\(P\)	\(x\)	\(y\)	\(z\)	\(s\)	\(t\)	\(u\)	RHS
1	0	- 0.04	0.06	0	0	0.02	4.8
0	0	1	- 1	1	0	0	5
0	0	10.8	7.3	0	1	0.1	24
0	1	0.96	1.06	0	0	0.02	4.8

Activity	A	B	C	D	E	F	G	H
Workers	2	1	1	2	1	1	1	1

Questions — OCR Further Discrete (71 questions)

Browse by module

Browse by board

OCR Further Discrete 2024 June Q5

OCR Further Discrete 2024 June Q6

OCR Further Discrete 2020 November Q1

OCR Further Discrete 2020 November Q2

OCR Further Discrete 2020 November Q3

OCR Further Discrete 2020 November Q4

OCR Further Discrete 2020 November Q5

OCR Further Discrete 2020 November Q6

OCR Further Discrete 2021 November Q1

OCR Further Discrete 2021 November Q2

OCR Further Discrete 2021 November Q3

OCR Further Discrete 2021 November Q4

OCR Further Discrete 2021 November Q5

OCR Further Discrete 2021 November Q6

OCR Further Discrete 2021 November Q7

OCR Further Discrete Specimen Q1

OCR Further Discrete Specimen Q2

OCR Further Discrete Specimen Q3

OCR Further Discrete Specimen Q4

OCR Further Discrete Specimen Q5

OCR Further Discrete 2018 September Q1

OCR Further Discrete 2018 September Q2

OCR Further Discrete 2018 September Q3

OCR Further Discrete 2018 September Q4

OCR Further Discrete 2018 September Q5