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 Mechanics 1 P1 P2 P3 P4 PMT Mocks PURE Paper 1 Paper 2 Paper 3 Pure 1 S1 S2 S3 S4 SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics Stats 1 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 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 Mechanics 1 PURE Pure 1 S1 S2 S3 S4 Stats 1 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 SPS SPS ASFM SPS ASFM Mechanics SPS ASFM Pure SPS ASFM Statistics SPS FM SPS FM Mechanics SPS FM Pure SPS FM Statistics SPS SM SPS SM Mechanics SPS SM Pure SPS SM Statistics 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

OCR Further Discrete 2024 June Q5

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

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

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

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

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:
- give the pivot column used and the value of the pivot element
- write down the value of $P$ after this iteration
- find the values of $x , y$ and $z$ after this iteration
- describe the effect of the iteration geometrically.

OCR Further Discrete 2020 November Q4

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

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

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

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.
- State which item Sam should leave behind to maximise the total value.
- Write down a possible packing with this item omitted.
- Explain why no larger total is possible.

OCR Further Discrete 2021 November Q2

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

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 card numbered 25 has two red digits,
- the card numbered 26 has one red digit,
- the card numbered 148 has no red digits.
- By considering the cards with one digit, two digits and three digits, or otherwise, determine how many cards have no red digits.
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
- the card numbered 2 is in set A ,
- the card numbered 15 is in sets B and C ,
- the card numbered 23 is in none of the sets.
  \includegraphics[max width=\textwidth, alt={}, center]{133395d2-5020-4054-a229-70168f1d0f95-4_588_1150_1667_246}
- By considering the cards with one digit, two digits and three digits, or otherwise, determine how many cards in set A have no red digits.
- Given that, for the cards with no red digits, $n ( B ) = 21 , n ( C ) = 9$ and $n ( A \cap B ) = 12$, use the inclusion-exclusion principle to determine how many of the cards with no red digits are in none of the sets A, B or C.

OCR Further Discrete 2021 November Q4

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

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

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 objective function, $P$, to be maximised.
- The constraints as inequalities.
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.
- The graph of the feasible region.
- The optimal integer valued solution.

OCR Further Discrete 2021 November Q7

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

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

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

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

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

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 March Q1

1 The masses, in kg , of ten bags are given below. $$\begin{array} { l l l l l l l l l l } 8 & 10 & 10 & 12 & 12 & 12 & 13 & 15 & 18 & 18 \end{array}$$

Use first-fit decreasing to pack the bags into crates that can hold a maximum of 50 kg each. Only two crates are available, so only some of the bags will be packed. Each bag is given a value.
Bag A B C D E F G H I J
Mass (kg) 8 10 10 12 12 12 13 15 18 18
Value 6 3 3 2 4 5 4 6 4 4
Find a packing into two crates so that the total value of the bags in the crates is at least 32 .

OCR Further Discrete 2018 March Q2

2 A linear programming problem is $$\begin{array} { l l } \text { Maximise } & P = 4 x - y - 2 z
\text { subject to } & x + 5 y + 3 z \leqslant 60
& 2 x - 5 y \leqslant 80
& 2 y + z \leqslant 10
& x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$

Use the simplex algorithm to solve the problem. In the case when $z = 0$ the feasible region can be represented graphically.
\includegraphics[max width=\textwidth, alt={}, center]{9fe422a0-c498-4ad5-bdfc-f70482960d39-2_636_1619_1564_230} The vertices of the feasible region are $( 0,0 ) , ( 40,0 ) , ( 46.67,2.67 ) , ( 35,5 )$ and $( 0,5 )$, where non-integer values are given to 2 decimal places. The linear programming problem is given the additional constraint that $x$ and $y$ are integers.
Use branch-and-bound, branching on $x$ first, to show that the optimum solution with this additional constraint is $x = 45 , y = 2$. 350 people are at a TV game show. 21 of the 50 are there to take part in the game show and the others are friends who are in the audience, 22 are women and 20 are from London, 2 are women from London who are there to take part in the game show and 15 are men who are not from London and are friends who are in the audience.
Deduce how many of the 50 people are in two of the categories 'there to take part in the game show', 'is a woman' and 'is from London', but are not in all three categories. The 21 people who are there to take part in the game show are moved to the stage where they are seated in two rows of seats with 20 seats in each row. Some of the seats are empty.
Show how the pigeonhole principle can be used to show that there must be at least one pair of these 21 people with no empty chair between them. The 21 people are split into three sets of 7 . In each round of the game show, three of the people are chosen. The three people must all be from the same set of 7 but once two people have played in the same round they cannot play together in another round. For example, if A plays with B and C in round 1 then A cannot play with B or with C in any other round.
By first considering how many different rounds can be formed using the first set of seven people, deduce how many rounds there can be altogether.

OCR Further Discrete 2018 March Q4

4 The graph below connects nine vertices A, B, ..., H, I.
\includegraphics[max width=\textwidth, alt={}, center]{9fe422a0-c498-4ad5-bdfc-f70482960d39-3_543_693_1347_680}

(a) Show that the minimum sum of the degrees of each pair of non-adjacent vertices is 9 .
(b) Explain what you can deduce from the result in part (a).
Use Kuratowski's theorem to prove that the graph is non-planar.
Prove that there is no subgraph of the graph that is isomorphic to $\mathrm { K } _ { 4 }$, without using subdivision or contraction.

OCR Further Discrete 2018 March Q5

5 The diagram represents a map of seven locations (A to G) and the direct road distances (km) between some of them.
\includegraphics[max width=\textwidth, alt={}, center]{9fe422a0-c498-4ad5-bdfc-f70482960d39-4_382_771_356_644} A delivery driver needs to start from his depot at D , make deliveries at each of $\mathrm { A } , \mathrm { B } , \mathrm { F }$ and G , and finish at D .

Write down a route from A to G of length 70 km . The table shows the length of the shortest path between some pairs of places.
D A B F G
D -
A - 70
B - 84
F 84 -
G 70 -
(a) Complete the table.
(b) Use the nearest neighbour method on the table, starting at D , to find the length of a cycle through $\mathrm { D } , \mathrm { A } , \mathrm { B } , \mathrm { F }$ and G , ignoring possibly repeating E and C .
By first considering the table with the row and column for D removed, find a lower bound for the distance that the driver must travel.
What can you conclude from your previous answers about the distance that the driver must travel? A new road is constructed between D and F . Using this road the driver starts from D , makes the deliveries and returns to D having travelled just 172 km .
Find the length of the new road if
(a) the driver does not return to D until all the deliveries have been made,
(b) the driver uses the new road twice in making the deliveries.

OCR Further Discrete 2018 March Q6

6 The activities involved in a project, their durations, immediate predecessors and the number of workers required for each activity are shown in the table.

Activity	Duration (hours)	Immediate predecessors	Number of workers
A	6	-	2
B	4	-	1
C	4	-	1
D	2	A	2
E	3	A, B	1
F	4	C	1
G	3	D	1
H	3	E, F	2

Model the project using an activity network.
- Calculate the early and late event times.
- Calculate the independent and interfering float for each activity.
- Draw a cascade chart for the project, showing each activity starting at its earliest possible start time.
- Construct a schedule to show how three workers can complete the project in the minimum possible time.

		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

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

Bag	A	B	C	D	E	F	G	H	I	J
Mass (kg)	8	10	10	12	12	12	13	15	18	18
Value	6	3	3	2	4	5	4	6	4	4

Questions — OCR Further Discrete (67 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 March Q1

OCR Further Discrete 2018 March Q2

OCR Further Discrete 2018 March Q4

OCR Further Discrete 2018 March Q5

OCR Further Discrete 2018 March Q6